Mike s Grab Bag of Useful Stuff
Mike's Grab Bag of Useful Stuff
Before we leave this chapter 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 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. |
Supporting Optional Variables with Optional<T>
A really favorite template of mine is one that encapsulates optional variables. Every variable stores values, but they don't store whether the current value is valid. Optional variables store this information to indicate if the variable is valid or initialized. Think about it, how many times have you had to use a special return value to signify some kind of error case?
Take a look at this code, and you'll see what I'm talking about:
bool DumbCalculate(int &spline) { // imagine some code here.... // // The return value is the error, and the value of spline is invalid return false; } #define ERROR_IN_DUMBCALCULATE (-8675309) int DumbCalculate2() { // imagine some code here.... // // The return value is a "special" value, we hope could never be actually // calculated return ERROR_IN_DUMBCALCULATE; } int _tmain(void) { ////////////////////////////////////////////////////////////////////////////// // Dumb way #1 - use a return error code, and a reference to get to your data. // int umbAnswer1; if (DumbCalculate1(dumbAnswer1)) { // do my business... } ////////////////////////////////////////////////////////////////////////////// // Dumb way #2 - use a "special" return value to signify an error int dumbAnswer2 = DumbCalculate2(); if (dumbAnswer2 != ERROR_IN_DUMBCALCULATE) { // do my business... } } There are two evil practices in this code. The first practice, "Dumb Way #1" requires that you use a separate return value for success or failure. This causes problems because you can't use the return value DumbCalculate1() function as the parameter to another function because the return value is an error code:
AnotherFunction(DumbCalculate1()); // whoops. Can't do this!
The second practice I've seen that drives me up the wall is using a "special" return value to signify an error. This is illustrated in the DumbCalculate2() call. In many cases, the value chosen for the error case is a legal value, although it may be one that will "almost never" happen. If those chances are one in a million and your game sells a million copies, how many times per day do you think someone is going to get on the phone and call your friendly customer service people? Too many.
Here's the code for optional<T>, a template class that solves this problem.
#pragma once /////////////////////////////////////////////////////////////////////////////// // optional.h // // An isolation point for optionality, provides a way to define // objects having to provide a special "null" state. // // In short: // // struct optional<T> // { // bool m_bValid; // // T m_data; // }; // // #include <new> #include <assert.h> class optional_empty { }; template <unsigned long size> class optional_base { public: // Default - invalid. optional_base() : m_bValid(false) { } optional_base & operator = (optional_base const & t) { m_bValid = t.m_bValid; return * this; } //Copy constructor optional_base(optional_base const & other) : m_bValid(other.m_bValid) { } //utility functions bool const valid() const { return m_bValid; } bool const invalid() const { return !m_bValid; } protected: bool m_bValid; char m_data[size]; // storage space for T }; template <class T> class optional : public optional_base<sizeof(T)> { public: // Default - invalid. optional() { } optional(T const & t) { construct(t); m_bValid = (true); } optional(optional_empty const &) { } optional & operator = (T const & t) { if (m_bValid) { * GetT() = t; } else { construct(t); m_bValid = true; // order important for exception safety. } return * this; } //Copy constructor optional(optional const & other) { if (other.m_bValid) { construct(* other); m_bValid = true; // order important for exception safety. } } optional & operator = (optional const & other) { assert(! (this == & other)); // don't copy over self! if (m_bValid) { // first, have to destroy our original. m_bValid = false; // for exception safety if destroy() throws. // (big trouble if destroy() throws, though) destroy(); } if (other.m_bValid) { construct(* other); m_bValid = true; // order vital. } return * this; } bool const operator == (optional const & other) const { if ((! valid()) && (! other.valid())) { return true; } if (valid() ^ other.valid()) { return false; } return ((* * this) == (* other)); } bool const operator < (optional const & other) const { // equally invalid - not smaller. if ((! valid()) && (! other.valid())) { return false; } // I'm not valid, other must be, smaller. if (! valid()) { return true; } // I'm valid, other is not valid, I'm larger if (! other.valid()) { return false; } return ((* * this) < (* other)); } ~optional() { if (m_bValid) destroy(); } // Accessors. T const & operator * () const { assert(m_bValid); return * GetT(); } T & operator * () { assert(m_bValid); return * GetT(); } T const * const operator -> () const { assert(m_bValid); return GetT(); } T * const operator -> () { assert(m_bValid); return GetT(); } //This clears the value of this optional variable and makes it invalid once // again. void clear() { if (m_bValid) { m_bValid = false; destroy(); } } //utility functions bool const valid() const { return m_bValid; } bool const invalid() const { return !m_bValid; } private: T const * const GetT() const { return reinterpret_cast<T const * const>(m_data); } T * const GetT() { return reinterpret_cast<T * const>(m_data);} void construct(T const & t) { new (GetT()) T(t); } void destroy() { GetT()->~T(): } }; As you can see, it's not as simple as storing a Boolean value along with your data. The extra work in this class handles comparing optional objects with each other and getting to the data the object represents.
Here's an example of how to use optional<T>:
///////////////////////////////////////////////////////////////////////////////// // Optional.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "optional.h" optional<int> Calculate() { optional<int> spline; spline = 10; // you assign values to optionals like this... spline = optional_empty(); // or you could give them the empty value spline.clear(); // or you could clear them to make them invalid return spline; } int main(void) { ///////////////////////////////////////////////////////////////////////////////// // Using optional<T> // optional<int> answer = Calculate(); if (answer.valid()) { // do my business... } return 0; } | Best Practice | I personally don't see why so many programmers have it out for the value (-1). Everyone seems to use that to stand for some error case. I think (-1) is a fine upstanding number and I refuse to abuse it. Use optional<T>, and join me in saving (-1) from further abuse. |
Pseudo-Random Traversal of a Set
Have you ever wondered how the "random" button on your CD player worked? It will play every song on your CD at random without playing the same song twice. That's a really useful solution for making sure players in your games see the widest variety of features like objects, effects, or characters before they have the chance of seeing the same ones over again.
The following code uses a mathematical feature of prime numbers and quadratic equations. The algorithm requires a prime number larger than the ordinal value of the set you wish to traverse. If your set had ten members, your prime number would be eleven. Of course, the algorithm doesn't generate prime numbers; instead it just keeps a select set of prime numbers around in a lookup table. If you need bigger primes, there's a convenient web site for you to check out.
Here's how it works: A skip value is calculated by choosing three random values greater than zero. These values become the coefficients of the quadratic, and the domain value (x) is set to the ordinal value of the set:
Skip = RandomA * (members * members) + RandomB * members + RandomC Armed with this skip value, you can use this piece of code to traverse the entire set exactly once, in a pseudo random order:
nextMember += skip; nextMember %= prime;
The value of skip is so much larger than the number of members of your set that the chosen value seems to skip around at random. Of course, this code is inside a while loop to catch the case where the value chosen is larger than your set but still smaller than the prime number. Here's the source code:
/****************************************************************** PrimeSearch.h This class enables you to visit each and every member of an array exactly once in an apparently random order. NOTE: If you want the search to start over at the beginning again - you must call the Restart() method, OR call GetNext(true). ******************************************************************* class PrimeSearch { static int prime_array[]; int skip; int currentPosition; int maxElements; int *currentPrime; int searches; CRandom r; public: PrimeSearch(int elements); int GetNext(bool restart=false); bool Done() { return (searches==*currentPrime); } void Restart() { currentPosition=0; searches=0; } }; /************************************************************************* PrimeSearch.cpp ************************************************************************** int PrimeSearch::prime_array[] = { // choose the prime numbers to closely match the expected members // of the sets. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, // begin to skip even more primes 5003, 5101, 5209, 5303, 5407, 5501, 5623, 5701, 5801, 5903, 6007, 6101, 6211, 6301, 6421, 6521, 6607, 6701, 6803, 6907, 7001, 7103, 7207, 7307, 7411, 7507, 7603, 7703, 7817, 7901, 8009, 8101, 8209, 8311, 8419, 8501, 8609, 8707, 8803, 8923, 9001, 9103, 9203, 9311, 9403, 9511, 9601, 9719, 9803, 9901, // and even more 10007, 10501, 11003, 11503, 12007, 12503, 13001, 13513, 14009, 14503, 15013, 15511, 16033, 16519, 17011, 17509, 18013, 18503, 19001, 19501, 20011, 20507, 21001, 21503, 22003, 22501, 23003, 23509, 24001, 24509 // if you need more primes - go get them yourself!!!! // Create a bigger array of prime numbers by using this web site: // http://www.rsok.com/~jrm/printprimes.html }; PrimeSearch::PrimeSearch(int elements) { assert(elements>0 && "You can't do a this if you have 0 elements to search through, buddy-boy"); maxElements = elements; int a = (rand()%13)+1; int b = (rand()%7)+1; int c = (rand()%5)+1; skip = (a * maxElements * maxElements) + (b * maxElements) + c; skip &= ~0xc0000000; // this keeps skip from becoming too // large.... Restart(): currentPrime = prime_array; int s = sizeof(prime_array)/sizeof(prime_array[0]); // if this assert gets hit you didn't have enough prime numbers in your set. // Go back to the web site. assert(prime_array[s-1]>maxElements); while (*currentPrime < maxElements) { currentPrime++; } int test = skip % *currentPrime; if (!test) skip++; } int PrimeSearch::GetNext(bool restart) { if (restart) Restart(); if (Done()) return -1; bool done = false; int nextMember = currentPosition; while (!done) { nextMember = nextMember + skip; nextMember %= *currentPrime; searches++; if (nextMember < maxElements) { currentPosition = nextMember; done = true; } } return currentPosition; } I'll show you a trivial example to make a point.
void FadeToBlack(Screen *screen) { int w = screen.GetWidth(); int h = screen.GetHeight(); int pixels = w * h; PrimeSearch search(pixels); int p; while((p=search.GetNext())!=-1) { int x = p % w; int y = h / p; screen.SetPixel(x, y, BLACK); // of course, you wouldn't blit every pixel change. screen.Blit(); } The example sets random pixels to black until the entire screen is erased. I should warn you now that this code is completely stupid, for two reasons. First, you wouldn't set one pixel at a time. Second, you would likely use a pixel shader to do this. I told you the example was trivial: use PrimeSearch for other cool things like spawning creatures, weapons, and other random stuff.
