Game Programming: Random Number Generation

Lots of computer applications require events to happen at random. Games are an obvious example, you might want the aliens to move in a random pattern, the layout of a dungeon to be randomly generated or the artificial intelligent characters to be a little less predictable. The question is though, how can a computer pick a number at random? The answer is that they cannot, if you want true randomness then you have to get it from some external source. Do not despair though, for all practical purposes true randomness is not needed, we just need Pseudo randomness. A Pseudo Random Number is one that is predictable yet appears unpredictable.

One of the oldest and most widely used methods of Pseudo Random Number Generation is the Linear Congurential Generator (LCG). Though this sounds complicated all it really means is that we take a starting value (the seed) do a little bit of math on it and the resulting number is then used as your random number and becomes the new seed for generating the next random number. The classical LCG looks like n = n * a + b mod m. For simplicity we can drop the addition (+ b) and just use n = n * a mod m.

As a simple example let’s use n = n * 11 mod 31. So, each time we want to generate a new number we take the old number and multiply it by 11. If the new number is greater than, or equal to, 31 then we divide it by 31 and take the remainder (or repeatedly subtract 31 until we arrive at a number less than 31, however you want to look at it).

Starting with a seed of 1 we get a sequence which looks as follows:

11, 28, 29, 9, 6, 4, 13, 19, 23, 5, 24, 16, 21, 14, 30, 20, 3, 2, 22, 25, 27, 18, 12, 8, 26, 7, 15, 10, 17, 1, 11, 28, 29, …

We get each of the numbers between 1 and 30 in a seemingly random order before the sequence repeats itself.

The special magic lies in the numbers that we choose to multiply and mod by. If the wrong numbers are used the sequence does not look random. For example if we use n = n * 12 mod 30, again with a seed of 1, then the sequence is:
12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6…
Only four different numbers are produced before the sequence repeats and all the numbers are even.

Selecting the right numbers to use is complex and easy to get wrong. Luckily the hard work has already been done for us. Back in 1969 Lewis, Goodman and Miller suggested n = n * 16807 mod 2147483647 and it has been widely studied and tested since. In 1988 Stephen Park and Keith Miller wrote an excellent paper called “Random Number Generators: Good Ones Are Hard To Find”. In it they look at some of the problems with commonly used random number generators and suggest that n = n * 16807 mod 2147483647 be adopted as a ‘minimum standard’. They also discuss how to implement the generator and one such implementation, based on a method developed by Schrage, is given in Listing 1 (in C) and Listing 2 (in BASIC). The beauty of this implementation is that it only requires 32-bit signed integers.

If you are interested in doing any simulation work utilising pseudo random numbers then a good book to read would be A Guide to Simulation by Bratley, Fox & Schrage which is where I took the algorithm for the portable implementation from.

Listing 1: Portable Implementation in C

static int rnd_seed;

void set_rnd_seed (int new_seed)
{
    rnd_seed = new_seed;
}

int rand_int (void)
{
    int k1;
    int ix = rnd_seed;
	
    k1 = ix / 127773;
    ix = 16807 * (ix - k1 * 127773) - k1 * 2836;
    if (ix < 0)
        ix += 2147483647;
    rnd_seed = ix;
    return rnd_seed;
}

Listing 2: Portable Implementation in BASIC

dim shared rnd_seed as integer

sub set_rnd_seed (new_seed as integer)
    rnd_seed = new_seed
end sub

function rand_int() as integer
    dim hi as integer
    dim lo as integer

    hi = rnd_seed \ 127773
    lo = rnd_seed mod 127773
    rnd_seed = 16807 * lo - 2836 * hi
    if (rnd_seed <= 0) then rnd_seed += 2147483647
    return rnd_seed
end function

A faster implementation of n = n * 16807 mod 2147483647 was suggested by David Carta in 1990. For full details of Carta's method I would suggest reading Robin Whittle's description at http://www.firstpr.com.au/dsp/rand31/. A version of Whittle's implementation in C is shown in Listing 3 and a version in BASIC is given in Listing 4.

Listing 3: Fast Implementation in C

static int rnd_seed;

void set_rnd_seed (int new_seed)
{
    rnd_seed = new_seed;
}

int rand_int (void)
{
    unsigned int hi,lo;
	
    hi = 16807 * (rnd_seed >> 16);
    lo = 16807 * (rnd_seed & 0xFFFF);
    lo += (hi & 0x7FFF) << 16;
    lo += hi >> 15;
    if (lo > 2147483647)
        lo -= 2147483647;
    rnd_seed = lo;
    return rnd_seed;
}

Listing 4: Fast Implementation in BASIC

dim shared rnd_seed as integer

sub set_rnd_seed (new_seed as integer)
    rnd_seed = new_seed
end sub

function rand_int() as integer
    dim hi as uinteger
    dim lo as uinteger

    hi = 16807 * (rnd_seed shr 16)
    lo = 16807 * (rnd_seed and 65535)
    lo += (hi and 32767) shl 16
    lo += (hi shr 15)
    if (lo > 2147483647) then lo -= 2147483647
    rnd_seed = lo
    return rnd_seed
end function

If you found this article useful, have any questions, comments or have a particular topic that you would like to see written about then please let me know.