This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Random numbers?

Random numbers?
by on (#20522)
Hi, all. Is there a place to pull random integers from? It doesn't look like there's a PRNG chip anywhere and I don't see any register that would have anything near randomness. Thanks in advance.

-- Nitron

by on (#20524)
You have to generate pseudo-random numbers yourself, in software. I believe 6502.org has sample source code for doing this.

by on (#20527)
There's a random # generator in Munchie Attack, source is included here:
http://nesdev.com/Munchie_Attack.zip

It's the random_gen subroutine, returns with the random # in A. You need to get a seed before calling it (put in the random4 variable). The way I get a seed is before the game starts, increment the seed while you wait for the player to press a button.

by on (#20528)
The RNG in munchie attack looks to be an LFSR, though the taps don't look to be quite optimal - it feeds D24 ^ D28 into D0, which repeats after a varying number of iterations.

An optimal 29-bit LFSR repeats after 536,870,911 bits. Depending on the initial value, the Munchie LFSR would repeat after 398,532,477 bits, 132,844,159 bits, or possibly less than 5,494,274 bits for truly suboptimal inputs.

A few minor adjustments would easily transform this LFSR into a 31-bit one of optimal length (2,147,483,647 bits):
Code:
        lda random4     ; random bit generator
        rol             ; written by kevtis
        rol             ; uses user input from joystick for initial values
        rol
        rol
        eor random4     ; this will XOR two bits together and put the answer in bit 7 of the acc
        rol             ; this puts the answer into the carry


Remove 1 ROL from the upper half, and add 3 to the bottom half:
Code:
        lda random4     ; random bit generator
        rol             ; written by kevtis
        rol             ; uses user input from joystick for initial values
        rol
        eor random4     ; this will XOR two bits together
        rol
        rol
        rol             ; and put the answer in bit 7 of the acc
        rol             ; this puts the answer into the carry

by on (#20529)
Tetramino has another example of a (working, tested) 32-bit LFSR-based PRNG.

by on (#20536)
Or else there's this....

randomtbl: .db $33,$f2,$06,$11,$c4,$50


You only need to TELL people that it's random. :wink:

by on (#20542)
The christmas program I posted uses a simple 8-bit linear congruential generator that looks like this:

Code:
lda random_seed
asl
asl
asl
clc
adc random_seed
clc
adc #53
sta random_seed

;random number is now in A


So in math terms it's just r = (r * 9 + 53) mod 256. It could easily be expanded to 16bits or more for better randomness.

Wikipedia on LCG.

by on (#20672)
ccovell wrote:
Or else there's this....

randomtbl: .db $33,$f2,$06,$11,$c4,$50


Yeah, but then you can end up with "Pac-Man pattern" effects.

If you want to be really random, have an ADC read a floating pin. It could get expensive if you want more than 12 bits from the ADC, and you wouldn't be able to do it purely in software. Though you could use it as a seed value for a LFSR or LCG.

by on (#20900)
It's not hard to mix both methods, acessing a table but with partially random increments, so that no pattern appears, and you're sure to place yourself the numbers that will appear from the table (if you want to keep them a certain range or something).

by on (#21753)
Speaking of PRNG, anyone (attemp) Mersenne Twister? or is 2KB too much to ask?

My personal fav is the "hand-trap" rng from mario 3. They use 8 bytes (7 in version 1) or one of the bytes with 2 every now-and then, and shift right, a lot.

by on (#21756)
The NES's 2 KiB of main RAM is not enough memory to hold the 2496 byte state of a Mersenne Twister instance.

Another problem that may affect an implementation's performance even on relatively less constrained platforms such as Game Boy Advance: MT is fast on average, but it works in spurts, which is bad for a real-time program. The reference implementation pauses to generate a block of 624 32-bit random numbers at a time and then spits them out instantly on demand. It should be possible to eliminate this periodic pause using a double buffer and avoid missing deadlines such as vblank, but that would use even more memory. Still, 5 KiB for a PRNG might be worth it on some platforms.

by on (#21768)
That's what I though... I think it was already introduced above, but using the controller data as a seed is probably your best bet. Generally I'd run an incrementing 8-bit counter every vblank. Then when the user presses start, that last value becomes the seed for the rors of doom...sure it gives only 255 initial seed combinations, but for more-or-less simple games this should be fine.

by on (#21876)
You can get way more than 256 seeds too.. or at least different starting points. If you look at the Munchie Attack source, I believe you'll find that my pre-game loop doesn't wait for vblank. It just keeps polling the controller and incrementing the seed. Doing that by vblanks makes it too easy to land in the same range multiple times, I thought.

But, it was convenient to do in that game. Nothing really happens between the title screen and game start except waiting.

by on (#21877)
As I understand it, most PC-based emulators read the controller only once per vblank due to limitations in DirectInput and USB.

by on (#21880)
tepples wrote:
As I understand it, most PC-based emulators read the controller only once per vblank due to limitations in DirectInput and USB.


Which is another reason why I do NES development, and not PC/emulator development, heheh. :)

Also I forgot to mention on my last post, the part about having more than 256 seeds means making the seed several bytes long (or even changing all the persistant RAM used by the RNG). Incrementing/polling really fast makes it possible.

by on (#21882)
Quote:
As I understand it, most PC-based emulators read the controller only once per vblank due to limitations in DirectInput and USB.
]
This would be a good thing to change. They could add a random delay of 0-1/60 second to the time the buttons change state. I should write a test program on the NES and see how authentic this can be.

by on (#21884)
One solution that should give 16 bits' worth of entropy without having to time things faster than vblank: Require one press of Start to close the title screen and another to acknowledge the menu. Timing the press, release, press, and release, should end up with at least 7 good bits from the press, 2 from the release, 5 from the next press, and 2 from the release.