Algorithms for an Infinite Universe

In today's PC world, consumers enjoy high levels of sophistication in their products. Given these experiences, it's no wonder that the depth of some games occasionally falls below the expectations of the target audience. Often, the chief cause of this is that the game is simply not big enough. Once the battles have been fought and the blood spilled, the player is left with something of an anticlimax.

Even with the multi-megabyte resources at their disposal, game designers often run out of the space they need to distribute a truly huge game, especially when the images are photo-realistic in detail and the sound is composed of awesome thumping music and sampled explosions. In such cases of large assets, the game universe's size suffers the first cut. In all likelihood, the team will decide that the game should hobble along with only twenty scenarios instead of the originally planned one hundred. Hopefully, the graphics will be so stunning that nobody will notice.

This, however, need not be the case. Memory size is not necessarily a threat to game depth. One of the most famous examples of the infinite game universe is a game called Elite. This game was originally written for the BBC Model B computer in 1980 by David Braben and Ian Bell. It has since been ported to all home computer formats, and is still as widely played now as it was in its heyday. The original game ran on a machine with 32KB of memory (16 ROM and 16 RAM), but still boasted a depth of play that has yet to be matched - seemingly infinite planets, all with names, and each with its own characteristics.

For certain types of level-based games such as Doom, Manic Miner, Tarzan and so forth, the only approach that makes any sense is to store the various level files in memory and convert them into the game universe in real time. However, for many styles of games that don't rely heavily on a maze-based universe, there is no real need to store a map of any kind. In fact, all that is required is to give the player a notion of infinity and unrestricted movement. It is in this latter type of game that we can employ algorithms to generate the characteristics of the game universe in real time.

There are three main areas in which the application of algorithms can give the player the feeling of being in an infinite universe:

For each of the above areas, there are existing techniques which may be employed to generate the features of the game universe in real time. That is, create the different aspects of the environment or even the plot with no prior knowledge other than the parameters required by the algorithms.

One of the key benefits of using algorithms to generate the universe in real-time is that it frees up all the space that otherwise would be taken up storing the name of each city, country, or planet. Now you can use that space for other aspects of the game. You no longer have to know in advance which races of aliens are involved in vicious wars, or where the guardian of the seven keys is hiding on the fourth island of a given sea - these things will be decided algorithmically as the game is played. In order to make such decisions, it is important that we are able to describe the characteristics of the universe in sufficient detail.

Another benefit of using these techniques is that the next step in the scenario - or the properties of a given game object (when the player arrives at that object) - aren't constrained by any actions that the player makes. Therefore, the world imposes no restrictions upon the player's movement beyond the rules of the game. The "game" may not even know at a given point in time what the outcome of a player’s move will be until after it has been made. The "game" doesn't have to impose any such moves on the player.

Predictably Random Numbers

The key to producing the effect of an infinite game universe is the ability to produce an endless variation in the principle game elements. This could be quite easily arranged, simply by generating a random number sequence using the current date and time of the host computer as the starting point (or seed). Thus, when continually played, events would unfold in a random manner, providing an infinite universe in which to play.

This approach suffers from two drawbacks. The first is that no two games would ever be the same. Not just in terms of the game play itself, but also key features of the universe would change, such as the initial placement of objects (such as stars and planets), or sequences of events. The second drawback stems from the first - it would be impossible for two players to share their experiences, since they would inhabit two completely different game universes. They would not be able to swap tips, such as "if you go to the third planet from sun x, be aware that you will be attacked," nor strategies for survival, since one strategy that works in one universe would not work in the other.

Therefore, we need to have a situation in which we can generate a sequence of random numbers repeatedly. The randomness gives us the power to create an infinite game universe, while the repeatability enables us to ensure that, at least in the beginning, two instances of the same universe will look the same. Such sequences of numbers are known as pseudo-random, simply because they can be repeated. The basic algorithm is as follows:

This may look daunting, but it is very simple to implement, as the code in Listing 1 shows. There are, however, a few points that should be noted. The first is that the sequence will repeat itself after Max iterations. The second is that the choice of Gen1 and Gen2 have a direct effect on the sequence of numbers, as does the seed. Gen1 and Gen2 must be much larger than Max for a satisfactory absence of pattern. In fact, the pattern breaking is done by Gen2; indeed, a simple multiplication followed by a division yields a sequence of numbers with a strong pattern, and Gen2 serves to remove that pattern to a certain extent.

Listing 1.cpp

// Pseudo Random Number Generation Example

// (c) 1999 Guy W. Lecky-Thompson
// All Rights Reserved

#include
void main(void)

{

// Choose two large integers such that
// one is double the other

unsigned long ulGenerator1;
unsigned long ulGenerator2;
ulGenerator1 = 4096;
ulGenerator2 = ulGenerator1 * 2;

// Choose a seed value that is between 1
// and the smaller of the large integers

unsigned long ulSeed = 1024;

// Choose a value Max, that represents the highest number that is to be returned

unsigned long ulMax = 2048;

// Generate a series of 10 numbers

for (int i = 0; i < 10; i++)

{

}

}

There is one final limitation. The largest number that can be generated using this system is 4,294,967,295. It follows from the algorithmic description above that the sequence will begin to repeat itself after the 4,294,967,295th iteration. This is a limitation of the data type used, a 32-bit unsigned integer. If greater numbers are required, it is necessary to move to a different representation.

Creating the Universe: an Example

With our pseudo-random number generator in place, we can now begin to build our universe. In the manner of all good game examples, this will be represented by a black backdrop upon which we will place a scattering of stars.

In this example, we are just going to let the chips fall where they may, and not worry about whether the generated universe adheres to the physical laws of universe creation. We shall see later how to incorporate limitations into the generation of universe features. For now, however, we will simply apply our pseudo-random number generation algorithm. Listing 2 shows the implementation for the PseudoRandomizer class.

Listing 2

Prand.cpp

// Implementation File for the PseudoRandomizer Class

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

#include "prand.h"

PseudoRandomizer::PseudoRandomizer(unsigned long ulGen1,

unsigned long ulSeed,

unsigned long ulMax)

{

this->ulGen1 = ulGen1;

this->ulGen2 = ulGen1 * 2;

this->ulSeed = ulSeed;

this->ulMax = ulMax;

}

unsigned long PseudoRandomizer::PseudoRandom()

{

unsigned long ulNewSeed;

ulNewSeed = (this->ulGen1 * this->ulSeed) + this->ulGen2;

ulNewSeed = ulNewSeed % this->ulMax; // Use modulo operator to ensure < ulMax

this->ulSeed = ulNewSeed;

return this->ulSeed;

}

unsigned long PseudoRandomizer::PseudoRandom(unsigned long ulMaxValue)

{

unsigned long ulNewSeed;

this->ulMax = ulMaxValue;

ulNewSeed = (this->ulGen1 * this->ulSeed) + this->ulGen2;

ulNewSeed = ulNewSeed % this->ulMax; // Use modulo operator to ensure < ulMax

this->ulSeed = ulNewSeed;

return this->ulSeed;

}

Prand.h

// Class Header File for the PseudoRandomizer Class

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

class PseudoRandomizer

{

private:

unsigned long ulGen1, ulGen2, ulSeed, ulMax;

public:

PseudoRandomizer(unsigned long ulGen1,

unsigned long ulSeed,

unsigned long ulMax);

unsigned long PseudoRandom();

unsigned long PseudoRandom(unsigned long ulMaxValue);

};

The code in Listing 3 implements the Universe class. As can be seen, the dimensions of the required universe are used to provide values for Gen1 and Gen2, the two modifiers from the PseudoRandomizer class. In this way, we are sure that the sequence of numbers resulting from the given seed will not change from instance to instance.

Listing 3:
Unigen.cpp

// Class Implementation File for the Universe Class

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

Universe::Universe(unsigned long ulXDimension,

unsigned long ulYDimension)

{

// Set the parameters for this universe

this->ulXDimension = ulXDimension;

this->ulYDimension = ulYDimension;

// Initialise the randomizer

this->prRandomizer = new PseudoRandomizer(ulXDimension,

ulYDimension,

ulXDimension * ulYDimension);

}

int Universe::StarAt(unsigned long ulXPosition,

unsigned long ulYPosition,

unsigned long ulSerialNumber)

{

unsigned long ulRandomValue;

// Set up the serial number for this grid reference

ulSerialNumber = ((ulYPosition + 1) * this->ulXDimension) + ulXPosition);

for (unsigned long ulCounter = 0; ulCounter < ulSerialNumber; ulCounter++)

{

ulRandomValue = this->prRandomizer->PseudoRandom();

}

// If ulRandomValue falls in the lower 1%, there is a star here

if (ulRandomValue <= ((this->ulXDimension * this->ulYDimension) / 100))

return 1;

return 0;

}

Unigen.h

// Class Header File for the Universe Class

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

#include "prand.h" // The Class Definition for the random number generation

class Universe

{

private:

unsigned long ulXDimension, ulYDimension; // The 'size' of the Universe

unsigned long ulUniverseSerialNumber;

PseudoRandomizer * prRandomizer;

public:

Universe(unsigned long ulXDimension,

unsigned long ulYDimension);

int StarAt(unsigned long ulXPosition,

unsigned long ulYPosition,

unsigned long ulSerialNumber);

};

Use of the Universe class is very simple. The initialization code simply sets up the randomizer, and stores the dimensions of the universe. If we wish to know whether there is a star at a given point, we call the StarAt class member. This will then generate a unique "serial number" value for the given grid reference, and call the randomizer that number of times. The resulting value is then used to decide whether a star is present or not. If a star is present, a value that is greater than 99 percent of the total area will be indicated. Incidentally, the area of the universe is used to determine the maximum value returned by PseudoRandomizer.

The discerning reader will have noticed by now that universes generated in this way cannot be truly random, as the dimensions must be given beforehand. In fact, due to the limitations of our randomizer routine, each universe may only be 65,535 by 65,535 units in size (the square root of the maximum possible generated random number). Thus, this system lacks Macro-Infinite Resolution. However, if we populate 1 percent of the total area with game elements (stars, in this example), there will be 42,948,362 of them, which is enough to give a reasonable illusion of infinity.

Name Generation Techniques

In order to see how the PseudoRandomizer class may be employed to give characteristics to a particular game element, we shall now turn our attention to naming each of the stars in the universe. There are a myriad of techniques for doing this, but one of the most popular is known as the Markovian List (see also A.K. Dewdney, The Tinkertoy Computer, W.H. Freeman: 1990). In essence, this involves examining the frequency of repeated elements in a given number of sequences, and using this as a basis for generating new sequences. The sequences in the case of names are built up of letters.

Before creating actual names, we need to build up a table in which the frequency of adjacent letters in a list of sample names can be stored. This table must be 26 by 26 in order to store all the letters in the alphabet. We can then examine each word in a given list, and determine the frequency of adjacent letters in each word. The cumulative frequencies are stored in the table. For example, if the word is:

‘Nicole’

Then the adjacent letter couples are:

‘ni’ ‘ic’ ‘co’ ‘ol’ ‘le’

So, for this word, we would add one to the value stored in the column referenced by ‘n’ and ‘i’, and one to the value stored in the column (i,c), and so on for each couple. Applying the same technique to every word in the list results in a table which represents the frequencies of all letter couples.

Listing 4 shows the core algorithm for generating such a table. The table used in this listing is actually 28 by 28 in size, so that we can identify those letters which may end or begin a name.

Listing 4:
Tablegen.cpp

// Building a letter frequency table

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

#include

#include

void AddLetters(char * szWord, unsigned long ulTable[28][28])

{

int nWordLength, nFirstLetter, nLastLetter, nLetter;

// Decapitalise the word

for (nLetter = 0; nLetter < (int)strlen(szWord)-1;nLetter++)

tolower(szWord[nLetter]);

// Add the first, and last to the table

nWordLength = (int)strlen(szWord);

nFirstLetter = (szWord[0] - 'a') + 1;

nLastLetter = (szWord[nWordLength-1] - 'a') + 1;

ulTable[0][nFirstLetter]++; // Space followed by letter

ulTable[nLastLetter][27]++; // Letter followed by space

for (nLetter = 0; nLetter < nWordLength-2; nLetter++)

{

nFirstLetter = (szWord[nLetter] - 'a') + 1;

nLastLetter = (szWord[nLetter+1] - 'a') + 1;

ulTable[nFirstLetter][nLastLetter]++;

}

}

It should be noted that this technique is not constrained by language; that is, any language will work equally well, and for those languages that are based on the Roman Alphabet (accents excluded), the algorithm can be applied as is, with no further modifications.

Once the table has been built, it can then be used to build new words at random. The first step is to determine the length of the desired word. Next, we must ascertain the first letter. This is done by adding up all the frequencies of those letters which can appear at the beginning of a word (that is, the frequencies of the letter couples in the first row of the table). Then, we choose a number at random between 1 and the sum of all the frequencies. The final step in choosing the letter is to start at the first column, and check to see if the chosen value falls between 1 and the stored value. If not, each column is examined in turn, by adding the value stored there and checking to see if this exceeds the random value. Once we find a column in which this is the case, we have found our starting letter.

The above algorithm yields a letter that can be preceded by a space character. The exact same technique can be applied on the following letter, but this time we use the row referenced by the letter that was chosen to begin the word. Then, for each letter that we require in the word, the same steps can be taken in turn until we have filled each available position. The code in Listing 5 shows the algorithm for doing this.

Listing 5:
Namegen.cpp

// Building a word from a letter frequency table

// (c) 1999 Guy W. Lecky-Thompson

// All Rights Reserved

#include

#include "Prand.h" // Pseudo-randomizer

#include

int GetLetterPosition(unsigned long ulWordTable[28][28], PseudoRandomizer * prGenerator, int nPrevious)

{

int nCounter;

unsigned long ulFrequencyTotal, ulFrequencyRunningTotal, ulRandomLetter;

// Get the frequencies

for (nCounter = 1; nCounter < 27; nCounter++)

{

ulFrequencyTotal = ulFrequencyTotal + ulWordTable[nPrevious][nCounter];

}

// Choose a 'target' frequency

ulRandomLetter = prGenerator()->PseudoRandom(ulFrequencyTotal);

// Move through the table until we hit the 'target' frequency

ulFrequencyRunningTotal = 0;

nCounter = 1;

do

{

ulFrequencyRunningTotal = ulFrequencyRunningTotal + ulWordTable[nPrevious][nCounter];

nCounter++;

} while (ulFrequencyRunningTotal < ulRandomLetter);

return nCounter;

}

void GenerateWord(int nLetters, char * szWord, unsigned long ulWordTable[28][28], PseudoRandomizer * prGenerator)

{

int nLetterPosition;

// First, find the letter that can start the word

nLetterPosition = GetLetterPosition(ulWordTable,prGenerator,0);

// We have the first letter

sprintf(szWord,"%c\0",(nLetterPosition-1) + 'a');

// Repeat until nLetters have been added

do

{

nLetterPosition = GetLetterPosition(ulWordTable,prGenerator,nLetterPosition);

sprintf(szWord,"%c\0",(nLetterPosition-1) + 'a');

} while ((int)strlen(szWord) < nLetters);

printf("Word : %s\n",szWord);

}

So, in order to generate a name for each of our stars, all we need to do is seed the PseudoRandomizer based on the unique position of the star (based on the grid reference), and let it produce a stream of random numbers which will provide the basis for choosing each letter in the word. Since we are guaranteed the same sequence of numbers for every seed value, all we need store is the frequency table. In addition, since the frequency table is derived from a list of real world words, each name will also "sound" natural.

Using this technique applied to the text of this article, I generated the frequency table in Figure 1. Applying the name generation algorithm produced the sequence of twenty names in Figure 2. At this point it is worth calculating where the storage "break even" point is.

The table will occupy (28x28)x2 bytes of memory, if we assume each value to be a 16-bit floating point number. This means that (code excluded) we are using 1,568 bytes of storage space. This could equally well hold the actual names of the stars, in which case we could store 261 names instead (assuming each is 6 characters long).

So, if we need only to store 261 names for our universe, then it is more efficient simply to store them directly. Using our universe model, this would mean that the universe dimensions would be 161 by 161 units (since only 1 percent can be occupied, and we only have space for 261 stars), or about 0.2 percent of the algorithmic capacity, based on a maximum universe dimension of 65,535 x 65,535.

Generating Random Terrain

We have already discussed the Macro-Infinite Resolution, and how it is limited by the size of random number sequence that can be generated. However, at the other end of the spectrum is Micro-Infinite Resolution; in effect, zooming in to the detail of a given game element. In practice, this is limitless, so long as a given point that we wish to examine can be uniquely identified within the limitations of the system.

This means that so long as we can identify a given game element uniquely based on its position in the game universe, we can define the characteristics of that point algorithmically. The reason that it needs to be identified is so that we can seed the random number generator using the identifier, and guarantee that the sequence of numbers generated which are used to determine the characteristics are the same for two instances of the game universe.

One example of how this is useful is in the generation of terrain maps. It means that not only can we generate the entire map, but that we can also zoom in to ever increasing detail on a given point, so long as we can identify it uniquely. For example, we can show the map, and then zoom in to a coastline. As we zoom, the coastline will become ever more detailed as the resolution increases. The reason that this is possible is that we can break down each feature into a series of grids, and then each of those grid squares into grids to get more detail, and so on. Each of the grid squares can be given certain characteristics based on its position in the game Universe.

The simplest type of terrain that can be generated is completely chaotic. That is, for each point onthe arbitrary grid, a value can be assigned at random which indicates the height of the terrain. The image in Figure 3 is the result of such a random terrain generator

Of course, it does not look like traditional terrain, because there are no patterns to the arrangement of height values. In order to create a pattern, a technique can be used known as Quadrant Average Analysis. The essence of this technique is to break down the terrain into a series of grids. For each grid, the sum of the height values in the squares is calculated, and then the average computed, which is then the value given to the entire grid. This can then be performed again for successively larger grids until the required resolution is achieved (Figure 4 shows this technique in action).

Note that in defining the landscape in this fashion, if we decide to "zoom in" to the map, we can recalculate each land feature by it’s placement on the planet, based on the neighboring features. Be warned, however, that the greater the size of the quadrants used to create each feature, the more computationally expensive it will be, since more squares need to be taken into account.

More realism can be achieved if we use a mixture of storage and calculation. One of the best techniques for creating realistic landforms is based on observing the natural formation of land in the real world. The key to the creation of the majority of natural landforms is the existence of fault lines on a planets surface. These fault lines result in either ridges or troughs, which give mountains or valleys. The fault lines intersect at certain points.

There is more to the science of geophysics than that, but this will be more than enough for our next example. As before, we use a grid. This time, instead of populating it with random squares, we draw lines running from top to bottom and left to right, as shown in Figure 5. The start and end points of the lines are chosen using the pseudorandom number generator seeded on a value that is a combination of their sequence number and the planets position within the Universe.

Next, the same algorithm is applied as before, to smooth out the spaces between the lines. The effect of this can be seen in Figure 6. To add even more spice to the landforms, we can vary the "height" of each point of the lines with an algorithm. We might choose, for example, to apply a sine function of a pseudorandom amplitude and frequency. When we combine these, and "average out" the resulting pattern, the result is very convincing.

However, it is much too computationally expensive to actually recalculate all this just to zoom into one square, so this initial height map must be stored for future reference. We can, on the other hand, assign other features such as rivers, trees, or grass in an algorithmic fashion based on the stored value of a particular square along with it’s position, in real time without any real penalties.

Plot Sequencing

Pulling all of these techniques together into a game requires the use of Plot Sequencing. This applies not only to the continuing story line (Event Sequencing), but equally to the placement of Game Elements. That is to say, the flow of the game is determined based on the location of Game Elements within the Universe. Since this placement has been determined algorithmically, the Event Sequencing must also be based on algorithms.

Earlier we illustrated how the pseudorandom number generator can be used to determine the placement of individual Game Elements (the example itself used stars). Now we must turn our attention to the characteristics of each star - the shape of the Game Elements will determine a large part of the addiction to the game in the mind of the player. It is the interaction of the Game Elements that make the player return for a second try.

Once we have determined the type of feature each Game Element should have, it is time to start choosing the actual values that each Element will have. In our example, we can say that each star may be host to a number of planets. Furthermore, each planet can have a number of moons. Of course, some stars will not have planets, and some planets will not have moons. Arbitrarily, we choose that 25 percent of the stars should have planets orbiting them, and that of those 10 percent should have moons.

To put this into effect, for each star there is a 25 percent chance that planets will be found in orbit around it, and that for each planet there is a 10 percent chance that it will, in turn play host to a moon.

Here again, we shall use the pseudorandom number generator, returning a value between 1 and 100, seeded on the serial number of the Game Element. As previously noted, each star can be assigned a serial number based on it’s position within the Universe. Using the same technique, each planet that orbits a given star can also be given a serial number based on its position relative to the star itself. Thus, we can seed the generator and decide upon the placement of moons.

One should not be dissuaded from using the same serial number for different Game Elements, since the characteristic that is defined by the result of the pseudorandom number generator will be different, and therefore distinct. Indeed, for extremely large Universes, it may be unrealistic to assign a unique number to each end every Element. One must assume that, in programming the game itself, the difference between Star-997854 and Planet-997854 is clearly definable.

At the beginning of the article, I used, as an example of a large Universe model, Elite by David Braben and Ian Bell. In this game, each star has other characteristics such as the type of population (from Human to Frogs), the political status of the system (Anarchic through Democratic), and commodity prices based on the industry type (Agricultural, Industrial, and so on). Each of these can be modeled using algorithms based on the pseudorandom number generator. It is the mixture of these Element Characteristics that give shape to the game.

Once these characteristics have been defined, it becomes possible to coordinate events in the Game Universe (the plot) based upon corresponding values of various characteristics with relation to the game player. This Universe Coherence lends an aspect to the game which is predictable and yet has it’s basis in the chaotic relationships defined by the application of pseudorandom algorithms.

For example, if the player travels to a system whose political bearing is anarchic, with a cargo of weapons, one can say that he is likely to be attacked by pirates. However, the same player travelling to a democratic system may in turn be subject to the attention of local police who wish to relieve him of his illegal arms cache. Exactly when the subject will be attacked, and by whom, is determined by the pseudorandom number generator. In order to further coordinate events, we may also choose Reference Points within the Universe. A Reference Point is simply a value that, when reached, triggers another sequence of events.

Imagine, for a moment, attempting to store all this information. It would require either large amounts of memory, or frequent hard drive or CD-Rom accesses. Either way, the penalties are stricter than the time it takes to determine the course of events using an algorithmic model. And it is not only the realms of outer space that are subject to this type of game development style. Almost all first person role playing games may also use this technique. We may wish to say that a particular door has a key that is stored on an island somewhere, exactly where, we may not care, and we can determine where it is located, how the player learns of its location and when it is applicable as the game unfolds, provided that we have defined a rich set of rules that specify, algorithmically, the nature of the game itself.

I mentioned earlier that the pseudorandom technique can be used to achieve Micro-Infinite Resolution. The preceding example is one illustration of this. Another way in which this could be demonstrated would be if we decided to put villages, or towns, on the squares. Then we could put a random network of streets within the towns, and buildings next to the streets. These building would have windows and doors, opening to rooms with furniture. Some of the furniture might have cupboards containing maps, keys, gold or weapons. As long as we keep zooming in and calculating the location of these objects based on their relative positions, there is no limit to the quantity of objects that we can locate in real time.

The techniques provided here only skim the surface of this approach; indeed, the ways in which it can be applied are limited only by the imagination of the game designer.

Guy is a recent graduate from the University of Derby, UK, where he received a First Class Honors degree in Computer Studies, specializing in the Design of Intelligent Agents ( thesis title ). Recently, he has taken an interest in the real time generation of game universes, studying techniques used in early memory-limited home computers. He works as a programmer for a financial institution management company in Brussels, Belgium.