TASVideos

Tool-assisted game movies
When human skills are just not enough

Random Generators

Randomness functions in different games

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

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:
    1. Execute RndFunc1 once.
    2. Reset RndCount2.
    3. Ready the Chance deck array.
    4. Execute RndFunc1 three times.
    5. Take last 8 bits of RndVal1, XOR with RndCount2, integer divide by 16, and use this value as an offset to the deck array.
    6. Check deck array. If already occupied, increment RndCount2. Otherwise occupy offset, and try next card.
    7. 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:
    1. Execute RndFunc1 once, then RndFunc2 once, then RndFunc1 five times.
    2. Take last 8 bits of RndVal1, XOR with RndVal2, mod 6, and increment for Die 2.
    3. Execute RndFunc1 five times.
    4. 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

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  2A:          rol a
        $D66B  2A:          rol a
        $D66C  49 41:       eor #$41
        $D66E  2A:          rol a   
        $D66F  2A:          rol a   
        $D670  49 93:       eor #$93
        $D672  65 55:       adc RandomCtrl2
        $D674  85 54:       sta RandomCtrl1
        $D676  2A:          rol a
        $D677  2A:          rol a
        $D678  49 12:       eor #$12
        $D67A  2A:          rol a   
        $D67B  2A:          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 1D:        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


Combined RSS Feed
RandomGenerators last edited by Zeupar on 2012-03-31 22:38:37
Page info and history | Latest diff | List referrers | View Source