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:
RND LDA RNDL
LSR
LSR
SBC RNDL
LSR
ROR RNDH
ROR RNDL
LDA RNDL
RTS
...my 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
rts
randbyte: ldx #7
rb_loop: jsr random
dex
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 :-)
inx
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 http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/