To waste some time today I played some Super Mario Bros 3 on my Wii. I only made it trough three levels before I reached the first Toad House. Upon receiving the item from Toad I decided to investigate something I've wanted to know for, I don't know, maybe 15 years. How exactly does the game decide what item you receive? I remember as a child that people playing Super Mario Bros 3 did the weirdest stuff in Toad Houses to improve their item karma. Running around, doing weird jumps, whatever.
Anyway, I really wanted to know when the game decides what item you receive and how it decides that. Does the game already know what item you receive as soon as you enter the Toad House? Are the items placed in the boxes when you enter the Toad House? Does it do any other weird stuff?
Thanks to FCEUX and IDA Pro it did not take long to figure out what's going on. Here is the relevant code:
ROM:D19B LDX byte_3EB
ROM:D19E DEX
ROM:D19F CPX #5
ROM:D1A1 BMI loc_D1B1
ROM:D1A3 LDA byte_782
ROM:D1A6 AND #$F
ROM:D1A8 TAY
ROM:D1A9 LDA RandomNess,Y
ROM:D1AC CLC
ROM:D1AD ADC ToadHouseIndex,X
ROM:D1B0 TAX
ROM:D1B1
ROM:D1B1 loc_D1B1: ; CODE XREF: ROM:D1A1
ROM:D1B1 LDA ItemArray,X
ROM:D1B4 TAX
ROM:D1B5 INX
ROM:D1B6 RTS
Where the three arrays referenced in the code are
ROM:D13B ItemArray: .BYTE $C ; DATA XREF: ROM:loc_D1B1
ROM:D13C .BYTE 8
ROM:D13D .BYTE 4
ROM:D13E .BYTE 5
ROM:D13F .BYTE 6
ROM:D140 .BYTE 4
ROM:D141 .BYTE 5
ROM:D142 .BYTE 6
ROM:D143 .BYTE 1
ROM:D144 .BYTE 2
ROM:D145 .BYTE 3
ROM:D146 .BYTE 4
ROM:D147 .BYTE 2
ROM:D148 .BYTE 3
ROM:D149 .BYTE 5
ROM:D14A ToadHouseIndex: .BYTE 2 ; DATA XREF: ROM:D1AD
ROM:D14B .BYTE 3
ROM:D14C .BYTE $A
ROM:D14D .BYTE $A
ROM:D14E .BYTE $A
ROM:D14F .BYTE 5
ROM:D150 .BYTE 8
ROM:D151 .BYTE $B
ROM:D152 .BYTE $E
ROM:D153 .BYTE $11
ROM:D154 RandomNess: .BYTE 0 ; DATA XREF: ROM:D1A9
ROM:D155 .BYTE 1
ROM:D156 .BYTE 2
ROM:D157 .BYTE 0
ROM:D158 .BYTE 1
ROM:D159 .BYTE 2
ROM:D15A .BYTE 0
ROM:D15B .BYTE 1
ROM:D15C .BYTE 2
ROM:D15D .BYTE 0
ROM:D15E .BYTE 1
ROM:D15F .BYTE 2
ROM:D160 .BYTE 0
ROM:D161 .BYTE 1
ROM:D162 .BYTE 2
ROM:D163 .BYTE 0
Here's a pseudo-disassembly of the code:
if toadhouse_index < 6:
item_index = toadhouse_index
else:
randomness = PRNG[$782] % 0x03
item_index = toadhouse_index + randomness
item = item_array[item_index]
So yeah, basically what happens is this. Depending on what Toad House
you are in you receive different items. If the identifier of the Toad
House you are in is between 1 and 5 you will always receive the same
item (like the Frog Suit, no matter what box you pick, in the first
Toad House of World 3). Toad Houses with higher IDs offer three random
items. What item you receive is determined only after you open a box.
So, in fact only the box you open is filled. The other two boxes are
never touched. They are total smoke screens whose only purpose is to
fool the player into believing he actually takes part in the decision
what item to receive.
The RandomNess array basically simulates a module operation on the
pseudo-randomly generated input value to cut down the random value to
something between 0 and 2 (for the three boxes).
ItemIndex is actually longer than indicated in the disassembly above.
It goes down until (and including) the three 0x0A values in
ToadHouseIndex. The real ToadHouseIndex starts only after the three
0x0A values because Toad House IDs less than six are not used to index
into the ToadHouseIndex array.
The ItemArray contains identifiers of the items you can receive in a
Toad House. The first five values are for Toad Houses where only one
item can be found. The other parts of the array form triples (starting
at indices 0x05, 0x08, 0x0B, 0x0E, and 0x11 as seen in ToadHouseIndex)
that define what items you can find in what Toad House. The exact
meaning of the items can be found in the
Data Crystal Wiki.
So yeah, all mysteries solved. You open a box in the Toad House and the
game randomly gives you one of the available items for that Toad House.
To finish this post, here's what the pseudo-random generator looks like:
ROM:997D ; =============== S U B R O U T I N E =======================================
ROM:997D
ROM:997D
ROM:997D sub_997D: ; CODE XREF: sub_B502+52
ROM:997D LDX #0
ROM:997F LDY #9
ROM:9981 LDA RandomNess
ROM:9984 AND #2
ROM:9986 STA byte_0
ROM:9988 LDA byte_782
ROM:998B AND #2
ROM:998D EOR byte_0
ROM:998F CLC
ROM:9990 BEQ loc_9993
ROM:9992 SEC
ROM:9993
ROM:9993 loc_9993: ; CODE XREF: sub_997D+13
ROM:9993 ; sub_997D+1B
ROM:9993 ROR RandomNess,X
ROM:9996 INX
ROM:9997 DEY
ROM:9998 BNE loc_9993
ROM:999A RTS
ROM:999A ; End of function sub_997D
ROM:999A
ROM:999A ; ---------------------------------------------------------------------------
In pseudo-disassembled code:
if (RandomNess[0] & 0x02) ^ (RandomNess[1] & 0x02) == 0:
CF = 0
else:
CF = 1
for i := 0 to 8:
CF_TEMP = RandomNess[i] & 0x01
RamdonNess[i] = (RandomNess[i] ROR 1) | (CF << 7)
CF = CF_TEMP
Basically you have a 72 bits array that is originally seeded (at
another place in code) with {0x88, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00} and then regularly re-calculated (probably on each NES
interrupt) to continuously change all values of the buffer. This is a bit difficult to describe in Pseudo-Code as the Carry Flag plays a very important role in the algorithm.