What is a good random number generator for a game?

Question

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.

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];
   }

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, ...)

Mersenne Twister is typical in the industry, especially since it lends itself well to SIMD and can be made super fast. Knuth is popular too (thanks, David).

In most game applications speed is really the critical factor, since players are going to complain about low framerate a lot more than they will complain about the fact that there is a slight bias towards generating a 3 whenever it is preceded by a 7, 2, and 9 in that order.

The exception of course is gambling for money, but there your relevant licensing authority will specifically lay out the algorithms that you can use.

Buy a cheap webcamera, a ionizing smoke detector. Disassemble both of them, smoke detector contain little radioactive material - a source of gamma waves - which will result in firing photons at your webcamera. That's your source of true randomness :)

Mersenne Twister is very good, and it's fast as well. I used it in a game and it's not hard at all to implement or use.

The WELL random algorithm was designed as an improvement over the Mersenne Twister. Game Gems 7 has more info. on it, if you can borrow that or have it.

On that WELL page I linked you to, the number is the period of the algorithm. That is, you can get 2^N - 1 numbers before it needs reseeding, where N is: 512, 1024, 19937, or 44497. Mersenne Twister has a period of N = 19937, or 2^19937 - 1. You'll see this is a very large number :)

The only other thing I can point out is that boost has a random library, which you should find useful.

In response to your edit, yes the Twister or WELL is that much better than rand(). Also, the old modulus trick harms the distribution of the numbers. Even more reason to use boost :)

In a real-time game, there's no way for a player to determine the difference between a "good" generator and a "bad" one. In a turn-based game, you're right--some minority of zealots will complain. They'll even tell you stories, in excruciating detail, of how you ruined their lives with a bad random number generator.

If you need a bunch of genuine random numbers (and you're an online game), you can get some at Random.org. Use them for turn-based games, or as seeds for real-time games.