(This article is in six parts: parts one, two , three, four, five and six, along with a follow up article series Proceduralism; and is also available as a PDF)
Procedural content generation is yet to set the game industry on fire. It has featured in one of the greatest games of all time, Diablo and it's successor, who directly trace their roots to roguelike games such as Angband. But the recent implementation of random level generation in Hellgate: London did little to inspire people that this method works well for game level design. But bubbling under the surface of the industry, and very much evident in future games like Spore is a methodology that like most technologies has been underwhelming in the short term but in the long term will have profound consequences for how games are designed.
An announcement late last year should have set the hearts of anyone working in the games industry a tremor. No, it wasn't Activision merging with Vivendi. Gearbox Software previewing use of procedural content generation in Borderlands was met with moderate skepticism, but was generally well received. It enabled me to remind at least one other person of the greatness of the line 'Guns. We need lots of fucking guns.', predating Neo's similar but censored sentence by seven years (The movie in question was Split Second). But more importantly, it points the way forward to a time where the current role of the level designer will be as obsolete as punch cards for programming computer games.
This article will survey the current scope of procedural content generation in order to highlight where PCG is making inroads into the traditional level designer roles, and how various enabling technologies are making procedural content easier to build and deploy within other game technologies. The survey will point in a number of directions, not necessarily positive, that I anticipate procedural content generation taking game play, and conclude with some suggestions what the next five years will bring, and a few options for anyone interested in taking the ideas herein further.
Procedural content generation (PCG) is the programmatic generation of game content using a random or pseudo-random process that results in an unpredictable range of possible game play spaces. I prefer the term procedural content generation to procedural generation: the wikipedia definition of procedural generation includes using dynamic as opposed to precomputed light maps, and procedurally generated textures, which while procedural in scope, do not affect game play in a meaningful way. The concept of randomness is also key: PCG should ensure that from a few parameters, a large number of possible types of content can be generated.
Procedural content generation can exist in games in a number of ways.
1. Runtime random level generation
This is the 'prototypical' example of procedural content generation, which is what most of you would have thought of when you starting reading this article. The classic example is of Rogue's random placement of rooms linked by corridors, which makes the game infinitely replayable and softens the penalty of permadeath. I would suggest that dynamic random level generation in two dimensions is still an interesting area of research: I've written extensively about it elsewhere, but there are still algorithms to be discovered and techniques to be used. The problem is however mostly solved in the sense that there is a robust variety of interesting algorithms from maze generators to room placers to choose from and considerable literature covering the implementation methods.
In contrast, procedural content generation in 3 dimensions is still a relatively undeveloped field. Hellgate: London is an example of how not to do three-dimensional design - the cost of generating sufficiently interesting 3d objects and textures ensures that there is a great deal of repetition in the resulting random levels. It is possible to extend many of the two dimensional concepts into the 3rd dimension: maze generation is mostly extend able depending on which algorithm you choose, and the recent releases of Dwarf Fortress shows that it is possible to extend the classic roguelike design into three dimensions.
Procedural generation of height fields in 3d is the only other area that has had considerable effort devoted to it. Probably the best in-game example is Tribal Trouble which uses a simulation of erosion in order to create a play field resulting an infinite number of multi player maps. There are a large number of fractal-based world generators which use similar techniques to create vast and elaborate world spaces, which to a greater or lesser degree use simulation of geological and meteorological processes to design the map height-fields and populate them with content.
What is missing is any serious attempt to create fully three dimensional world spaces, including bridges, archways, towers and other highly interconnected topologies. This is in a big part due to one of the key constraints of dynamic level generation which is to ensure complete connectivity between all parts of the map. Even in a two dimensional map, this can be a complex problem. In 3d, any game which simulates gravity must ensure that units that fall into lower parts have a way of accessing back to the higher parts unless deliberate disconnections form a part of the game play. In addition, constraints on slope steepness, minimum unit size and so on can complicate level connectedness considerably.
Tribal Trouble side steps these issues somewhat by generating enough maps and checking their connectedness, and then using a statistical proof to show that a sufficiently large percentage of maps will be playable. Other random level generators may use a verification method, which discards and restarts any maps that may prove unsuitable for play. Sufficient tests have to be made for degenerate cases, and fall backs to avoid infinite loops or sufficiently long delays in level generation, which even with a two dimensional maps can be a considerable complication, often due to the computational cost of random number generation. Dwarf Fortress maps, even prior to the introduction of a 3rd dimension, could take 15 minutes or more to run on a modern processor.
2. Design of level content
If the problems of random map generation may seem insoluble, then this does not stop them from being used. What frequently happens is that level content, particularly height fields, is generated in the level design tool, as opposed to the final game engine. The level designer is then responsible for verifying the correctness of the level or modifying it to ensure it is correct. Procedural content generation then becomes a mechanism for minimising the cost of content creation.
Darwinia by Introversion Software is a great example of using procedurally generated levels supplemented with hand editing to leverage a small developer base. The Darwinia levels were original built using a procedural 3d height field generator as it would have been unfeasible to places all the map vertexes manually. Introversion is using the same technique for their next in-development game Subversion: Chris Delay releases frequent development updates on the in house blog that are well worth reading. The Subversion city generator looks robust enough to be used as a dynamic random level generator at this stage but without knowing the final game play it is impossible to be sure.
The MegaTexture technology that John Carmack developed initially for Enemy Territory: Quake Wars lends itself well to importing a procedurally generated bitmap for a map level. The technology itself uses Wikipedean 'procedural generation' to convert this bitmap into a three dimensional playing space, but the original bit map could be created using standard PCG height field algorithms and 2 dimensional PCG techniques.
At a lower level, there are already well accepted techniques for infilling level detail using 'procedural generation' and procedural content generation techniques. Chief amongst these is SpeedTree, a middle ware product that enables level designers not to have to worry about the placement of every in-game tree and shrub. SpeedTree is used in Oblivion to great effect from what was originally a piece of software developed to enhance computer game golf courses.
Similar techniques can be used to automate the placement of textures and decals so level designers don't have to worry about texture alignment and can instead focus on higher level design elements. This is in addition to procedural textures, which are again an example of 'procedural generation' that may incorporate random noise to lessen visible artefacts.
3. Dynamic world generation
This is one of the earliest procedural content generation techniques, where the in-game map exceeds the ability of the computer to store it either in memory or on-disk (depending on performance requirements). While storage has grown massively since the days of Elite, it is still not unlimited and the same techniques can be put to great use, for instance, displaying all the objects in an typical size asteroid belt or planetary ring.
The technique is to use a seed number (42 is a popular choice) which remains constant, and then grow the playing field iteratively using this seed number permutated by pseudo-random number techniques. Usually growth is from a top-down subdivision, which lends itself well to fractal generation techniques, as well as matching typical level of detail (LOD) implementations. The map is never held in memory except as a temporary structure to display, and is discarded as soon as components of it are no longer required: nothing procedurally generated is ever written back out to disk.
The best example of this in development is Infinity: The Quest for Earth. I can only urge you to watch this video (wait for the second half if you are impatient) and then read the developer's blog, in order to see the power of this technique.
It does have significant drawbacks. In particular, certain structures, typically long thing ones like roads and rivers are very hard or completely impossible to implement this way because of the subdivision technique (roads are merely hard, rivers impossible because of the dependency of having to know the height of an adjacent subdivision in order to compute the river path). And currently the process is very CPU intensive, with increasing levels of detail usually depending on a high O-notation algorithm of some kind.
Changing the algorithm will also change all of the map, as the map structures themselves are highly dependent on the algorithm and therefore the software cannot be upgraded easily without resetting the game. The procedural content generated must be verified as consistent as a part of the run-time implementation: which limits what checks can be made to ensure that the content makes sense and therefore requires robust generation procedures. Finally, any change to the map must be stored as a delta. Reloading map deltas will ultimately overwhelm the strengths of the technique, so the majority of implementations will prevent, minimise or ignore any player or designer made changes to the map structure.
What instead happens is that the map lends itself well to exploration: essentially you are moving through a set of possibility spaces. The game designer is as much in the thrall of the procedural content generation algorithm as the players. He can manipulate the algorithm to try to generate different types of spaces - but the whole world depends on the algorithm, and therefore he may equally destroy something else that has been created. In fact one DOS-based game has made this exploration a central element of the game: features discovered and named by the players become a part of each further release.
I hope you've enjoyed reading this far. More to come in part two.
Further Reading:
The articles and links sections on the Procedural Content Generation wiki.
Posts
