Random Number Generation?
Moderator: Moderators
Random Number Generation?
Hello again, I hate to ask so many questions, but I can't find any info on this elsewhere.
Does anyone know of a way to generate random numbers on the NES?
I have to generate random numbers between a few different ranges (0F, 01, and 03) and was wondering if anyone knew how.
I believe that in some other lower level languages this can be done by reading an address that changes faster than the system can accurately read it, thus providing mixed results. That would then give a single random bit that could be added to other random bits to create a larger range. Is there any method like this for the NES?
Does anyone know of a way to generate random numbers on the NES?
I have to generate random numbers between a few different ranges (0F, 01, and 03) and was wondering if anyone knew how.
I believe that in some other lower level languages this can be done by reading an address that changes faster than the system can accurately read it, thus providing mixed results. That would then give a single random bit that could be added to other random bits to create a larger range. Is there any method like this for the NES?
One common method to generate pseudorandom numbers on 8bit computers is a polynomial counter. Seed it with the time to get through the menus, then clock it once for 01, twice for 03, or four times for 015. See the source code for LJ65, Concentration Room, and Russian Roulette for an example of a 32bit Galois LFSR used as a PRNG.
I just use this routine, since you can never prove that it's not random:
Code: Select all
random:
lda #9
rts

 Posts: 2157
 Joined: Sun Jun 05, 2005 2:04 pm
 Location: Minneapolis, Minnesota, United States
 Contact:
Really, to generate a random number start out with a seed value that's semirandom. I usually have the player press Start or something at the beginning of the game some time, and that usually comes before I need to use the random number generator. I just take the amount of time it takes the player to press start in frames and use that as the seed value. It's almost impossible to get it to have the exact same value. Then you take that value, shift it, eor it with the VBLCount (an 8bit variable increasing by 1 every frame), subtract 5 from it, add it to some other variable, etc. Then you save that value as the seed for the next time you use the routine. You basically mutilate the seed value by performing calculations on it with a bunch of variables, and the end result is usually pretty random.
I use a simple, small routine like the one described in this page.
To increase randomness across frames, I call this routine several times while waiting for the NMI in order to advance a "random" amount of numbers in the sequence.
To increase randomness across frames, I call this routine several times while waiting for the NMI in order to advance a "random" amount of numbers in the sequence.
 neilbaldwin
 Posts: 481
 Joined: Tue Apr 28, 2009 4:12 am
 Contact:
Internally, all computers store numbers in binary. Hex is just a (usually) more convenient way for programmers to visualize that data. But you can still easily manipulate the individual bits. Several 6502 instructions can be used for manipulating bits (AND, ORA, EOR, ROL, ROR, ASL, LSR, and so on). In your ASM code, just like you use "$" to represent hex values you can use "%" to represent binary numbers.Zsy wrote:Oh, so I can address a hex value as if it were a binary value and it'll work just fine?
So far I never needed uniformly distributed random numbers in a range that wasn't a power of 2, so I just truncate the numbers in the easiest possible way that will make it fit in the range I want.blargg wrote:Kasumi, that only works if you need a range that's a power of 2. It's more involved if you need another range, especially if it needs to be uniformly distributed.
I can't think of a way to uniformly distribute random numbers in arbitrary ranges that doesn't involve at least a multiplication. For a maximum range of 0255 I'd probably do something like ((upper limit + 1) * 8bit random number) / 256. The division would be accomplished by simply ignoring the lower bits of the multiplication result. But now that I think of it, it wouldn't be very uniform... because of rounding some numbers would be selected twice...
One thing you can do, and which is done in four projects of mine (LJ65 for NES, FK Convey for PC, Lockjaw for PC/GBA/DS, and something unreleased for NES), is feed the poweroftwo PRNG through a leastrecentlyused queue. Put the numbers in a queue, select one of the members at the front of the queue at random, and rotate it to the back of the queue. This also avoids generating the same number several times in a row, if your game rules consider repetition to be a problem.
Edit: Somewhat ninja'd by Tepples.
If you want something that gives you a different range you could try the method Tepples uses for his Tetris randomizer which I think is pretty clever. (At least, I think. I haven't checked the source code, but he described it this way once, I believe)
Seven pieces. He used 3 bits. Seven of the possibilities deal the piece it corresponds to. (1= I, 2 = O, etc.) When the eighth possibility comes up he increments (or decrements) and wraps around a variable and deals the piece that corresponds to the current value of the variable.
Something like this:
This could work even if say one needed 12 values out of 16. Just change the and to add another bit as 1, and change the cmp. The downside is that if you get multiple numbers greater than or equal to the cmp value in a row, they'll be decremented by one which isn't very random. But I'd probably cut my losses at that point. To combat this you could use a variable for each of the extra numbers, or I could try to design something else.
edit: or you could use a queue as described by Tepples above.
True, but he did specifically ask for something that would give him 16 different values.blargg wrote:Kasumi, that only works if you need a range that's a power of 2. It's more involved if you need another range, especially if it needs to be uniformly distributed. Maybe you can adjust your algorithm so that it works for values in a powerof2 range.
If you want something that gives you a different range you could try the method Tepples uses for his Tetris randomizer which I think is pretty clever. (At least, I think. I haven't checked the source code, but he described it this way once, I believe)
Seven pieces. He used 3 bits. Seven of the possibilities deal the piece it corresponds to. (1= I, 2 = O, etc.) When the eighth possibility comes up he increments (or decrements) and wraps around a variable and deals the piece that corresponds to the current value of the variable.
Something like this:
Code: Select all
Randseven:This routine will end with a random number 06 in the accumulator
jsr randomgen
and #%00000111
cmp #$07
bcc endrandseven
dec incvalue
bpl randseven.nowrap
lda #$06
sta incvalue
randseven.nowrap:
lda incvalue
endrandseven:
rts
edit: or you could use a queue as described by Tepples above.