This page is a mirror of Tepples' nesdev forum mirror (URL TBD).

# random number

I was thinking of ways to generate random numbers...

So far, I've just been used a frame counter and some bit shifting and adding. I think I can come up with a method of random number generation...

But, for a future project, I don't really want " random " because a truly random sequence could have the same number come up several times in a row, what I really want is "mixed", but not in a repetitive way.

I could use a random number algorithm, but make sure that the number is different from the last number.

Any thoughts?
One way to get a number different from the last number is to simply try again if you got the last number.
Or you could do the randomized array method, basically like shuffling a deck of cards.
for (int i = 0; i < SIZE; i++)
{
_ _ int i2 = Random number that is >= i and < SIZE
_ _ arr.swap(i, i2)
}
Quote:
randomized array

I think I might use this to some degree, and use a frame count at "user presses start" to initialize the seed.
It's worth pointing out that LFSRs always emit a unique sequence, and once you see the same number repeat, all subsequent numbers repeat too.

This is how Pitfall for the 2600 worked: it actually represented the level as an 8-bit LFSR that could be clocked both forwards and backwards, so it could get the "next" and "previous" screen trivially from the current screen. And it's completely deterministic.
What I typically use is a least recently used queue. First I fill an array with numbers 0 to max-1. Then I choose an index r from 0 to depth-1, where depth < max, move elements at indices r+1 through max-1 down 1 position, and put the value that was at index r at the end. One tweak is to arrange the initial values to have more copies of a particular value that you want more often, or to move values that shouldn't be seen at the very start toward the end of the initial list.

I've used this in RHDE (for choosing wall pieces), my port of robotfindskitten (for choosing NKI descriptions), Thwaite (for choosing target buildings), and a previous puzzle game (for choosing pieces).
How about a 16 bit LFSR algorithm...still deterministic, but with 65,536 unique results, should seem random.
If you just want to cycle through a given set of numbers, you can just add a relatively prime number and modulo to keep it in range, and this will cycle through each number.

e.g. modulo 8:

1. x = 0
2. x = (0 + 3) % 8 = 3
3. x = (3 + 3) % 8 = 6
4. x = (6 + 3) % 8 = 1
etc.

As long as the number you are adding by each time is relatively prime to the modulo (i.e. they have no common factors), it will always cycle through all of them.

You could keep a table of relatively numbers to use and change it every time you hit zero. For example, mod 8 has the following options: 1,3,5,7.