From "Game Coding Complete" by Mike McShaffry.
An Excellent Random Number Generator
There are as many good algorithms for generating random numbers as
there are pages in this book. Most programmers will soon discover
that the ANSI rand() function is completely inadequate because it
can only generate a single stream of random numbers. In any game
I've ever created multiple discrete streams of random numbers were
required.
Unless your game comes with a little piece of hardware that uses
the radioactive decay of cesium to generate random numbers, your
random number generator is only pseudorandom. A pseudo-random
number sequence can certainly appear random, achieving a relatively
flat distribution curve over the generation of billions of numbers
mapped to a small domain. Given the same starting assumption,
commonly called a seed, the sequence will be exactly the same. A
truly random sequence could never repeat like that.
This might seem bad because you might feel that a hacker could
manipulate the seed to effect the outcome of the game. In practice,
all you have to do is regenerate the seed every now and then using
some random element that would be difficult or impossible to
duplicate. In truth, a completely predictable random number
generator is something you will give your left leg for when writing
test tools or a game replay system.
A Tale from the Pixel Mines
Every Ultima from Ultima I to Ultima VIII used the same random
number generator, originally written in 6502 assembler. In 1997
this generator was the oldest piece of continually used code at
Origin Systems. Finally this RNG showed its age and had to be
replaced. Kudos to Richard Garriott (aka Lord British) for making
the longest-lived piece of code Origin ever used.
Here's a cool little class to keep track of your random numbers.
You'll want to make sure you save this code and stuff it into your
own toolbox. The RNG core is called a Mersenne Twister pseudorandom
number generator and it was originally developed by Takuji
Nishimura and Makoto Matsumoto:
/* Period parameters */
#define CMATH_N 624
#define CMATH_M 397
#define CMATH_MATRIX_A 0x9908b0df /* constant vector a */
#define CMATH_UPPER_MASK 0x80000000 /* most significant w-r bits
*/
#define CMATH_LOWER_MASK 0x7fffffff /* least significant r bits
*/
/* Tempering parameters */
#define CMATH_TEMPERING_MASK_B 0x9d2c5680
#define CMATH_TEMPERING_MASK_C 0xefc60000
#define CMATH_TEMPERING_SHIFT_U(y) (y >> 11)
#define CMATH_TEMPERING_SHIFT_S(y) (y << 7)
#define CMATH_TEMPERING_SHIFT_T(y) (y << 15)
#define CMATH_TEMPERING_SHIFT_L(y) (y >> 18)
class CRandom {
// DATA
unsigned
int
rseed;
unsigned long
mt[CMATH_N]; /* the array for
the state vector */
int
mti;
/* mti==N+1 means mt[N] is not initialized */
// FUNCTIONS
public:
CRandom(void);
unsigned int Random( unsigned
int n );
void SetRandomSeed(unsigned int n);
unsigned int
GetRandomSeed(void);
void Randomize(void);
};
CRandom::CRandom(void)
{
rseed = 1;
mti=CMATH_N+1;
}
// Returns a number from 0 to n (excluding n)
unsigned int CRandom::Random( unsigned int n )
{
unsigned long y;
static unsigned long mag01[2]={0x0,
CMATH_MATRIX_A};
if(n==0)
return(0);
/* mag01[x] = x * MATRIX_A for x=0,1 */
if (mti >= CMATH_N) { /* generate N words at
one time */
int kk;
if (mti ==
CMATH_N+1) /* if sgenrand() has not been called,
*/
SetRandomSeed(4357); /* a default initial seed is used
*/
for
(kk=0;kk<CMATH_N-CMATH_M;kk++) {
y =
(mt[kk]&CMATH_UPPER_MASK)|(mt[kk+1]&CMATH_LOWER_MASK);
mt[kk] = mt[kk+CMATH_M] ^ (y >> 1) ^ mag01[y &
0x1];
}
for
(;kk<CMATH_N-l;kk++) {
y =
(mt[kk]&CMATH_UPPER_MASK)|(mt[kk+1]&CMATH_LOWER_MASK);
mt[kk] = mt[kk+(CMATH_M-CMATH_N)] ^ (y >> 1) ^ mag01[y &
0x1];
}
y =
(mt[CMATH_N-1]&CMATH_UPPER_MASK)|(mt[0]&CMATH_LOWER_MASK);
mt[CMATH_N-1] =
mt[CMATH_M-1] ^ (y >> 1) ^ mag01[y & 0x1];
mti = 0;
}
y = mt[mti++];
y ^= CMATH_TEMPERING_SHIFT_U(y);
y ^= CMATH_TEMPERING_SHIFT_S(y) &
CMATH_TEMPERING_MASK_B;
y ^= CMATH_TEMPERING_SHIFT_T(y) &
CMATH_TEMPERING_MASK_C;
y ^= CMATH_TEMPERING_SHIFT_L(y);
return (y%n);
}
void CRandom::SetRandomSeed(unsigned int n)
{
/* setting initial seeds to mt[N]
using */
/* the generator Line 25 of Table 1
in */
/* [KNUTH 1981, The Art of Computer Programming
*/
/* Vol. 2 (2nd Ed.),
pp102]
*/
mt[0]= n & 0xffffffff;
for (mti=1; mti<CMATH_N; mti++)
mt[mti] = (69069 * mt[mti-1]) &
0xffffffff;
rseed = n;
}
unsigned int CRandom::GetRandomSeed(void)
{
return(rseed);
}
void CRandom::Randomize(void)
{
SetRandomSeed(time(NULL));
}
The original code has been modified to include a few useful bits,
one of which was to allow this class to save and reload its random
number seed, which can be used to replay random number sequences by
simply storing the seed. Here's an example of how to you can use
the class:
CRandom r;
r.Randomize();
unsigned int num = r.Random(100); // returns a number from
0-99, inclusive
You should use a few instantiations of this class in your game,
each one generating random numbers for a different part of your
game. Here's why: Let's say you want to generate some random taunts
from AI characters. If you use a different random number sequence
from the sequence that generates the contents of treasure chests,
you can be sure that if the player turns off character audio the
same RNG sequence will result for the treasure chests, which nicely
compartmentalizes your game. In other words, your game becomes
predictable, and testable.
A Tale from the Pixel Mines
I was working on an automation system for some Microsoft games, and
the thing would just not work right. The goal of the system was to
be able to record game sessions and play them back. The system was
great for testers and programmers alike. It's hard to play a few
million hands of blackjack. Every day. Our programming team
realized that since the same RNG was being called for every system
of the game, small aberrations would begin to result as calls to
the RNG would begin to go out of sync. This was especially true for
random character audio, since the timing of character audio was
completely dependant on another thread, which was impossible to
synchronize. When we used one CRandom class for each subsystem of
the game, the problem disappeared.