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

(You'll want to read parts one, two , three and four first)

There's two kinds of hard - I'll call them depth and complexity.

Depth is similar to what I think Dwarf Fortress does for it's random world generation - it requires that you come up with e.g. a list of every possible type of mineral, multiple 'layers' of level generation such as height, moisture, temperature and combine these all. The building blocks however are relatively simple - some kind of fractal subdivision, working out which combination of height, vegetation, temperature etc result in plains, swamps and so on.

Complexity includes problems however that there is no possible solution for, or the solution cost rapidly increases out of bounds. Things like the Travelling Salesman problem, placing rooms and corridors in some kind of ordering, etc. Placing rivers falls in this scheme - you have to keep trying and abort if the river doesn't reach the sea in most naive implementation of rivers for instance.

To compare the two, most naive AI routines are complex rather than deep. For instance, in chess, it is complex to check for every possible move as the combination of moves grows so quickly, so deep solutions such as having a 'book' of moves are required.

Dwarf Fortress achieves the depth problem probably better than anyone else. But I can't think of anyone coming up with complex solutions for procedural content generation. For instance, in AI, the 'complex' solutions are always 5 years away, as I mentioned, but they seem to be getting closer, and AI becoming a little smarter.

Listening to Tarn Adams' recent interview with Geek Nights, he's anticipating that plot like game behaviour will emerge the lower level rules in Dwarf Fortress. I suspect this will, because he has enough depth in the game to support it. But I also suspect that very few other people, particularly commercial developers are going to want to spend the time coming up with as deep games. (S.T.A.L.K.E.R. is on the outer edges of 'deep' game behaviour, and it took six years to develop). So the 'short cut' is to come up with a procedural content generation system for game plots / game narrative to try to get replayability to another 'level'.

Most responses to earlier parts of this article have focused on procedural content generation being equivalent to randomly generating game levels or game worlds. I agree that this is an important area to focus on, and something that we'll see increasingly used in commercial games. But I also would argue that these techniques are mostly 'solved' and are therefore 'uninteresting'. In particular, most games which procedurally generate '3D' maps are really just generating a 2d surface e.g. a height field, and those that are 3d are mostly done through fractal subdivision, which while an interesting field of study, has been used extensively.

The one area that random map generation is missing complex 3d topology generation: and no game is currently doing this. Dwarf Fortress doesn't generate the fortresses for you - it still relies on human intelligence to go through the process of placing tunnels and building bridges and towers. When a game is capable of procedurally generating maps of the complexity of Half-Life 2, S.T.A.L.K.E.R., Minerva or any other modern FPS, then PCG for random map generation will be completely 'solved'.

And the reason that this hasn't been done is that complex 3d topology is a complex problem as opposed to a deep problem. 3d space with gravity is immediately an ordered space, and therefore requires that map connectivity be checked as a part of the generation process. Since connectivity cannot be guaranteed, the map generation may have to throw away randomly generated maps and you immediately move into the bounds of the halting problem - you can no longer prove the PCG algorithm will ever complete, for whichever algorithm you choose. (To clarify: the issue is not proving an individual map is disconnected, it's ensuring that you don't generate an infinite number of disconnected maps in succession).

In addition, complex 3d topology highlights some significant human perceptual issues - particularly the fact that we are biased against looking up. I suspect that any PCG which generates complex 3d topology will have to include an expert system that constrains the types of maps created. Constraints will include techniques to encourage the player to look up in the instance where there is a vertical element in the map, ensuring that gaps in the map that the player has to traverse are jumpable, tunnels are at least the player unit size and so on.

The expert system may act as a 'generator' rather than a 'constrainer' - these are analogous to 'wall-adder' vs. 'passage carvers' in maze generation, in the sense that the 'generator' may add features to the map that are consistent of a set of rules such as lily pads on a lake surface that the player can jump across.

It may well be that it is not ever possible to create a complex 3d topology procedural content generator that is good enough to be acceptable. I believe it will require extensive use of user mediated content techniques to get right, particularly for multi-player maps. Tools such as heat maps, as demonstrated in Valve's Half-Life: Episode 2 and Bungie's Halo 3, are already used for high-level analysis, and could be adapted for analysis with AI techniques such as neural networks and genetic algorithms. Similar AI techniques could potentially analyze every 3d map ever made and try to come up with a rule set of common features. These are not straightforward suggestions.

If we are stuck with hand made 3d maps, this only excludes 2 out of the 7 procedural content generation techniques I outlined previously. Again, S.T.A.L.K.E.R. is a great example of this - particularly in it's use of dynamic AI to ensure that the game-play within the maps keeps randomly changing. Even in Halo, where the AI is completely deterministic (after earlier experiments with random AI behaviour), there is still enough randomness from the player actions to ensure that the AI behaves differently every time encountered.

But I believe the real strength of procedural content generation will be seen in procedural generation of plot and narrative content. I'll discuss this in greater detail in part six.