Mike's Grab Bag of Useful Stuff

Friday Apr 8th 2005 by Mike McShaffry
Share:

Arm yourself with some lifesaving snippets of code from Mike McShaffry. Some code defies classification. It gets thrown into a toolbox with all the other interesting things that simply won't die. Dust them off and use them on every project and you'll never disappointed.

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.

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 DumbCalculate1(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 dumbAnswer1;
   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;
}
Practice Best
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.

If you are familiar with Boost C++ you'll know that it also has an optional template, but to be honest it does some thing I don't like very much, namely overloading the '!' operator to indicate the validity of the object. Imagine this code in Boost:

optional<bool>bIsFullScreen;

//imagine code here ...

if (!!bIsFullScreen)
{

}

Yes, that's no typo! The "!!" operator works just fine with Boost's optional template. While coding like this is a matter of taste, I personally think this is unsightly and certainly confusing.

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.

Developing the Style That's Right for You

Throughout this chapter I've tried to point out a number of coding techniques and pitfalls that I've learned over the years. I've tried to focus on the ones that seem to cause the most problems and offer the best results. Of course, keep in mind that there is not single best approach or one magic solution for coding a game.

I wish I had more pages because there are tons of programming gems and even game programming gems out there. Most of it you'll beg or borrow from your colleagues. Some of it you'll create yourself after you solve a challenging problem.

However you find them, don't forget to share.

About the Author

Mike McShaffry, a.k.a. "Mr. Mike," started programming games as soon as he could tap a keyboard. He signed up at the University of Houston, where he graduated five and one-half years later. Then, he entered the boot camp of the computer game industry: Origin Systems. He worked for Warren Spector and Richard Garriott, a.k.a. "Lord British," on many of their most popular games. In 1997, Mike formed his first company, Tornado Alley. He later took a steady gig at Glass Eye Entertainment, working for his friend Monty Kerr, where he produced Microsoft Casino.

About the Book

Game Coding Complete, Second Edition
By Mike McShaffry



Published: January 14, 2005, Paperback: 850 pages
Published by Paraglyph Press
ISBN: 1932111913
Retail price: $44.99
This material is from Chapter 3 of the book.

Paraglyph Press, copyright 2005, Game Coding Complete, 2nd Edition.
Reprinted with permission.

Share:
Home
Mobile Site | Full Site
Copyright 2017 © QuinStreet Inc. All Rights Reserved