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?

Post by Zsy » 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?

tepples
Posts: 21973
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » 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.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Thu Aug 05, 2010 7:34 am

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:

Post by Celius » 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.

User avatar
Memblers
Site Admin
Posts: 3832
Joined: Mon Sep 20, 2004 6:04 am
Location: Indianapolis
Contact:

Post by Memblers » 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.

User avatar
tokumaru
Posts: 11692
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru » 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.

User avatar
neilbaldwin
Posts: 481
Joined: Tue Apr 28, 2009 4:12 am
Contact:

Post by neilbaldwin » 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)?

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

Post by Zsy » 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?

User avatar
Kasumi
Posts: 1292
Joined: Wed Apr 02, 2008 2:09 pm

Post by Kasumi » Fri Aug 06, 2010 3:19 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:

Post by Zsy » 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!

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » 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.

User avatar
tokumaru
Posts: 11692
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru » 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.

User avatar
tokumaru
Posts: 11692
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru » 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...

tepples
Posts: 21973
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » 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.

User avatar
Kasumi
Posts: 1292
Joined: Wed Apr 02, 2008 2:09 pm

Post by Kasumi » 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

 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.

Post Reply