Random Numbers

[Primordial Ooze]

How do I generate a random number in 6502 assembly language?

 

How would I generate a random number between x and x say 1 to 6?

 

Your help in this matter would be greatly appreciated.

 

Sincerely,

 

Primordial Ooze

[GroovyBee]

How would I generate a random number between x and x say 1 to 6?

 

Is the final number going to be used in lookup tables or for comparisons e.g. AI decisions? How often do you need a new value?

 

I'm pretty sure that there is a random number generator in the 7800's Desert Falcon source code (available on AA or Curt Vendel's site).

[accousticguitar]

I'm not sure how to get a random number, but I do know that once you have the random number you can trim it with the "AND" operator. For example, if you have a random number between 0 and 255 and you want a number between 0 and 7, you can AND the value you have to trim it to a number between 1 and 7.

 

LDA (value)
AND #%00000111

You can do this with 15 (0 to 15), 31 (0 to 31), 63 (0 to 63), and 127 (0 to 127).

 

You can read about it in Atari Roots Chapter 9 under "Boolean logic."

 

http://www.atariarchives.org/roots/

Edited March 8, 2010 by accousticguitar

[+batari]

This topic has been covered extensively, and basically all programmers use a linear feedback shift register (LFSR). You can use an 8-bit LFSR with reasonable results for something line 1-6. Below is code we developed for either an 8 or 16-bit LFSR (the latter uses two bytes shifted different directions and EOR'ed with each other, which achieves excellent results.) To use 8=bit, define a byte called "rand," or to use 16-bit, also define a byte called rand16.

 

Random number is returned in the accumulator.

randomize
       lda rand
       lsr
ifconst rand16
       rol rand16
endif
       bcc noeor
       eor #$B4 
noeor 
       sta rand
ifconst rand16
       eor rand16
endif
       rts

EDIT: The routine above needs to be seeded before it will work. Any initial value for rand and rand16 other than zero will work.

Edited March 8, 2010 by batari

[TROGDOR]

Here's a post that discusses random number generators, and techniques to seed them. I recommend the 16-bit implementation. It's the best trade off between RAM usage, speed, and getting a reasonably random number sequence.

 

It's much easier to generate random numbers that are multiples of 2. To get a number from 1 to 6, you could generate a number from 0 to 7. If the result is 6 or 7, get a new number until you get one that is less than 6. Then add one to the result. The only risk with this technique is that it requires an indeterminate number of cycles, since you don't know how many 6s and 7s you'll generate before you get a usable number. It's better to adjust the game requirements so that only powers of two are needed for random numbers.

Edited March 9, 2010 by TROGDOR

[accousticguitar]

It's coming back to me now. I think I used one of those routines in one of my hacks.

[+batari]

To get a number from 1 to 6, you could generate a number from 0 to 7. If the result is 6 or 7, get a new number until you get one that is less than 6. Then add one to the result. The only risk with this technique is that it requires an indeterminate number of cycles, since you don't know how many 6s and 7s you'll generate before you get a usable number. It's better to adjust the game requirements so that only powers of two are needed for random numbers.

When using a LFSR, the maximum number of cycles is determinate since a LFSR is a sequence of 255 (or 65535) pseudo-random numbers. One could code the LFSR in C or another language and determine the maximum number of tries to get a valid number. It might be reasonable.

 

Another alternative, if the above is not reasonable, is to simply get one random number per frame and only use it if it's within a valid range. It might be perfectly fine for a certain action to be delayed a few frames.

[GroovyBee]

Or use a modulo look up table if you have the ROM space.

[scitari]

I am very close to finishing my first Atari 2600 game in assembly and struggled a bit with finding information about setting random seeds. I have been using INTIM to set the seed right after initialization and am using the LFSR algorithms others have posted and discussed in this forum. I require the powerups and game mechanics to appear to be different each time the player starts the game. This is in contrast to many other games where the LFSR is used to generate the same sequence of events each time using a single random seed. With the INTIM approach I was getting the same seed on start in subsequent games. I found this piece about developing AI approaches to play Atari games and it specifically discusses LFSR approaches and their determinism. It mentions calling the LFSR routine each time a frame is drawn. The result is that a different point in the pseudo random number sequence is used as the seed each time a random number is needed for game play due to player action or inaction. In other words, the player unwittingly sets the seed thus making it appear much more random. I call the LFSR each time through the main loop at the end of the overscan. Works beautifully. I thought I would share this here since I didn't see it mentioned anywhere else. I am sure it is common knowledge among veterans as the article implies. Here is the article if you are interested:

 

https://www.aaai.org/ocs/index.php/WS/AAAIW15/paper/download/9564/10216

Edited December 10, 2017 by scitari

[vidak]

There's a bit of discussion about random number generation on the Stella Mailing List - check out my Commo Dig and ctrl+f the web page with the word "random"

[+SpiceWare]

It mentions calling the LFSR routine each time a frame is drawn.

Yep, I cover that in the Random Numbers entry of my Collect tutorial.

One thing that helps when using an LFSR is to keep reading values at a regular rate, even if you don't need the value. What this does is impose an element outside of the Atari's control - namely the time it takes the human to do things: hit the RESET switch to start a game, collect the next box, etc. I've added this to VerticalBlank

VerticalBlank:
        jsr Random
...