How did NES games generate random numbers?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
Marscaleb
Posts: 240
Joined: Fri Sep 11, 2015 10:39 am
Contact:

How did NES games generate random numbers?

Post by Marscaleb »

What were some common ways that NES games generated their random variables?
I saw a cool video that explained the RNG in Super Mario World, and it was fascinating to see the way that it worked there. I'm really curious how it was done in other games, especially for NES games where calculations had to be even more simplistic.
What were viable methods? Did any games use a pre-set table of random values?
User avatar
koitsu
Posts: 4201
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: How did NES games generate random numbers?

Post by koitsu »

https://wiki.nesdev.com/w/index.php/Ran ... _generator has material here, including references which discuss several methods. One that may not be discussed there, and is generally shunned but is used in several games, is to use a value in RAM at power-on/reset (i.e. programmers felt this provided "some degree of randomness" given SRAM decay and the like, though it is generally a faulty design).
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How did NES games generate random numbers?

Post by rainwarrior »

I don't think that's shunned? It shouldn't be used as the only method to gather entropy for a starting seed, mostly because emulators tend to have deterministic startup RAM, but it is certainly a useful one.

Also a lot of that list of games is uninitialized RAM bugs which is an entirely different topic than deliberately using it for random seed entropy. (You can intialize RAM after using it to gather entropy, too, by the way.)

Also also, gathering entropy for a starting seed is a completely separate thing than generating a random number once you have that seed. You can use any seed generating method with any PRNG method, more or less.
User avatar
koitsu
Posts: 4201
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: How did NES games generate random numbers?

Post by koitsu »

I'll rephrase: using a byte/word from somewhere in RAM on power-on (determining reset vs. power-on is often done) as your sole form of entropy is shunned.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How did NES games generate random numbers?

Post by rainwarrior »

On the subject of gathering entropy, there is a thread linked at the start of that article, though the beginning of the thread starts off incredibly obtuse, eventually blargg laid out a good summary of available techniques:
viewtopic.php?p=107596#p107596
blargg wrote:* Initial RAM contents
* Initial timing of things (how many cycles until first event)
* Indeterminate hardware behavior (double write to $2007)

If you have battery RAM, keep RNG's state in it or even just a reset counter, then no need for HW randomness
The first and third option there generally aren't viable on an emulator, though, but you can combine techniques to get better entropy on hardware than you can on an emulator.

And if "entropy" is jargon, it's just a vague measure of how random the result really is. If the result is less predictable, you have more entropy.
User avatar
koitsu
Posts: 4201
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: How did NES games generate random numbers?

Post by koitsu »

An additional entropy source I've read about here on the forum -- and which falls under blargg's second bullet point -- is counting how many NMIs/VBlanks have gone by from the when NMI-on-VBlank is enabled (or roughly RESET) until the time the player presses the first joypad button (presumably Start to start the game). I always thought that one was clever as well as easy to implement.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: How did NES games generate random numbers?

Post by Dwedit »

How *did* NES games generate random numbers? They generally did NOT use power on state for entropy, and if they did, they just used memory as the seed without initializing it first.

The Dragon Warrior games used a RNG in the style of a linear-feedback shift register. Bits shift out, XORs at various points, bits shift in. When it wants a random byte, it just calls it 8 times.
Dragon Warrior 4 added in a CPU cycle counter, so when processing for the frame is complete, it will repeatedly increment the RNG until vblank happens. This makes it highly chaotic, and also breaks some of the guarantees that LFSRs provide about total period.

Repeatedly calling the RNG while waiting for the next frame is fairly common, most of the Konami games will do math on the RNG during idle time.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
Post Reply