Implementing a (pseudo) random number generator

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

AWJ
Posts: 433
Joined: Mon Nov 10, 2008 3:09 pm

Re: Implementing a (pseudo) random number generator

Post by AWJ »

rainwarrior wrote:
AWJ wrote:If two of the same enemy are in the same RNG-tapping state on the same frame then they'll always both choose the same behaviour
I've seen that in several games, and I've always thought of it as a serious flaw, not something people hardly notice. :P I've often been annoyed at how unintentionally predictable RPG battles can become.
The concerns in an action game are totally different from those in an RPG. You might have noticed that all the games I've complained about poor quality PRNGs in are RPGs (the Dragon Quests are the only NES/SNES RPGs I know of that have particularly good PRNGs; Square's are universally terrible)

In an action game you're generally consuming less than one random number per frame on average (enemies generally don't choose a new action every frame, only when they finish their current one) and you want to avoid spikes in CPU usage, especially if you're doing a sprite 0 raster split.
Sometimes you don't realize why something plays out kinda crummy, and it's really just from poor PRNG use, but you can't tell because you're not comparing against a good PRNG.
Yep, in an RPG unwanted correlation between successive random numbers (e.g. hit rolls and damage rolls) can badly distort game balance. Another example to go with those DBZ cards: stat growth in Final Fantasy 2. You weren't supposed to lose a point in Intelligence almost every time you gained one in Strength and vice versa, it was supposed to be more like a 1/6 chance, but lolSquareRNG. There are a whole bunch of monsters in Romancing SaGa 3 that simply never appear due to lolSquareRNG, and at least one item that's unobtainable as a consequence.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Implementing a (pseudo) random number generator

Post by Oziphantom »

in a side note, if you are looking for "fast" 8bit,16bit PRNG with full range there are some documented here http://codebase64.org/doku.php?id=base:6502_6510_maths although you might need to do something like counter till the user presses a button to substitute for any use of the SID's LFSR.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Implementing a (pseudo) random number generator

Post by rainwarrior »

AWJ wrote:The concerns in an action game are totally different from those in an RPG.
I was not contrasting action games with RPGs. I was mentioning them because their PRNGs are often on very prominent display so they can show up bad behaviour in very obvious ways, so they're a good example. Action games have the same PRNG problems, just are usually more obtuse to understand.
AWJ wrote:In an action game you're generally consuming less than one random number per frame on average
...which is why optimizing you PRNG isn't normally a useful gain, not at the expense of number quality.
AWJ wrote:You want to avoid spikes in CPU usage, especially if you're doing a sprite 0 raster split.
Missing a raster split is a very specific problem with very specific conditions, and PRNGs are hardly the only source of variable timing. (...and IRQs make it irrelevant.) I think it's bad to throw away PRNG quality in the name of speed before they're identified as a performance problem. There's always specific examples where it is worth it, but the case I'm making is that you shouldn't start with it.

It's very easy to make them faster and lower-quality later on, but it's really hard to do the opposite, and for similar reasons its much harder to realize what the negative consequences of low-quality PRNG are when you haven't been using the higher quality version by default.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Implementing a (pseudo) random number generator

Post by FrankenGraphics »

An (unpragmatical) alternative is to etch a PCB with a thermal or avalanche noise generator onboard. That way you would get True RNG, which is especially more suitable for lotteries, gambling, security, and is nondeterministic. The need for TRNG in a game of entertaining value is debatable, but you could also get another noise audio source out of i and the routine for sampling the noise would be very fast. Oh, and that would pretty much rule out emulators. Just thought i should add the alternative for the sake of completeness.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Implementing a (pseudo) random number generator

Post by Dwedit »

Nintendo DS has a microphone, which could be an excellent source of entropy, but Pokemon games on the DS still managed to only care about the clock's second at boot time. Then there's the infamous Deal or No Deal where they completely forgot to randomize anything at all, making the top prize always in the same exact briefcase.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
zeroone
Posts: 939
Joined: Mon Dec 29, 2014 1:46 pm
Location: New York, NY
Contact:

Re: Implementing a (pseudo) random number generator

Post by zeroone »

Details on the PRNG used in Nintendo Tetris: http://meatfighter.com/nintendotetrisai ... Tetriminos
User avatar
Zutano
Posts: 38
Joined: Tue Apr 04, 2017 1:22 pm
Location: Ohio, USA
Contact:

Re: Implementing a (pseudo) random number generator

Post by Zutano »

Is there a way to access the value in the NES APU's noise channel directly to get random numbers?
http://zutanogames.com/ <-- my dev blog
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Implementing a (pseudo) random number generator

Post by Dwedit »

No, you can't read the noise value. But a LFSR (linear feedback shift register) is the same algorithm that the noise channel uses.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
Post Reply