Random number generators in NES games. It's mostly assembly code, but
the purpose is to document them as information that is hopefully practical.
Table of contents [
expand all] [
collapse all]
Legend of Kage
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 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.
Rockman 1
; 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
rts
As 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%)
Rockman 2
; 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
Monopoly
RndVal1_A = $0037
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.
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.
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
(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
;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
...
; (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
Bomberman has a very complex random function. This may be necessary so as
to avoid any noticeable patterns in the randomly generated level contents.
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: rts
This 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.
FDS Backgammon
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