Game Development Reference
In-Depth Information
'
years to hopefully give you a head start on making your own. First, I
ll show you a
cool random number generator, and then I
'
ll show you a neat algorithm to traverse
any set in random order without visiting the same member twice. Finally we
'
ll end
with a memory pool class I wrote a while back.
There are as many good algorithms for generating random numbers as there are
pages in this topic. Most programmers will soon discover that the ANSI
rand()
function is completely inadequate because it can only generate a single stream of ran-
dom numbers. Most games need multiple discrete streams of random numbers.
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 ran-
dom, achieving a relatively flat distribution curve over the generation of billions of
numbers mapped to a small domain, like the set of numbers between 1 and 100.
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 affect 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 some-
thing you will give your left leg for when writing test tools or a game replay system.
Even Old Code Can Be Useful
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 continuously 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
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:
'
s a cool little class to keep track of your random numbers. You
'
class GCCRandom
{
