Page 1 of 2
Random Number Generation?
Posted: Thu Aug 05, 2010 5:41 am
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 (0-F, 0-1, and 0-3) 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?
Posted: Thu Aug 05, 2010 6:29 am
One common method to generate pseudorandom numbers on 8-bit computers is a polynomial counter
. Seed it with the time to get through the menus, then clock it once for 0-1, twice for 0-3, or four times for 0-15. See the source code for LJ65
, Concentration Room
, and Russian Roulette
for an example of a 32-bit Galois LFSR used as a PRNG.
Posted: Thu Aug 05, 2010 7:34 am
I just use this routine, since you can never prove
that it's not random:
Posted: Thu Aug 05, 2010 6:48 pm
Really, to generate a random number start out with a seed value that's semi-random. 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 8-bit 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.
Posted: Thu Aug 05, 2010 7:27 pm
Yeah it's mostly a matter of generating the seed, then use an LFSR that doesn't repeat for long enough. If the seed is zero however, the LFSR will always be stuck at zero.
Posted: Thu Aug 05, 2010 7:38 pm
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.
Posted: Fri Aug 06, 2010 12:11 am
Further to this, any good methods for generating an 8-bit number within a range without doing (too much) multiplication or division (i.e. fast)?
Posted: Fri Aug 06, 2010 2:33 pm
Tokumaru's method seems the least processor intensive, but I need to generate numbers within ranges, specifically, I need to generate 16 individual random binary values. Is there a way to read a single bit of a number stored in hex?
Posted: Fri Aug 06, 2010 3:19 pm
Will make it 0 or 1. You can then beq or bne depending on the condition.
will make it a number between 0 and 15.
Posted: Fri Aug 06, 2010 3:23 pm
Oh, so I can address a hex value as if it were a binary value and it'll work just fine?
That's what I was hoping, but I thought I might have to convert it first.
This is awesome, and makes my life 100 times easier, thanks!
Posted: Fri Aug 06, 2010 3:41 pm
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 power-of-2 range.
Posted: Fri Aug 06, 2010 3:44 pm
Zsy wrote:Oh, so I can address a hex value as if it were a binary value and it'll work just fine?
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.
Posted: Fri Aug 06, 2010 4:00 pm
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.
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.
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 0-255 I'd probably do something like ((upper limit + 1) * 8-bit 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...
Posted: Fri Aug 06, 2010 5:20 pm
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 power-of-two PRNG through a least-recently-used 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.
Posted: Fri Aug 06, 2010 5:33 pm
Edit: Somewhat ninja'd by Tepples.
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 power-of-2 range.
True, but he did specifically ask for something that would give him 16 different values.
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 0-6 in the accumulator
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.