Thursday 25 August 2011

Proceduralism: Part Eight (Content)

[You'll probably want to read the original article series that inspired this follow up, then start with parts one, two, three, four, five, six and seven of this series.]
What do I mean by content?

This is one of the foundational ideas of procedural content generation: that there is something we can generate procedurally which has an impact on game play. From the PCG wiki:

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. This wiki uses the term procedural content generation as opposed 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: procedural content generation should ensure that from a few parameters, a large number of possible types of content can be generated.
When I wrote the original Death of the Level Designer article series I set up PCG in direct opposition to PG, but they can clearly be seen as a continuum: dynamic lights and other traditional procedural generation techniques don't affect your ability to play the game until they do (see e.g. the flashlight in Doom, HDR bloom blinding you, trying to snipe through procedurally textured grass and so on).

Here I'm going to be more specific about my use of the word content: I'm going to define it in opposition to what I referred to as architecture in part six. Architecture is when you generate something procedurally and then try to fit game play to it, content is when you generate something procedurally for only game plays sake, and then let the player try to fit meaning to it.

[Edit to add: I'm using the word content in two different ways. As the C in PCG, content includes architecture, but I think it is relatively uninteresting. Topology is more interesting, but if you're just designing a maze for mazes sake: because you're game is set in a labyrinth for instance, then it doesn't help much. A better example would be buildings. If your building interiors are designed primarily to look like real building interiors, it is architecture, but if they're primarily designed to have waist high cover and door ways you can hide behind, it is 'content' driven in the way I'm defining in this article.]

A concrete example should help you. Later versions of Zangband (an Angband variant) feature a procedurally generated wilderness. Briefly, the wilderness map is a 2d array where each cell has three values: law, population and height, where each value is generated using Perlin noise and then normalised to guarantee that extremes of each value exist somewhere in the wilderness. The actual terrain selected for each grid location in the map array is selected from a 3d Whittaker diagram (basically a way of choosing a terrain type where adjacent values are usually similar, but with boundaries between terrain), where each axis is the law, population and height value. Each grid location is subdivided into a 16x16 map array where individual terrain features are generated as defined by the terrain in the Whittaker diagram - sparse trees, grass and occasional pools of water in savannah terrain for instance.

Zangband terrain looks beautiful, and natural up close, but has no bearing to any real world situation because the values used to pick terrain have no relationship to reality. Law is the (inverse) difficulty level of monsters generated in the terrain, population is the frequency of said monsters, and height is a randomiser to ensure that there's sufficient variety in terrain of similar population and law values (remember, the Zangband map is a 2d array), with a value picked for sea level so that a certain percentage of the map is water. High population are converted to towns and cities, high population, high law areas are fields, and low law areas include more dangerous terrain types like pools of acid and lava to complement the increased difficulty of monsters in those regions.

The Zangband procedural generation is, with the exception of height, a content-based PCG system. There is a direct relationship between terrain and the difficulty of the region, which the player can discover, with some explicit linking to player preconceptions (pools of lava), and some less direct linkages (are snowy forests more difficult, or simply at higher altitudes?).

While I said the values used to generate this terrain have no bearing on reality, the player is going to make sufficient meaningful connections between terrain and reality when they play the game. This is possible because the fine grade scale of the game looks plausible: everywhere the player looks appears that it might correspond to something in reality, so the player doesn't notice that the macro scale is nonsensical: actually not nonsensical, but generated completely around game play requirements, instead of ensuring the game matches an approximation of the real world.

While Zangband's wilderness generation code is elegant it doesn't play terribly well in its current form. There's no hard barriers (except for city walls) so it is very easy to move from safe terrain to deadly terrain without recognising the significance of the change, and the destinations you are looking for (dungeons) are sparsely populated because of a design decision to have different dungeon types without enough variety in what can occur in each dungeon. Both those problems can be fixed: one of the first posts for this blog is about wilderness generation using Voronoi diagrams where I propose generating the wilderness more as an undirected graph from randomly generated points on a plane, where some edges are eliminated from the Delaunay triangulation by putting up barriers, and some points are filled with untraversable terrain (mountains, seas, lava) while ensuring that all traversable nodes remain connected.

And I've written about how to make dungeons interesting in the Unangband Dungeon Generation article series: by subdividing the dungeon into one or more 'ecologies' of different but related monster collections which are used as selection lists for what monsters should exist here, and then decorates the dungeon rooms with randomly selected items and terrain types biased towards those which are related the most powerful monster in the dungeon ecology. The assumption here is that the player wants information about the most important thing on the current dungeon level - the most powerful monster that they are going to face, and so ecologies and decorations are selected which relate to some feature of that monster - if it breathes fire, the ecology may have other fire breathers and there may be burn marks on walls and floor and trees, if it is evil, there may be evil monsters and blood spattered furnishings, if it summons wolves, there will be at least one type of wolf available to choose from.

The correlations if you see an orc are only weak: you might be seeing it because the boss was an orc, and the ecology was partially filled with 'orc' monsters, or because the boss was an evil priest and the ecology had 'evil' monsters, or because the boss was a black dragon and it was a black orc (matching on names, instead of creature flags). Each ecology could be built from several such matches so you have multiple hints (and to ensure more variety); similarly the dungeon features chosen were heavily biased (5:1) or (10:1) to pick a feature with a similar match process, but could always pick a random one instead.

This ends up with a biased randomness, where you are being fed enough clues and enough noise that while you think something is going on behind the scenes, you are never quite sure if each piece of information in isolation is relevant. Information is a commodity when it comes to procedural content, but also a litmus test: it's not procedural if it can be spoiled.

The breakthrough in designing this came when I realised that there should be multiple ecologies on a level - with boundaries between each ecology which were filled with weaker related monsters, and that the architecture of the level (huge hallways, narrow burrows, natural caves) could be independent of what was filling it. Prior to those two conclusions, levels had ended up boring, but with multiple overlapping themes the dungeon became a lot more interesting. (For instance, Terraria has three axis in which themes overlap: depth, type of rock, and the presence of water or lava.)

That's because biased randomness was necessary but insufficient: you also require juxtapositions - where something unexpected occurs the player is forced to come up with a way to rationalize it. People are good at telling stories: the positioning of an arrow trap, a skeleton and a snake in Spelunky may be read as the dramatic death of a former explorer, whereas each of these elements separately may lack this meaning.

The big weakness with this biased randomness + juxtaposition approach to creating interesting content (and the simulate everything approach of Dwarf Fortress) is that you need a lot of content to make it interesting because otherwise you never have enough possible combinations to create any significant meaning. Luckily the total cost of creating a new creature in Unangband is incredibly low, somewhat more so for the complicated raw format that Dwarf Fortress uses, but compared to a 3d model (or in some instances a 2d sprite), it pales into insignificance.

Where the advantage is in the marginal cost: the cost to add an extra creature is generally fixed for a procedurally generated environment because once the rules are in place you can generate an infinite number of new levels; whereas in a hand-designed environment you have to potentially change every single level by hand if you should change an assumption about how a creature moves or the player acts, and as the total playable space goes up, the cost of additional content in that space goes up even faster. Procedural generation is how Terraria has been able to add so much content since release.

It is possible to combine procedural and hand-designed content without requiring a huge overhead of content types, by creating vignettes (small scenes) of artist created content which can be inserted into a larger procedural space. Some procedural generation systems consist of nothing but templates of hand-built scenes combined in such a way they can fit together. To make them effective, the vignette should have some random content so that it remains unpredictable when it is encountered over multiple playthroughs, as well as some interior space where the theme of the larger procedural area around them can break through (rather than merely restricting the template to a single theme). Part of the genius of Spelunky is that it consists of pieces of small platforming 'beats' combined together in a way that is only perceptible after multiple play throughs (Darius Kazemi suggests about 500 or so). I would also suggest considering adding bread crumbs of content which can be procedurally placed in the path leading to the vignette to help further integrate the template and the wider level.

Unangband does one better in that it has a room generator that is deliberately designed to create interesting rooms by placing content about the room in a combination of patterns and random placement. Briefly, two overlapping rectangles are created, and then content is placed in either the north, south, east, west or intersection of the two rectangles while a description of the room is created using a Markov chain. The tableau that is created can mimic player actions: bodies and blood can be scattered around the room in a manner similar to the consequences of player combat - creating additional resonance and meaning. More games could benefit from the procedural placement of the detritus of fire fights and assassinations.

Another piece of the content puzzle is progression. I've referred to increasing difficulty level already, but it needs to be stated that increasing reward levels are equally important. You can be sure that any newly generated weapons or treasures are going to be interesting for the player by ensuring that they will be more powerful than what the player has already found (give or take some random variance). Similarly, more challenging monsters are inherently interesting, to a point. To avoid the treadmill of more powerful items + more powerful monsters feeling like Ground hog day you should also expand the range of permitted behaviours: firstly by introducing them singly (ranged attacks, alternative movement) and then in combination.

The final piece of the puzzle is making sure your content is porous and well connected. This allows the player to find the optimal difficulty level for the way they want to play, and to move to freshly generated spaces when the content they have already encountered is exhausted. Terraria does this by allowing a new world to be generated at any time, Angband by allowing new levels to be created on the fly and so on.

But increasingly, developers aren't just relying on the player to find and create interesting content in procedural games, they're inventing methods that rely on simulating player wants and needs. The AI director in Left4Dead and Dark Spore is the best known example, but there are a number of others, and the most promising avenue of new research into procedural generation techniques. And I'll be looking at those in part nine.


Nick said...

Very interesting - I'm just in the process of designing new FAangband wilderness. Basic plan is:
1. A whole bunch of regions, each knowing which other ones abut it;
2. Each region has a (predefined) basic map of the types of terrain in it;
3. Actual wilderness is generated randomly, and a chunk of it around the player is retained, but it ages off as the player moves away and gets regenerated if they go back.

I'm also going to have some vignettes, but only a fairly small number (20 odd), that will always appear.

The main reason for these particular choices is that the wilderness is based on the existing Beleriand map, and the vignettes are significant locations (like Gondolin).

Rune Skovbo Johansen said...

Interesting article, but I must admit I'm still a bit confused about your various definitions and stances.

Do you mean that the design of the topology of a space can be either Architecture or PCG, depending on whether the guiding principles are looks or gameplay respectively? Or do you mean that topology is always Architecture and PCG is the stuff that is placed "within that space"?

If the former - "topology is only PCG if it's designed for gameplay" - then I'd say that maze algorithm design, as I'm using it, is primarily PCG. If you mean the latter - "topology is Architecture and not PCG" - then I'd disagree and argue that in many cases the topology of an area together with the things found within that topology together form the gameplay, and that in some cases it's not possible at all to separate the topology out as something separate because they're deeply intertwined. I'm essentially disagreeing with this statement from your previous article "It is the contents of these generated spaces that is the most important part of procedural generation".

To take a few examples: I place rewards at dead ends, so control of how many dead ends there are, how long they are, and which hazards might be along the way is driven by gameplay design. Similarly, how many loops to form in a maze and their placement can affect how easy or hard it might be to flee from an enemy, or chase one and trap it in a dead end. The topology the player and enemy moves around in is as essential to this as the properties of the player and enemy themselves.

And besides from all that, exploration of a space is a form of gameplay too. Look at a game like Knytt Stories. Aside from occasional challenges, large parts of the game have virtually no challenge and consist only of 1) A certain traversable topology and 2) Beautiful and distinct scenery. For a certain type of gamers, the exploration of an novel space is interesting in itself. When combined with a requirement to build up an understanding of the macro topology in the game in order to progress, this is a form of gameplay in itself.

The line between Architecture (even the "for looks, not for gameplay" part of it) and PCG then becomes blurry when realizing that an important part of the sensation of exploration is linked together with things such as interesting looks and by different areas having distinct visual and topological features - the very things you called out as "not PCG".

Andrew Doull said...

I knew this would get confusing because I'm using content in two different ways: the C in PCG in general, and the content term I'm using for this article.

The C in PCG content includes architecture, but I think it is relatively uninteresting. Topology is more interesting, but if you're just designing a maze for mazes sake: because you're game is set in a labyrinth for instance, then it doesn't help much. A better example would be buildings. If your building interiors are designed primarily to look like real building interiors, it is architecture, but if they're primarily designed to have waist high cover and door ways you can hide behind, it is 'content' driven in the way I'm defining in this article.

The maze example you give is content driven. There's no maze-like platformers in real life.

Dan Kline said...

This is... awesome.

My new definitive reference on how to create PCG spaces. Lots of techniques to investigate too. Putting the academics behind things I was doing ad hoc.

Thanks. This is one of the best pieces I've read all year. I could read 10 more posts on this sub-topic.

PS next, maybe the impacts of various PCG axes? You briefly touch on how overlap makes them better, but I'd love to drill into detail on what examples work best/worst and why.

Andrew Doull said...

Dan: Thanks.

The axes you select entirely depend on the space you're generating. One is going to be difficulty level in most implementations - Zangband splits this into two as I mentioned, but you could choose almost anything provided it is game play related (plus some noise). In fact, they don't need to be a continuous axis: Zangband wilderness does this because you don't expect to see large discontinuities in natural spaces. In Unangband, I identified that the pillars either side of a corridor exit could be varied procedurally (as well as spacing similar pillars along the corridor) and then pick an appropriate decoration for each room. Of course you need some non-decorated rooms so you can present multiple entrance types if that room is intersected by multiple corridors.

If you can overlap, you should: for instance, you might decide to expand Zangband's behaviour by having piles of skulls appear whenever the derivate (slope) of the law level exceeds a certain amount. That'd be a great way of letting the player know they were moving into or out of danger quickly, and would mean you could potentially have skulls in jungle, fields, snowy forests etc.

Andrew Doull said...

s/derivate/derivative :)

Of course, this leads to lots of experimentation and tuning of values to get things right. That is another big risk, because these systems aren't tested and well understood the way that a lot of existing procedural generation techniques are.

Rune Skovbo Johansen said...

Okay, so you mean that design of the topology of a space can be either Architecture or Content, depending on whether the guiding principles are looks or gameplay respectively.

That's a good distinction to make and be aware of, but I'd be vary to call the "for looks" side for "Architecture". Real world architects of profession would tell you that architecture is driven by function, not just making things pretty looking.

The utility you design a space for in a game may be completely different from the utility you'd design a similar looking space for in the real world, but nevertheless the word "Architecture" has inherit connotations to utility based design, which to me in a game design context would be more about designing gameplay than making things look pretty.

Maybe we can find a better word to describe topology and looks which is not driven by gameplay design?