Monday, 14 January 2008

The Death of the Level Designer: Procedural Content Generation in Games - Part One

(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.

11 comments:

Andrew Doull said...

Hey everyone: I'm sure there's lots more procedural content generation links out there. Please post them as comments here, and I'll include them.

In particular, can anyone find a reference to the DOS game I'm thinking of?

Matt said...

Strategy games have been using random maps for ages.

Of particular note (at least to me) is the ability in Civilization 4 for users to be able to create their own scripts for map generation.

Here's a link to a forum dedicated to it: http://forums.civfanatics.com/forumdisplay.php?f=182

Andrew Doull said...

Which is why 2 of the examples I gave for random map generation are strategy games: Tribal Trouble and Dwarf Fortress. I'm not saying PCG is a new thing...

Thanks for the link - I've been meaning to give Civ IV a try and will definitely have a look at this.

jice said...

A very good article on procedural content :

http://www.gamasutra.com/features/20010302/oneil_01.htm

Blondie said...

Nice articles! I have to take exception to the statement that "procedural generation has yet to set the industry on fire". It already has, it's just that the fire has died down for a while. Back in the 80s, PCG was de rigeur, because we didn't have the disk space for huge map files, and it was a way to get streaming for free in a very small memory footprint. Games like Elite and Sundog have "been there done that". As the current trend towards large open world environments continues, studios will become overwhelmed by the requirements for authoring content (as we are on our current title :) ) and PCG will see a renaissance.

Abesto said...

Hi, I realize the question is quite old, but better later than never. A DOS game matching the description is Noctis. It has a sequel in the making, but it's current status is mostly unknown. Site:
anywhrebb.com.

Dan said...

I think Elite deserves a mention, as it was probably one of the earliest examples of procedural content generation that's well known.

Also daggerfall had 3D dungeons that where randomly generated. I'd be interested to know the exact technique employed. (just joined corridors and rooms - or something more complicated?)

I think the most exciting type of procedural content (for the programmer :D) is procedural story or plot. At a very basic level it's pretty easy to do.

GameConnoisseur said...

The FPS "Krieger" is (as far as I know) an excellent example of producedural content. It's only 98kb, but features more then one level of play.

You can download the beta here: http://www.fileplanet.com/154672/150000/fileinfo/Krieger-Beta

And read about it here: http://en.wikipedia.org/wiki/.kkrieger

/Anders

Togelius said...

Wow - this is the article I've been looking for for a long time! I started reading it just now, but then I saw that there's 7 parts of it... So I need to find a quieter day and sit down and read it all properly. Expect more comments.

In the meantime, may I shamelessly promote some blog posts about my own work in procedural content generation? It's quite original, as it's based on evolutionary computation and other computational intelligence algorithms.

The first one is about modelling driving behaviour and evolving racing tracks in car racing games:
http://togelius.blogspot.com/2008/12/automatic-game-design.html

The second, more recent one, is about evolving game rules using a learning-based fitness function:
http://togelius.blogspot.com/2007/08/how-better-ai-can-make-racing-games.html

Andrew Doull said...

Togelius: If we're advertising - get thee to the PCG wiki ( http://pcg.wikidot.com )... I would add references to your articles there, but I figure you'd be able to better do this yourself.

Togelius said...

Andrew: Added "Automatic Game Design" to the PCG wiki - not sure from which other articles to link it in, though.