October 25, 2016
Hot Topics:

Mike's Grab Bag of Useful Stuff

  • April 8, 2005
  • By Mike McShaffry
  • Send Email »
  • More Articles »

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"

   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:


//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:


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;

   PrimeSearch(int elements);
   int GetNext(bool restart=false);
   bool Done() { return (searches==*currentPrime); }
   void Restart() { currentPosition=0; searches=0; }



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:
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


   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)

   int test = skip % *currentPrime;
   if (!test)

int PrimeSearch::GetNext(bool restart)
   if (restart)

   if (Done())
   return -1;

   bool done = false;
   int nextMember = currentPosition;

   while (!done)
      nextMember = nextMember + skip;
      nextMember %= *currentPrime;

      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;

      int x = p % w;
      int y = h / p;

   screen.SetPixel(x, y, BLACK);
   //of course, you wouldn't blit every pixel change.

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.

Page 3 of 3

Comment and Contribute


(Maximum characters: 1200). You have characters left.



Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date
Rocket Fuel