What is a good random number generator for a game?

Solution 1:

Sometimes game developers don't want true randomness and a shuffle bag is more appropriate.

If you do want randomness, the Mersenne twister satisfies your requirements. It is fast, statistically random, has a long period and there are plenty of implementations out there.

Edit: rand() is typically implemented as a linear congruential generator. It's probably best if you make an informed choice of whether or not it's good enough for your purposes.

Solution 2:

There are much better choices than Mersenne Twister nowadays. Here is a RNG called WELL512, designed by the designers of Mersenne, developed 10 years later, and an all around better choice for games. The code is put in the public domain by Dr. Chris Lomont. He claims this implementation is 40% faster than Mersenne, does not suffer from poor diffusion and trapping when the state contains many 0 bits, and is clearly a lot simpler code. It has a period of 2^512; a PC takes over 10^100 years to cycle through the states, so it is large enough.

Here is a paper overviewing PRNGs where I found the WELL512 implementation. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

So - faster, simpler, created by the same designers 10 years later, and produces better numbers than Mersenne. How can you go wrong? :)

UPDATE (11-18-14): Fixed error (changed 0xDA442D20UL to 0xDA442D24UL, as described in the paper linked above).

/* initialize state to random bits */
static unsigned long state[16];
/* init should also reset this to 0 */
static unsigned int index = 0;
/* return 32 bit random number */
unsigned long WELLRNG512(void)
   {
   unsigned long a, b, c, d;
   a = state[index];
   c = state[(index+13)&15];
   b = a^c^(a<<16)^(c<<15);
   c = state[(index+9)&15];
   c ^= (c>>11);
   a = state[index] = b^c;
   d = a^((a<<5)&0xDA442D24UL);
   index = (index + 15)&15;
   a = state[index];
   state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
   return state[index];
   }

Solution 3:

George Marsaglia has developed some of the best and fastest RNGs currently available Multiply-with-carry being a notable one for a uniform distribution.

=== Update 2018-09-12 ===

For my own work I'm now using Xoshiro256**, which is a sort of evolution/update on Marsaglia's XorShift.

=== Update 2021-02-23 ===

In .NET 6 (currently in preview) the implementation of System.Random has been changed to use xoshiro256**, but only for the parameterless constructor. The constructor that takes a seed uses the old PRNG in order to maintain backwards compatibility. For more info see Improve Random (performance, APIs, ...)