Saturday, 19 January 2008

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.


Alexander (VaderSB) Samarin said...

Amazing series Andrew! Looking forward to the sixth part!

I must say that I totally agree with you that procedural plot generation will be a giant leap forward, but not dwelling into the details - generating _really interesting_ plot is much more difficult task than generating a level or a texture for example. The point is when you've got 100 textures of rusty metal generated - most of them will look ok. But 100 stories (plots) generated. What if most of them will be just boring? How can you detect these degenerate stories? :) You have to let computer to rate them? :) What will be the rules of ratings, what will be the algorithm? Damn, finding out if story is interesting or not is just really another thing than finding out a path on a level!
I wonder - do you believe that this thing is solvable without having a _real_ artificial intelligence? And if we imagine a future with real AI created - it will allow really new ways of development - I guess you won't need to mess with code then, you will talk with AI in human language instead and _he_ will make a final program for you, and so do he will rate stories.
Anyway, I've got too far :) Looking forward to your thoughts in Part 6!

Andrew Doull said...

Part six is up.

Kamineko said...

Hi. You seem to have used the same link for both the Bungie and Valve links about heat maps.

Shoku said...

There's a much better work around for this halting problem: don't generate maps you'll have to reject.

But we're rejecting them when they lack connectivity.

The solution is to make the connectivity first instead of carving it out later. Instead of this fractal origin business choose your areas and then generate the map around that.

We haven't got any trouble making mazes that have a guaranteed path through and it's not a particularly challenging task to require that points in the maze be reachable at certain times if you've got the connectivity mapped out beforehand.

But maybe you go into that in later articles :b