Random number generators in NES games. It's mostly assembly code, but
the purpose is to document them as information that is hopefully practical.
### Legend of Kage

### Rockman 1

### Rockman 2

### Monopoly

### Bomberman

### FDS Backgammon

Table of contents [expand all] [collapse all]

In Legend of Kage, the randomness function does not actually take samples
of player input, or any other volatile data. Legend of Kage has a function
"UpdateRandom" at address $A4E5, that simply multiplies the value of RndSeed
(memory address $0F) by 5 and adds 11. It uses the memory address $0E as a temporary, but it does not use its prior value.

The function is called contiguously in an infinite loop by the main program. It's also called manually each time a sample of the RndSeed is taken.

The function is called contiguously in an infinite loop by the main program. It's also called manually each time a sample of the RndSeed is taken.

The actual randomness of it comes from the fact that depending on the duration of the NMI (in number of CPU cycles), a different number of iterations of the UpdateRandom function is called. The more time the NMI takes, the less time elapses after the NMI before the next NMI occurs, and thus, the less iterations the UpdateRandom function experiences between the two NMIs.

The duration of the NMI is influenced by *everything* the game does, including the music, checking for collisions, checking for input, etc. This makes the randomness in Legend of Kage extremely volatile, and extremely non-portable between different emulators. Differences between timings of memory accesses, timings of CPU instructions, timings of DMA transfers, timings of NMI trigger, all timing differences can throw the randomness off.

; This piece of code is executed at every frame. It's invoked by the NMI routine ; even when the game is lagging. The variable $0D is a temporary variable ; used by the game for various purposes. When the screen scrolls, its value ; is 0x03 and otherwise it's 0x78 + number of onscreen sprites, or something ; like that. It is purposely made hard to predict. RandomUpdate: ;at $D574 lda $0D eor RandomSeed ;at memory address $46 adc FrameCounter ;at memory address $23 lsr a sta RandomSeed ; This function is the frontend to randomness calculation. ; Input: ; A = max value ; Output: ; A = random number (smaller than input was). ; Modifies: ; carry flag ; $40 ; This function gives the same value for every invokation during ; the same frame. It is used by almost everything in the game. RandomFunc: ;at $C5A0 sta $40 lda RandomSeed sec loop: sbc $40 bcs loop adc $40 rtsAs an example, here's how the game determines which bonus to give when an enemy is killed:

CreateBonus: ;at $05BF13 lda #100 jsr RandomFunc ldy #$3B ldx #5 loop: cmp BonusProbabilityTable,x bcc endloop iny dex bpl loop endloop: cpy #$3B ; 3B=no item, 3C=pearl, 3D=small wpn, and so on beq noitem ; Spawn the bonus drop tya jsr CreateEnemy ... noitem: ... BonusProbabilityTable: .byt 99, 97, 95, 80, 65, 12 ; Probabilities for: ; 1UP (1%), Big Energy (2%), Big Weapon (2%), ; Small Energy (15)%, Small Weapon (15%), Score Pearl (53%)

; This piece of code is executed at every frame. It's invoked by the NMI routine ; even when the game is lagging. The variable $480 is the fractional part ; of Megaman's X position. When $480 wraps around a full cycle, Megaman's ; X position will be incremented by 1 pixel. This variable is only ; influenced by Megaman's movements. RandomUpdate: ;at $D0C6 lda $0480 eor RandomSeed ;at memory address $4A adc FrameCounter ;at memory address $1C lsr a sta RandomSeed ; This function is a generic math function (it performs 8-bit division), ; but it is also used as the frontend to randomness calculation. ; Input: ; $01 = divident ; $02 = divisor ; Output: ; $03 = result ; $04 = remainder (modulo) ; Modifies: ; Y ; carry flag ; ; It is used as a randomness function by copying the random seed ($4A) ; into $01 and setting $02 as the max value. DivMod: ;at $C84E lda #0 sta $03 sta $04 lda $01 ora $02 bne nonzero sta $03 rts nonzero: ldy #8 loop: asl $03 rol $01 rol $04 sec lda $04 sbc $02 bcc skip sta $04 inc $03 skip: dey bne loop rts

RndVal1_A = $0037

RndVal1_B = $0038

RndVal1_C = $0039

RndVal2 = $0302

RndCount1 = $0027

RndCount2 = $00F7

RndVal1_B = $0038

RndVal1_C = $0039

RndVal2 = $0302

RndCount1 = $0027

RndCount2 = $00F7

Execution of RndFunc1: The current 24-bit^{[1]} random seed RndVal1 is left-shifted by 1.
The new entering bit is 0 if the 3rd and 4th bits from the left are the same, and 1 otherwise.

This is an event of what is better known as a linear feedback shift register.

Execution of RndFunc2: Execute RndFunc1 5 times and add 35 to RndVal2 (mod 256).

Randomization occurs every frame (except those which are lagging or playing sound effects). Which randomization occurs on a frame depends on which stage the game is at.

Note: All divisions and moduli operate on *unsigned* 8-bit integers.

Before the game:

- Random seed at frame 7: 3E2AD2
- Increment of RndCount1 begins after a button is pressed to begin.

- Game is not at enter-name screen: Increment RndCount1. Then execute RndFunc1 once. (RndCount1++, RndVal1 << 1)
- Game is at enter-name screen: Increment RndCount1. Then execute RndFunc1 once. Then take RndCount1, mod 32, and execute RndFunc1 that many times. Then execute RndFunc1 once. If A is pressed, reset RndCount1. (RndCount1++, RndVal1 << 2-33)
- Game is setting card decks:

- Execute RndFunc1 once.
- Reset RndCount2.
- Ready the Chance deck array.
- Execute RndFunc1 three times.
- Take last 8 bits of RndVal1, XOR with RndCount2, integer divide by 16, and use this value as an offset to the deck array.
- Check deck array. If already occupied, increment RndCount2. Otherwise occupy offset, and try next card.
- Go back to step 4 unless the deck is full (no more cards). In that case go back to step 3, set RndCount2 to 16, and repeat with the Community Chest deck array. When both decks are done, stop.

- (RndVal1 << a lot)

During the game:

- Game is not showing overhead board: Execute RndFunc1 once. (RndVal1 << 1)
- Player is waiting to roll: Just before this happens, reset RndCount1. Increment RndCount1. Then execute RndFunc1 once, then RndFunc2 once, then, if not turn after double or opposing player menu, execute RndFunc1 twice. (RndCount1++, RndVal1 << 8 or 6, RndVal2 += 35)
- Player is rolling: Increment RndCount1. Then execute RndFunc1 once, then RndFunc2 once, then RndFunc2 twice, then if RndCount1 is divisible by 4, execute RndFunc1 twice. (RndCount1++, RndVal1 << 18 or 16, RndVal2 += 105)
- Player has thrown the dice: Execute RndFunc1 once, then RndFunc2 once. (RndVal1 << 6, RndVal2 += 35)
- On the frame to get dice roll:

- Execute RndFunc1 once, then RndFunc2 once, then RndFunc1 five times.
- Take last 8 bits of RndVal1, XOR with RndVal2, mod 6, and increment for Die 2.
- Execute RndFunc1 five times.
- Take last 8 bits of RndVal1, mod 6, and increment for Die 1.

- (RndVal1 << 16, RndVal2 += 35).

Everything marked (Acmlm) was found by Acmlm. Everything else was found by FractalFusion.

Some additional comments were added to the code.

- Random functions:

RndVal1_A = $0037 RndVal1_B = $0038 RndVal1_C = $0039 RndVal2 = $0302 ;(Acmlm) ;**************************************** ;* Shift RndVal1 left by 1 bit * ;* New bit entering RndVal1_C = ? * ;* Load random from RndVal1_C * ;**************************************** $C13E ; RndVal1 - A - C RndFunc1: LDA RndVal1_A ;01111000 11111111 00110110 - 01111000 - 1 ASL ; - 11110000 - 0 EOR RndVal1_A ; - 10001000 - 0 ASL ; - 00010000 - 1 ASL ; - 00100000 - 0 ASL ; - 01000000 - 0 <-- entering bit ROL RndVal1_C ;01111000 11111111 01101100 - 01000000 - 0 ROL RndVal1_B ;01111000 11111110 01101100 - 01000000 - 1 ROL RndVal1_A ;11110001 11111110 01101100 - 01000000 - 0 LDA RndVal1_C ; - 01101100 - 0 RTS ;**************************************** ;* Increment RndVal2 by 35 ($23) * ;* Run RndFunc1 5 times * ;**************************************** $C56D RndFunc2: LDX #$05 loop: LDA RndVal2 CLC ADC #$07 STA RndVal2 JSR RndFunc1 DEX BNE loop RTS

- Random analysis:

(Acmlm) 37 38 39 0302 ---------------------------------------- 70 19 EE = 011100000001100111101110 ¦ 00 Before starting (random 1) E0 33 DC = 111000000011001111011100 ¦ 00 $0037-0039 << 1 C0 67 B9 = 110000000110011110111001 ¦ 00 $0302 + 00 80 CF 72 = 100000001100111101110010 ¦ 00 01 9E E4 = 000000011001111011100100 ¦ 00 03 3D C8 = 000000110011110111001000 ¦ 00 06 7B 90 = 000001100111101110010000 ¦ 00 0C F7 20 = 000011001111011100100000 ¦ 00 19 EE 40 = 000110011110111001000000 ¦ 00 33 DC 81 = 001100111101110010000001 ¦ 00 67 B9 02 = 011001111011100100000010 ¦ 00 80 CF 72 = 100000001100111101110010 ¦ 00 Before rolling (random 2) CF 72 05 = 110011110111001000000101 ¦ 23 $0037-0039 << 8, $0027 is reset when this activates 72 05 46 = 111000100000010101000110 ¦ 46 $0302 +$23 05 46 58 = 000001010100011001011000 ¦ 69 3F 2B A1 = 001111110010101110100001 ¦ D2 While rolling (random 3) 84 17 CE = 100001000001011111001110 ¦ 3B $0037-0039 <<18,16,16,16,18,16,16,16,... depending on $0027 CE 30 E1 = 110011100011000011100001 ¦ A4 $0302 +$69 E1 49 44 = 111000010100100101000100 ¦ 0D 44 8F 6F = 010001001000111101101111 ¦ 76 BC D9 1B = 101111001101100100011011 ¦ DF After rolling (random 4) $0037-0039 << 6, 16 when getting dice values $0302 +$23

- before game:

;frame 7: 3E 2A D2 ;RAM(27)++ starts 3 frames after first press of A and occurs on every frame ; ***** ; executes first ; ***** ... $C053 JSR RndFunc1 ; executes always on every frame $C056 JSR $C2DE ... ; ***** ; executes when entering name ; starts on accept input ; stops one frame after OK ; ***** ;RAM($27)++ (somewhere) ... $94D6 LDA $27 $94D8 AND #$1F ;mod 32 $94DA TAX Iterate: ; iterates RAM($27)%32+1 times. $94DB JSR RndFunc1 $94DE DEX $94DF BPL Iterate ... ; ***** ; set up cards ; ***** ... $84A2 JSR Chance ; if jump, chance first, otherwise comm chest $84A5 LDX #$10 Chance: $84A7 STX $F6 ; 0 if chance, 16 if comm chest $84A9 STX $F7 $84AB LDY #$F $84AD LDA #$FF Init: ;sets chance/comm chest entries to $FF $84AF STA $472,X $84B2 INX $84B3 DEY $84B4 BPL Init $84B6 LDY #$F TryInsertCard: $84B8 JSR RndFunc1 $84BB JSR RndFunc1 $84BE JSR RndFunc1 $84C1 EOR $F7 $84C3 LSR ; $84C4 LSR ; $84C5 LSR ; $84C6 LSR ; idiv by 16, reduce to <16 $84C7 ORA $F6 ; +0 if chance, +16 if comm chest $84C9 TAX ;deck offset $84CA LDA $472,X $84CD BMI InsertCard ;vacant spot $84CF INC $F7 $84D1 JMP TryInsertCard InsertCard: $84D4 TYA $84D5 STA $472,X $84D8 DEY ;Next Card $84D9 BPL TryInsertCard $84DB RTS ;Done ...

- during game:

; (included again) ; ***** ; executes first ; ***** ... $C053 JSR RndFunc1 ; executes always on every frame $C056 JSR $C2DE ... ; ***** ; executes when on overhead board view ; ***** ... $8110 JSR $8585 $8113 JSR RndFunc2 ;executes on all but random 1 $8116 JSR $8585 $8119 LDA $26 ;0=not rolling 1=rolling $811B BEQ $8120 ;not sure why they double-check; see below (RandomWhenRolling) $811D JMP RandomWhenRolling ... ; ***** ; executes only on random 2 ; ***** ... $FA1B JSR RndFunc1 ;executes only on random 2 $FA1E AND #$1F ;mod 32 $FA20 CMP #$A ;mod 10 $FA22 BCC $FA28 $FA24 SBC #$A $FA26 BCS $FA20 $FA28 STA $5D $FA2A JSR RndFunc1 ;executes only on random 2 $FA2D AND #$D0 ... ;(Acmlm) ;**************************************** ;* Randomness variation when rolling * ;**************************************** RandomWhenRolling: $816E: LDA $0026 CMP #$01 ;equal when rolling BNE NotRolling JSR RndFunc2 JSR RndFunc2 INC $0027 LDA $0027 AND #$03 ;mod 4 BNE Skip ;... if RAM($27)%4==0 (i.e. every 4 frames) ... JSR RndFunc1 ;do this ... STA $00FA AND #$42 BNE $8190 LDA #$02 JSR $CB9A $8190: JSR RndFunc1 ;... and this AND #$12 BEQ $819C LDA #$01 STA $0504 Skip: $819C: ... NotRolling: JSR $8585 ;(Acmlm) ;**************************************** ;* Determine (and display) the dice * ;* Values are randomized between them * ;**************************************** $81EB: LDX #$01 NextDice: STX $00FB ... $8214: JSR RndFunc1 ;Randomize and load random value JSR RndFunc1 JSR RndFunc1 JSR RndFunc1 JSR RndFunc1 CPX #$01 ;If second dice, XOR with RndVal2 BNE Mod6 EOR RndVal2 Mod6: CMP #$06 ;modulo 6 BCC Save SBC #$06 BCS Mod6 Save: ADC #$01 ;0-5 -> 1-6 STA $0300,X ;store dice ... $825E: LDX $00FB DEX BPL NextDice

(RNG = Random Number Generator)

[1] The RndVal1 RNG is actually 22-bit, not 24-bit, because the first two bits are superfluous.

Some trivia:

- The RndVal1 RNG has a period of 2^22-1. Since 0 is a pathological case, it means that all nonzero 22-bit numbers are contained in this period.
- The RndVal1 RNG is slightly biased toward the die numbers 1, 2, 3, 4, because of mod 6 operating on (unsigned) 8-bit numbers.
- The RndVal1 RNG is reversible, a fact which can also be derived from its period.

Bomberman has a very complex random function. This may be necessary so as
to avoid any noticeable patterns in the randomly generated level contents.

Translated to C++, it becomes:

PermutateRandomCtrlVars $D668 A5 54: lda RandomCtrl1 $D66A 2: rol a $D66B 2: rol a $D66C 49 41: eor #$41 $D66E 2: rol a $D66F 2: rol a $D670 49 93: eor #$93 $D672 65 55: adc RandomCtrl2 $D674 85 54: sta RandomCtrl1 $D676 2: rol a $D677 2: rol a $D678 49 12: eor #$12 $D67A 2: rol a $D67B 2: rol a $D67C 65 56: adc RandomCtrl3 $D67E 85 55: sta RandomCtrl2 $D680 65 54: adc RandomCtrl1 $D682 E6 56: inc RandomCtrl3 $D684 D0 09: bne + ; $D68F $D686 48: pha $D687 A5 57: lda RandomCtrl4 $D689 18: clc $D68A 69 1: adc #$1D $D68C 85 57: sta RandomCtrl4 $D68E 68: pla + $D68F 45 57: eor RandomCtrl4 $D691 60: rtsThis function is called whenever randomness is needed, and often, the resulting value is even further permutated, for example, by executing "ror a" twice. The function is also called once every frame on the title screen.

Translated to C++, it becomes:

unsigned char PermutateRandomVars(unsigned char random[3], bool carry) { unsigned tmpval = carry << 8; tmpval = ((random[0] << 4) | ((tmpval & 0x100) >> 5) | (random[0] >> 5)) ^ 0x87; tmpval = (tmpval & 0xFF) + ((tmpval & 0x100) >> 8) + random[1]; random[0] = tmpval; tmpval = ((random[0] << 4) | ((tmpval & 0x100) >> 5) | (random[0] >> 5)) ^ 0x48; random[0] = tmpval; tmpval = (tmpval & 0xFF) + ((tmpval & 0x100) >> 8) + random[2]; random[1] = tmpval; tmpval = (tmpval & 0xFF) + ((tmpval & 0x100) >> 8) + random[0]; if(!++random[2]) { random[3] += 29; } return tmpval ^ random[3]; }It does such a meticulous job that I think that it may be based on some standard cryptographical function such as CRC32... But I don't know.

This code describes the RNG for FDS Backgammon.

At the title screen, the RNG begins at one of 32 possible sequences (0-31), and runs through the sequence one number per frame. When the title screen is cleared, the RNG stops and all dice rolls are determined.

Power-on uses sequence 31. For other sequences, do a reset when memory address $33 is the sequence number mod 32.

Because all dice rolls for a game are determined before it begins, nothing useful will likely occur, given that GBC Backgammon dice rolls can be manipulated just before rolling the dice. At least 17 rolls (some of them high doubles) must be done by both sides to complete the game. If a home board shutout is performed with an opposing piece on the bar, this prevents the opponent from making a roll, but the added flexibility is very small.

;initial seed function, one of 32 values $6245: LDX $33 ;incrementing value, not cleared on reset, used as seed ... LDA #0 $6254: STA $10,Y ;probably some clearing routine DEY BNE $6254 DEC $11 BPL $6254 TXA BNE $6262 LDX #$5F ;power-on value used as seed $6262: STX $500 ;put seed here ;initial 55 values ;recursion is length 55 and mod 180 ;first 55 values depend on one of 32 seeds $9CAB: LDA $500 ;take seed AND #$1F ;mod 32 STA $10 ;put in mem10 STA $637 LDA #$1 STA $11 ;mem11=1 LDY #$14 ;offset starts at 20 and will increment by 21 (mod 55) LDX #$36 ;X=54, 55 iterations CreateValue: LDA $11 STA $601,Y ;store mem11 at index LDA $10 SEC SBC $11 ;A=mem10 - mem11 BPL $9CCC CLC ADC #$B4 ;mod 180 $9CCC: STA $11 ;new value for mem11 and next index LDA $601,Y ;back to this index STA $10 ;put in mem10 TYA CLC ADC #$15 ;add 21 to offset CMP #$37 BCC $9CDD SBC #$37 ;mod 55 $9CDD: TAY ;new index DEX ;next BNE CreateValue ;if 0 done ;now execute RndFunc 3 times JSR RndFunc ;$9CE7 JSR RndFunc ;(falling into RndFunc) ;Recursion function ;Technically it throws 55 new numbers at once ;since it uses $600 as a pointer into a 55-number array ;It works like this: x_n = x_(n-55) - x_(n-24) (mod 180) RndFunc: $9CE7: LDY #$0 ;initial Next: $9CE9: TYA ;A=Y (index) STA $10 ;mem10 = A CMP #$18 BCS $9CF4 ;this is basically A-24 (mod 55) ADC #$1F BCC $9CF6 $9CF4: SBC #$18 $9CF6: TAY ;used as index LDA $601,Y STA $11 ;take value at index-24 and store in mem11 LDY $10 ;Y=original index LDA $601,Y ;A=index value SEC SBC $11 ;A-=mem11 BCS $9D08 ADC #$B4 ;mod 180 $9D08: STA $601,Y ;new value INY ;next index CPY #$37 ;if index reaches 55, done BNE Next LDA #0 ;start at index 0 STA $600 TAY LDA $601,Y ;(first value) RTS ; this calls a random value; used in GetDiceRoll GetRandomVal: INC $600 ;increment index LDA $600 ;index CMP $37 BCC NotOverflow ;if overflow execute RndFunc JSR RndFunc LDA #$0 ;totally redundant STA $600 $9CA6: NotOverflow: TAY LDA $601,Y ;value at index RTS ; determine dice roll GetDiceRoll: $815C: LDA $30C BNE Return ;if not ready, do nothing JSR GetRandomVal ;$9C94 LDY #$0 $8166: CMP #$24 BCC $816F SBC #$24 ;mod 36, Y=A/36 A%=36 INY BCS $8166 $816F: STA $10 ;mem10=A TYA STA $11 ;mem11=Y ASL ASL ASL ;8*Y SEC SBC $11 ;7*Y CLC ADC $10 ;7*Y+A CMP #$24 BCC $8183 SBC #$24 ;mod 36 TAY LDA LookUpTable,Y ;refer to look-up table 0<=Y<=35 81CF-81F2 PHA LSR LSR LSR LSR STA $46 ;idiv 16 upperhalfbyte, die 1 PLA AND #$F ;mod 16 lowerhalfbyte, die 2 STA $47 ... Return: RTS ;all values of the look-up table denote upper-lower paired representation of a dice roll LookUpTable: $81CF: $14 $66 $36 $65 $63 $11 $23 $33 $16 $31 $21 $53 $51 $61 $62 $35 $44 $22 $12 $32 $55 $34 $56 $25 $13 $43 $41 $42 $46 $15 $24 $52 $45 $26 $64 $54

RandomGenerators last edited by Zeupar on 2012-03-31 22:38:37

Page info and history | Latest diff | List referrers | View Source