nesdev.org

When I program an NES game and need a randomizer, which function is usually used for it?

I had a look into Visual C++ 6.0 and the functions there basically look like this: I assume this isn't really an ideal way for an NES game with the multiplication and the long values.

So, what does the typical NES randomizer look like?

The C code you quoted is a linear congruential generator, which depends on fast 32-bit multiplication.

On the 6502, a "typical" randomizer looks like Greg Cook's table-free implementation of CRC16. Initialize it with something nonzero, then just feed it a zero whenever you want a random number.

Examples of other random number generators can be found on codebase64 (personally, I use White Flame's 8 and 16-bit routines)

I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).

Most of the code samples in freem's link are forms of a Galois LFSR. There are other efficient ways to make random numbers on the NES, but this is a pretty practical method.

Some stuff I could find in older threads:
- A 16-bit galois LFSR I suggested to improve shiru's C library: viewtopic.php?p=130725#p130725
- Another previous thread: viewtopic.php?f=10&t=11241

rainwarrior wrote:I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).

The CRC16 that I linked above is an LFSR that generates 8 bits per call, as opposed to 1 with a naive LFSR implementation.

Is it really an LFSR clocked 8 times? I'd be interested in knowing how this was arrived at. Could you describe the underlying LFSR that it implements? It's a bit beyond me to try and decompose 8 LFSR steps from the steps in this code.

Been looking at this CRC16 algorithm posted by tepples, and it seems a bit curious. It has two dead spots (0, 61471), and two periods of length 32767 (lowest values: 1, 3).

Is there some reason that it can't have a full period of 65535? Why is it split in two? Is it standard for a CRC to sacrifice 1 bit of sequence length for error checking? This design goal seems somewhat contrary to the goals of a PRNG. With some understanding of how it works, would it be possible to modify the algorithm for a period of 65535?

Alternative possibility is that my implementation was incorrect, so it is attached for review.



Edit: Python scripts were later disallowed on this forum. Uploading a ZIP with what I think was the original script.

Okay, apparently decomposing it was not as tricky as I had thought. The algorithm is equivalent to 8 ticks of the following Galois LFSR:

tepples wrote:On the 6502, a "typical" randomizer looks like Greg Cook's table-free implementation of CRC16. Initialize it with something nonzero, then just feed it a zero whenever you want a random number.

I'm a bit confused: Why is CRC, i.e. hash values, used for randomization?

freem wrote:Examples of other random number generators can be found on codebase64 (personally, I use White Flame's 8 and 16-bit routines)

Thanks. I'll have a look at them.

rainwarrior wrote:I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).

Yeah, 255 is probably a bit low.

By the way, is there an "official" randomizer for NES games that many companies used? For example, did Nintendo, Konami or Capcom use one specific randomizer for their games or did it change from game to game?

rainwarrior wrote:Been looking at this CRC16 algorithm posted by tepples, and it seems a bit curious. It has two dead spots (0, 61471), and two periods of length 32767 (lowest values: 1, 3).

About a month ago, I suspected that something like this was true when I found that the CRC-16-CCITT polynomial was not in a list of maximal-length polynomials. Ever since, I've been using the 0xb400 polynomial for my 16-bit right shifted Galois LFSR to complement my 32-bit 0xa3000000 LFSR. Thank you for confirming that suspicion.

So, just for comparison. Here's a simple 16-bit LFSR, using $002D for the feedback. This is the lowest 16-bit polynomial with maximal sequence length (65535). So, with this naive approach, 5 bits at a time is comparable in speed/size to that CRC16 (62 cycles, 36 bytes). It would only have 5 bits of entropy, but it does have maximum sequence length (and leaves X/Y registers intact). If you typically need less than 6 bits at a time (e.g. you need random numbers in the range of 0-31), I think I'd recommend against using CRC16. Also you could create 8 entry points for the 1-bit lfsr, allowing you to specify the number of bits as needed on a case-per-case basis, allowing you to save cycles where you need fewer bits. It might be possible to make something that does 8 bits at once like Greg Cook's CRC16 algorithm, but I don't know how he constructed it. If it were adapted for a maximal-length polynomial, would it have the same efficiency, or require more code? I kind of suspect it's not a generic process, and that $1021 had to be hand-picked to be constructible in a low number of cycles.

DRW wrote:I'm a bit confused: Why is CRC, i.e. hash values, used for randomization?

Hashing and a PRNG have similar goals: try to produce a "random" state from the previous state. Hashes want to avoid clustering similar results (things should be spread out evenly to avoid collisions), so this is very similar to the idea of a PRNG that is trying to produce a number very different from the last one.

Tepples wasn't saying that people use CRC code specifically as PRNGs, just that the common LFSR PRNG algorithms are very similar calculations to a CRC.

DRW wrote:By the way, is there an "official" randomizer for NES games that many companies used? For example, did Nintendo, Konami or Capcom use one specific randomizer for their games or did it change from game to game?

I've never seen the same one twice in an NES game, but I haven't done any kind of extensive survey. I think if you went through games by one company you'd probably find a copy-pasted PRNG now and then. Not all games even require a PRNG, and very often it's practical to have more than one.

rainwarrior wrote:It might be possible to make something that does 8 bits at once like Greg Cook's CRC16 algorithm, but I don't know how he constructed it. If it were adapted for a maximal-length polynomial, would it have the same efficiency, or require more code? I kind of suspect it's not a generic process, and that $1021 had to be hand-picked to be constructible in a low number of cycles.

I did it for a 32-bit LFSR, but I'm not certain the process I used will help make an optimized 16-bit one.

here's 8 ticks of the $002D LFSR at once as a multiply and XOR. ($2D = %101101, so this is 4 operations of shift + XOR). This runs in constant time, but average time is almost the same as the .repeat version (also requires one byte of temporary storage? X in this example). Compared to the other version, it can't be broken down by number of bits needed like I suggested, though, so I think this way is inferior, at least. This is optimizing only the 8-bits case at the expense of cases requiring less. (Warning: this code is untested and could have errors, but I was only investigating how many cycles it should take. If this is incorrect, a correct version should be comparable.)

Actually, now that I've compared this I can see where Cook's CRC16 gets its added efficiency from. If I eliminated one of the taps here, I could probably cut ~25 cycles (putting it a lot closer to the CRC16 algorithm), but I'd also be losing maximal length at the same time (just like CRC16 does).

So, really, making an LFSR efficient for 8 bits at once is probably mostly a matter of finding a polynomial that will minimize the number of shifts required. There's probably some extra optimization hiding in Cook's method versus my naive multiply and XOR, but it's a bit minor compared to what it picks up by sacrificing sequence length.

Since I don't know much about the various details of the random number generator, which one shall I use now?

I would prefer a simple and fast algorithm. Seed value, a nice little calculation, that's it. It should of course work on 16 bits so that it doesn't already repeat after 256 calls. But other than that, it doesn't need to be specifically advanced.

I could just pick one of the various generators listed. Choosing a "random" one, so to say. But I'd like to have a "reason" to pick a specific one. Some established, "official" algorithm would be best.
Do you know which one I could take?
For example, is there an official implementation from an old 6502 library or does the implementation of the RND command from BASIC work for the NES? Or does the original C library have a rand function that doesn't use multiplication and division?

Something like that. Simple in its implementation, but with a touch of "officialness". Not just a "random" algorithm written by anybody and published on some private homepage.