It is currently Tue Jul 23, 2019 2:04 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Fri Jun 14, 2019 4:24 pm 
Offline
User avatar

Joined: Fri Sep 11, 2015 10:39 am
Posts: 163
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?


Top
 Profile  
 
PostPosted: Fri Jun 14, 2019 5:15 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 4156
Location: A world gone mad
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).


Top
 Profile  
 
PostPosted: Fri Jun 14, 2019 5:24 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7528
Location: Canada
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.


Top
 Profile  
 
PostPosted: Fri Jun 14, 2019 5:45 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 4156
Location: A world gone mad
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.


Top
 Profile  
 
PostPosted: Fri Jun 14, 2019 9:27 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7528
Location: Canada
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:
http://forums.nesdev.com/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.


Top
 Profile  
 
PostPosted: Fri Jun 14, 2019 11:14 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 4156
Location: A world gone mad
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.


Top
 Profile  
 
PostPosted: Sat Jun 15, 2019 12:03 pm 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4192
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!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group