Re: [stella] entropy & randomness

Subject: Re: [stella] entropy & randomness
From: Kevin Horton <khorton@xxxxxxxxxxx>
Date: Tue, 09 Oct 2001 01:44:47 -0500
At 23:43 10/8/01 -0400, you wrote:

I'm messing with the random number generator from Suicide Mission. Here it
is for reference:

       SBC RNDL
       ROR RNDH
       ROR RNDL
       LDA RNDL
       RTS question is, would it be more `random' to call this once every frame,
or only when I actually need a random number (maybe less than once a frame,
the program I'm messing with changes COLUBK every 32 frames)

The skinny on random number generation:

I was going to write this up eventually, but now seems like a good time to do it.

Usually, in a videogame, random numbers are generated via an "LFSR" or linear feedback shift register. These numbers are apparently random when one takes a small sample, but the pattern will eventually repeat. For a good demonstration of this, listen to the atari 2600's sounds. It uses LFSR's to generate the different distortions. You can "hear" when the sound "repeats" on distortion 08h. This is as close to white noise as the 2600 can generate.

The code snippet above is indeed one form of an LFSR. The "Traditional" method of making one of these is to use a shift register of N bits with 2 or 4 of the register's bits being XORed to generate the bit that gets clocked in.

With this style of LFSR, your maximum count is (2^N)-1 pseudorandom numbers before the sequence repeats. 32 bits gives (2^32)-1 or 4294967295 states before it repeats. That should be nice and random :-). Note that this is the number of unique random bits you will get, so divide by 8 if you're using bytes.

The _TTL Cookbook_ only goes up to 31 stages, and they suggest bits 28 and 31 so that is what I will use as well on my 6502 code example.

.org 00080h

rand0:        .block 1
rand1:        .block 1
rand2:        .block 1
rand3:        .block 1   ;reserve 4 bytes for our random # generator

.org 01000h

;A,B = bits to XOR together on rand3 ; 7654 3210 ; xAxx Bxxx

random:       lda rand3    ;we need to XOR bits 27 and 30 (counting from 0)
              rol a        ;30 in bit #6 (of rand3)
              rol a        ;27 in bit #4 (of rand3)
              eor rand3    ;XOR the two together
              rol a
              rol a        ;pop the XOR'd bit out into carry
              rol rand0
              rol rand1
              rol rand2    ;rotate 32 bits' worth
              rol rand3    ;note carry = random bit

randbyte: ldx #7

rb_loop:      jsr random
              bpl rb_loop  ;loop 8 times to get a random byte
              lda rand3    ;get from rand3 so if we use random: it won't reuse
              rts          ;bits

You should call the random # routine at least once a frame, even if it is not being used. This harnesses the randomness of the player to your advantage, since it will skip many states when the program does not require a random number. Say, you start at the same random # seed (see below for setting one on startup) every time, depending on which frame the player pressed the start button, he will start in a different place unless he has *good* timing and can hit on the correct 1/60th of a second to get in the same place on the sequence.

One curious thing about these LFSR's- each unique state will only occur *once* per run through the complete sequence. i.e. 012345678h will only occur once in the entire sequence before it repeats.

There is one major "gotcha" which brings us to seeding your random number generator so the results are even more random. Never load all 0's into an LFSR. Doing so will result in no random numbers being generated. 0 XOR 0 = 0. This is why you get (2^N)-1 unique states; the all 0's state is disallowed. Note that the LFSR, once it is set non-zero, can never get stuck at all 0's. It will repeat its sequence forever.

As for seeding it, I suggest this method. It seems to work very effectively.
Note I also initialize the 2600 at the same time by writing 000h to all zeropage addresses, and I set the SP to 0ffh.

init2600: ldx #000h ;start at byte 00000h in RAM

ir_loop:          txa
                  eor #03h      ;prevent XORing regs with themselves
                  and #03h      ;make sure all 4 regs get a chance at being
                  tay           ;seeded
                  lda 000h,x
                  eor rand0,y   ;xor is best for this since all bits have an
                  sta rand0,y   ;equal chance at being flipped.
                  eor lda #0    ;load #00h into RAM
                  sta 000h,x
                  txs           ;set stack to 0ffh at end of loop :-)
                  bne ir_loop
                  lda rand0
                  ora rand1
                  ora rand2
                  ora rand3     ;check for 000000000h state. bad juju if so
                  bne no_prob
                  inc rand2     ;set rand2 to 001h.

no_prob: rts

Basically, the routine grabs whatever happens to be in the TIA regs, and in RAM and XORs it with the random # registers. Note that the eor #03h is very important, since it prevents the registers XORing themselves. This would set them to 00h. After it grabs what happens to be in RAM/TIA, it writes 00h to the location, and sets the stack. Since x will be 0ffh before the loop ends, we get a "free" way to set the stack. Cute, hunh. As a bonus, X will = 0 which may be useful on return from this routine.

After that, the random # register is checked for all 0's. This is of course the "bad" state, and must be avoided. Setting rand2 to 001h is good enough, because after 30 or so iterations (half a second of playing time) it is good and random again. The odds of this happening are vanishingly small, however, except maybe on an emulator (which may initalize RAM to all 000h Even so, the TIA addresses shouldn't all read 00h).

A very good example of an LFSR getting stuck at the all 0's state is Fraction Fever for Colecovision. Play it on ColEmDOS. The LFSR is never initialized on startup, and ColEmDOS initalizes all RAM to 000h. As a result, nothing is random, and all the platforms are the same :-).

Archives (includes files) at
Unsub & more at

Current Thread