## Random Number Generation?

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Zsy
Posts: 26
Joined: Sun Jul 25, 2010 9:47 am
Location: CT, USA
Contact:

### 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 (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?

tepples
Posts: 22019
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:
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.

blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:
I just use this routine, since you can never prove that it's not random:

Code: Select all

``````random:
lda #9
rts``````

Celius
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 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.

Memblers
Posts: 3863
Joined: Mon Sep 20, 2004 6:04 am
Location: Indianapolis
Contact:
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.

tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil
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.

neilbaldwin
Posts: 481
Joined: Tue Apr 28, 2009 4:12 am
Contact:
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)?

Zsy
Posts: 26
Joined: Sun Jul 25, 2010 9:47 am
Location: CT, USA
Contact:
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?

Kasumi
Posts: 1292
Joined: Wed Apr 02, 2008 2:09 pm
And it.

and #%00000001

Will make it 0 or 1. You can then beq or bne depending on the condition.

and #%00001111

will make it a number between 0 and 15.

Zsy
Posts: 26
Joined: Sun Jul 25, 2010 9:47 am
Location: CT, USA
Contact:
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!

blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:
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.

tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil
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.

tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil
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...

tepples
Posts: 22019
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:
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.

Kasumi
Posts: 1292
Joined: Wed Apr 02, 2008 2:09 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

jsr randomgen
and #%00000111
cmp #\$07
bcc endrandseven

dec incvalue
bpl randseven.nowrap
lda #\$06
sta incvalue
randseven.nowrap:

lda incvalue

endrandseven:
rts``````
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.