Procedural Generation in Games

Ever wondered why, in games like Grand Theft Auto, you generally can't get into the buildings of cities to explore their interiors? Usually, it's a matter of time and memory, but these restrictions may change in the near future thanks to new techniques in procedural generation.

If a designer were forced to meticulously create the interiors of each and every building in an urban sandbox game like GTA, the game would no doubt end up well over budget. Even if the time were allotted, a typical game or DVD disc might not even have the capacity to hold all the models. So what if, instead, you could build up the models as they are required based on only a small, unique piece of information? That's what the second talk I saw for the candidates of a faculty position here at Carleton was all about (the first talk being on research in computational video). It was called "Generation P: The P Stands for Simulation" and given by Dr. Anthony Whitehead, who currently works in the School of Information Technology here at Carleton.

Procedural generation is all about creating objects and behaviors from some set of rules rather than explicit control from designers and developers. This makes the content available on demand, and not only reduces development time for a game, but can also add to the realism (since no two objects will be the same), unpredictability, and freedom of action on the part of the gamer.

There are some recent games that are out (or almost out) using procedural generation. In fact, the latest Grand Theft Auto (IV), which is allegedly going to be released sometime between February and April 2008, is said to use procedural generation to increase the number of explorable building interiors. The upcoming game Spore is almost completely procedural based, and many other simulation games like The Sims tend to use a lot of this technique. Other titles that made (or will make) use of procedural generation of some kind include Oblivion: The Elder Scrolls IV, kkreiger, Elite, and Diablo I and II.

You can almost think of procedural generation as a sneaky method for compression. After all, just one small seed value can be used to build the rest of an entire building, making use of the fact that a certain random number generation will always produce the same sequence of numbers. It is by using this fact that developers can ensure the same building is rebuilt every time it is needed.

However, there lies a small challenge still: if a building is destroyed and rebuilt several times during a gaming session, what happens to the changes that the gamer has made due to interactions within? The proven solution turns out to be as simple as you might imagine. A simple hash table is all that is required to persist the interactions.

You can learn more about procedural generation for buildings, with change persistence, in the paper Dr Whitehead co-authored: Lazy Generation of Building Interiors in Realtime.

It's not hard to imagine how procedurally generated content could be applied to many other aspects beyond graphical models. For instance, music in games could be algorithmically generated rather than composed, which could allow, for instance, easier mechanisms for transitioning between different areas on a map that require music of different moods. It will be interesting to see whether games continue along this path and what the results will be.