This is the last in of a three part series on game programming. This article picks up where More Coding Tidbits and Style That Saved My Butt left off. Go to Coding Tidbits and Style That Saved My Butt to start the series.

Before we leave this topic I wanted to arm you with some lifesaving snippets of code. Some code defies classification. It gets thrown into a toolbox with all the other interesting things that simply won't die. I try to dust them off and use them on every project and I'm never disappointed. I'll start with a great random number generator, show you a template class you can't live without, and end with a neat algorithm to traverse any set in random order without visiting the same member twice.

#### 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 pseudo-random. 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.

Tales 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-1;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.

Tales 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. |