The Developer’s Cry

 Yet another blog by a hobbyist programmer

Fast Pseudo Random Number Generator

Games need a good pseudo random number generator (PRNG). Flipping cards, rolling dice, determining hit points, choosing whether to fire a bullet or not, all these are random choices. Random is a strange phenomenon though. The set of numbers 1,1,1,1 is just as random as 4,2,1,3—even though I carefully hand-picked both sequences, the latter looks more random. A shuffled list of numbers is perceived as being more random than a list of truly random numbers.

It is a well-known fact (or actually, myth) that computers do not do random numbers; instead they are computed and therefore they are predictable. This was true until computer scientists found that real-world noise like typing speed, mouse movement, networking interrupts, and hard drive rotation statistics may be used for entropy: a source for random number generation. This is only a source though and the produced random number sequences may still be predictable depending on the algorithm used. Cryptographically safe RNGs aim to make it impossible to guess the next random number. There is a kind of chicken-and-egg relation here: crypto functions need good RNGs to be able to scramble the input; the scrambled output appears as random as any random data. Therefore the crypto function can be used as a RNG.

Anyway, there are some problems when it comes to games. Fast-paced action games may make hundreds of random choices every frame. At 60 frames per second, we don’t want to take too much time generating random numbers. Therefore cryptographically safe RNGs are off limits, we are going to have to settle with a more predictable PRNG.
Another problem is that at 60 fps, we might quickly drain the entropy pool. We can’t afford having to wait for new entropy, and we don’t want the operating system to run out. So even though modern operating systems can supply fairly truthful random numbers, we are not going to bother and stick with “decent enough” instead; we are going at it old-skool and calculate the pseudo random numbers by ourselves.

PRNG requirements for games:

In them old days, we would use rand() and seed it by calling srand(). rand() is a notoriously bad PRNG and you should not use it nowadays. The BSD man page even calls it “bad random number generator”. It has a low period, meaning that after a while the same prefix starts to repeat. This is a bad habit for a PRNG. I personally have bad experiences with rand(). My Tetris clone would happily generate the same block over and over again, giving some really bad gameplay experiences. I started handing out bonuses for this, but it didn’t make it more fun. The game notably improved when I switched to a different PRNG. The modern, new and improved equivalent of rand() is random(). It should be noted however that there might be a portability issue here; random() may not be available on your platform of choice.

Mersenne Twister

A popular modern PRNG is the Mersenne Twister. It is named after the Mersenne prime number that it uses. It is a well respected PRNG, and an easy choice for C++ programmers, as it is included in the C++11 standard library. The C++11 way to get some random numbers is:

#include <random>

std::random_device rd;     // only used once for seeding
std::mt19937 rng(rd());    // select Mersenne Twister
std::uniform_int_distribution<int> dist(0, 1000);
int n = dist(rng);

The Mersenne Twister is relatively slow for game code. Apparently it badly stresses the CPU cache.

XorShift

The most simple and fastest decent PRNG there is, is the XorShift algorithm. It simply does a couple of bit-shift and exclusive-OR operations, and that’s it. It has four internal state variables that you should initialize (in a more or less random manner, as you see fit).

uint32_t xorshift128(void) {
    // algo taken from wikipedia page
    uint32_t t = state.x ^ (state.x << 11);
    state.x = state.y;
    state.y = state.z;
    state.z = state.w;
    state.w = state.w ^ (state.w >> 19) ^ t ^ (t >> 8);
    return state.w;
}

XorShift is incredibly simple, but good enough for games. In that respect, it is a perfect fit for our purposes. There are XorShift* and XorShift+ variants, that use multiplication and addition respectively, and produce 64 bits values.

Statistical Analysis

In a feeble attempt to prove that XorShift suffices, I calculated the standard deviation for a series of numbers between 0 and 1000 generated by rand(), random(), std::mt19937, and xorshift128(). They all produce a standard deviation around 285, meaning that they all exhibit the same fairly high spread of values. In that sense, we can say that probably they all produce sets of random values usable for games. This is by no means an extensive analysis of the PRNGs, of course. There exists a test suite named TESTU01 for testing PRNGs, but I’ll leave it up to the math and computer scientists to play around with that.

For now, I’m happy to have found that the XorShift PRNG is exceptionally fast, while still producing decently enough pseudo random numbers. It is a perfect fit for games.

Two interesting links for further reading: