Not the key

This opinion piece on the Zelda series elegantly summarises why I don't think a 'procedural Zelda' will ever be interesting.

Brogue 1.5 released

I seldom mention other roguelikes being released, but I think this one is a little special. We recently discussed Brogue on Roguelike Radio and the first line of the Brogue 1.5 change log caught my eye.

Dungeons now include interactive “quest rooms,” which include lock-
and-key puzzles, collapsing/flooding terrain, hidden items, elaborate
traps, challenges, boss monsters and more. 

I asked Pender the obvious question 'How random are these? Will you get the same lock and key puzzle in the same room every time?'. His response has got me genuinely excited:

Pretty random, and definitely not. The level geography is generated
randomly, and then the quest room function takes over, picks a quest
room type (of which there are currently 17, defined by the data in a
master blueprints table) and scans the level to find discrete areas
that meet certain requirements of that quest room -- e.g. a dead-end
area of certain size range that is dominated by a single chokepoint
cell. Then it adapts that area to serve as that kind of quest room.  

He goes on to describe a nifty flood trap (that you may want to avoid reading to not spoil yourself) which is completely dynamically generated and triggered when you get a key from the centre of the room. And the puzzles can have dependencies on each other:

So the key that you take from the room, assuming you escape, will be
used to unlock a door elsewhere on the level. These locked rooms can
be nested within each other, as can the rooms that guard the keys, and
it is always possible to unlock them all in a single game

For the full explanation, change log and download links, see the Google groups thread.

Another response

I thought I was going to use this in the last Proceduralism article, but didn't so I'd better highlight it here. Rune Skovbo Johansen has written an excellent response to my Proceduralism article on architecture: Forcing Structure in Procedural Spaces. I highly recommend it as well as following his blog if you're not already.

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.

Proceduralism: Part Seven (Education)

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

I was going to be talking about content, but I think there's an important point that is worth underlining now, especially seeing as the previous post ruffled a few feathers.

One of the key challenges about procedural content generation is that so much of it is 'intuitive'. Not intuitive in the sense that it is easy to understand, but intuitive in the sense that you have to use your intuition to figure out what works and what doesn't work.

You will sit for hours, watching your algorithms generate content over and over, tweaking the parameters until you are satisfied with the outcome. It is an incredibly powerful feeling, like being a god in some sense, in that you are literally creating (and destroying) worlds with the click of a button or invocation of the command line. Even the smallest change can butterfly into unintended consequences or beauty, and there are a surprising number of times where accidents turn into final implementation. My favourite is the erosion simulation from Tribal Trouble, where a thermal erosion algorithm failed to produce the desired results, until the sign was reversed on the equation being used - turning a sophisticated model into a nonsensical result which happened to look better.

I've coined what I call Doull's Law: 'Any time saved using procedural generation will be wasted watching the resulting screen saver', to try to capture at least the amount of time this takes, if not the power of this idea.

The consequence of this centrality of intuition, is that you have to be told the story of developing a PCG algorithm, instead of just seeing the final code, in order to understand what was done and why. Projects that describe the process of development like Project Frontier, Procedural World, rune | vision, Making Worlds, Procedural Planets, Dungeon League, Polygon Map Generation, Infinity: the Quest for Earth, L.o.V.E. and Spore and all the other creation stories are incredibly important: not just as beautiful repositories of code and images and ideas, but as foundational documents to their procedural worlds.

And I believe, fundamentally, why procedural generation has never become mainstream, is that it takes time, especially time spent coding, to develop this procedural literacy. If you look at, for instance, the Braving Procedural Generation thread on TIGsource, you see variations on the same, simple cellular automata cave generation over and over, because each person who falls in love with PCG has to go through the same learning process themselves to try to discover this intuition.

That is why I set up the PCG wiki [1]- to try to improve the overall literacy in this field. And the feedback to the survey I'm running at the moment has been incredibly positive, but almost everyone feels like they don't know enough to contribute back. My vision ultimately is to have an online PCG paintbox on the wiki, that'll let you explore cellular automata, and height maps, and fire propagation and so on, all in your browser so you can experience this feeling without coding - I just don't have time to create such a beast.

Back on track in part eight.

[1] That and I needed a bibliography of PCG.

[Edit to add: I know we'll have achieved that level of literacy when we start talking about a Cepero nave, or Young trees. At the moment all we have is Perlin noise, which is a bit high frequency for my liking :) ]

Proceduralism: Part Six (Architecture)

[You'll probably want to read the original article series that inspired this follow up, then start with parts one, two, three, four and five of this series.]

Edge Magazine recently featured an article, Building Worlds with a Single Click, which highlighted and praised two exciting new projects by independent developers: Project Frontier by Shamus Young and Procedural World by Miguel Cepero, both of which feature beautiful procedurally generated worlds.

The thing is, we've got very good at building procedural worlds - so good that virtually every example uses the same small underlying set of well understood systems: noise, L-system based architecture, Whittaker diagrams and so on that even a single programmer working in their spare time can implement. Just to pick a few featured in the World Building page on the PCG wiki: Making Worlds, Procedural Planets, Dungeon League, Polygon Map Generation. And of course, there's Infinity: the Quest for Earth, L.o.V.E. and Spore; all of which feature incredibly detailed environments created by incredibly talented and smart programmers.

And all these amazing worlds? Almost everyone is focused on building these curate's eggs - which, if they eventually end up being released as a game, become a disappointing, empty and lifeless one.

[Edit: Miguel Cepero has responded to this post, and quite rightly points out that the above statement is not a nice thing to say, specifically when his and Shamus Young's project should not be judged on this basis as they have not been released. I would like to apologise for making this generalisation, which the article in Edge magazine points out is the big challenge that all these projects face.]

Does almost all procedural generation amount to, as John Carmack puts it, is "a really crappy form of data compression"?

My procedural spider senses tingle as soon as I see a procedural generation system that uses one of the following two approaches:

1. Mazes (and by extension BSP-trees)
2. Height maps

because I've yet to play a game where I've exclaimed 'Wow, what a great height map' (except Populous, but we'll get to that) and the pleasure of solving a maze isn't the same as the pain of having to play through one.

I've also seen a rise in recent suggestions and several implementations of Metroid-style procedural generation featuring gated lock-and-key puzzles to partition a map, on the assumption that being forced to traverse through a non-linear space looking for a key is some how interesting. This is putting the cart before the horse: Metroid (and Zelda) use this technique to force the player to explore an already interesting (and hand-designed) location, not because looking for a key is itself challenging. The lock-and-key puzzle is merely a dressed up fed ex quest where you're not told the location of the package you have to deliver (or worse, you stumble across the package without knowing its destination address).

When we talk about architecture in game play, we don't think of buildings and naves and antechambers: we refer to choke points, and cover, and objectives. The topology of the space is much more important than its aesthetic or fidelity. The most successful (and perhaps only successful) procedurally generated game spaces so far are all based on Rogue, with its simple room and corridor design.

With a room and corridor design we get four important features:

1. Corridors - which act as natural choke points at each end, and cover if you are in them
2. Convex shapes - spaces where you can see everything in the space from everywhere else
3. Concave shapes - spaces where some space is hidden from another (more cover)
4. Loops - which allow you a safe haven by traversing the loop to recover when chased by enemies of the same speed or slower

Elite, the other arguably successful procedurally generated game space, remains interesting because it is a procedural objective generator. Here you are searching for trade routes between high tech industrial and low tech agricultural worlds: the topology is interesting only because every edge is a potential goal.

Populous, Dwarf Fortress, Minecraft and Terraria all cheat procedural generation in two important ways: they allow you to modify the topology of the space and they encourage you to make interesting content in that space to which you become attached. An uninteresting dead end can be transformed into a useful corridor, or lit by a torch to mark that you've 'already been here' or mined for valuable ore. The procedural generation systems they use may make beautiful places, but it is the player's job to change them into interesting spaces.

It helps in the case of Minecraft and Terraria that much of the procedurally generated spaces mimic Rogue's room and corridor layout. Strategy games generally generate a mix of the Rogue-type (open areas, choke points defined by inaccessible terrain) and generation of objectives through resource scattering (call this Civilisation-type PCG).

Even with a room-and-corridor design, the architecture, or more correctly topology of a space is insufficient to lead to great procedurally generated games. As I discovered when working on Unangband dungeon generation, it is the contents of these generated spaces that is the most important part of procedural generation. And that is why it is so frustrating to see developer after developer get trapped in architecture, distracted by beautiful world building, and not concentrating from the start on the creating content.

And I'll be discussing content in part seven.

Policing procedural

I started the PCG wiki with the intention of cataloguing games that featured procedural generation, because, frankly, there weren't that many when I started, unless you counted things like procedural textures.

I've not put enough effort into the endeavour, because, frankly, you start a wiki so that other people can help you out, and there's not been enough contributors to keep me motivated (Although thanks to everyone who has contributed) and it became more interesting to describe all the different procedural algorithms out there, than compile a large list of games largely duplicating information already in Wikipedia.

The last few days of catching up on my RSS feeds reveals that pretty much every second game that gets mentioned now features procedural content generation. On one level, I think 'we've won' but I'm not entirely confident I'm sure what that means. Let me think about it for a little while and I'll get back to you with some further thoughts.