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.

Curation

I've been puttering about, updating parts of the PCG wiki and putting together a short survey to try to figure out why there's not more of a community involved in updating it (One observation: I was forgetting to approve membership requests. Sorry to anyone who applied and was waiting).

Coincidentally, I listened to a Moving Pixel podcast where the chaps from Critical Distance discuss the same problem I've been having: how to turn a list of interesting links into something with more structure and 'authority' (A word I'm wary of). At the moment, the PCG wiki is basically a big bunch of external links with a bit of structure, and I don't see myself having the time to do more than keep it vaguely up to date (Along with tricks like aggregating RSS feeds from various blog posts to make it look like it's being updated more frequently than it is).

[Edit to add: Craig Perko's Google plus comment on the same issue.]

So in one way, the wiki is no more useful than the Delicious procedural tag RSS feed.

And the wiki structure isn't quite right for what it needs to be. So I'm going to sketch out an idea and see if you have any suggestions as to whether anything else fits the bill.

Firstly, I need a tool, like Delicious, which does simple link aggregation, but in a way that is domain specific, so I and other wiki users can tag it with words like 'article', 'blog post' and so on, but also 'noise', 'maze', 'caves' which don't bring up every single 'blog post' in existence by someone using the same tool. Other than copy and paste, the wiki falls down here.

Then I need to be able to keep related links together on the same page. The way the Internet works at the moment, a blog post may spark follow up posts on Metafilter, reddit, various web forums and so on, which all make sense to group together, but will include their own original content.

Then it needs wiki style authoring over the top, along with discussion groups, rating systems similar to stack overflow and so on.

I can kind of hack this with the wiki currently, by having every 'external link' actually be another wiki page in front of the external link, but this is still missing Delicious style link tagging and is horribly clumsy.

This excludes all the problems with the current wiki (and wikis in general) having data handling (should year released = 1997 be metadata or tags?), dynamic templating and etc.

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.

Proceduralism: Part Three (What is Procedural?)

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

Alongside the attempt to define a taxonomy of procedural content, my other main goal for the PCG wiki was to list what games featured procedural content - expanding on the inadequate wikipedia entry to create a definitive go to guide if you were looking for a procedural fix. But this building this list has stumbled for two main reasons: a lack of time and contributors - which results in the majority of articles being stubs, with more polished entries where someone else has taken an interest, and a more fundamental problem with deciding whether a game is procedural or not.

But surely it should be clear whether a game is procedural? Take Elite - the canonical example of a procedural game, with an infinitely explorable universe generated from a starting seed. Elite is clearly procedural because of this infinite sandbox. Or is it?

It turns out the universe of Elite is in fact finite enough that it was possible for the founders to check the name of every planet to ensure that there were no curse words included in the final release. And if you are willing to accept a seeded universe but constant content as a starting definition for procedural, then is Eve Online procedural? What about Star Wars: Galaxies? Darwinia? Far Cry 2? Far Cry?

Well if Elite is not a good model to follow, then how about Rogue? Infinite, accessible dungeons - which implies accessibility to newly content is a prime requisite for procedurally generated games. But strategy games like Civilisation have had random maps almost as long as the strategy genre has been played on a computer, and listing every strategy game with a random map generator as a procedural game will be an enormous and potentially futile project.

So it's not simply a matter of random map generation, then how about other content like randomly varying the loot that you find. But that makes World of Warcraft as procedural as Borderlands and Left4Dead procedural because it dynamically mixes and matches zombie bodies to ensure variety in the horde.

But Left4Dead is procedural: because of the AI director, in the same way that Far Cry 2, but not the original Far Cry, is procedural because it has dynamic fire propagation. It's the emergence of interesting properties that makes a game procedural.

But this makes any game with a half-way adequate AI procedural, which is again not a useful definition from the point of view of building a wiki listing procedural games. And does a game like Deus Ex qualify as procedural because of the emergent property of using limpet mines to climb buildings? Maybe it is but Warren Spector didn't intend it that way.

We are left with two possible definitions which seem more robust but neither of which are ultimately satisfying: did the developer intend the game to be procedural, which leads to the problems of divining authorial intent, or is it procedural because I know procedural when I see it?

(I'll return to the matter of perspective later in this article series, but it is worthwhile noting that Minecraft feels more procedural than Populous because of the perspective the player sees the game from, in the same way that a first person shooter or platformer with random maps and AI feels more procedural than a top down strategy game with the same features. It is for this reason I've added a perspective category to games on the PCG wiki).

I want to avoid an argument about definitions for the moment, and try to look at some minimal examples of what we can mean by procedural. Take the following BASIC code:

10 PRINT HELLO WORLD
20 GOTO 10

Which if you run it, results as follows:

HELLO WORLD
HELLO WORLD
HELLO WORLD
...

The output of this code results in infinite content, and the code itself clearly defines a procedure for generating this content. But you and I both would have extreme difficulty in describing this as procedural content, because it is not very interesting.

What do I mean by interesting? That is the heart of whether a piece of content can be adequately described as procedural or not. If we just consider the output of an infinite number of HELLO WORLDS, we can see the content is not very interesting, because the underlying code required to generate this content is not particularly complex, and the result completely predictable.

But at the other extreme, apparently complete randomness isn't terribly complicated an algorithm either, such as this Python implementation of a multiple with carry random number generator shows. The output of this algorithm is too random for any human to detect the underlying pattern, while the pattern itself is compressible in a sense that true random numbers, such as thermal noise, are not.

The fact that a less than one page long algorithm can generate 'random' output as far as a person is concerned implies there is a not terribly complicated threshold past which someone is incapable of distinguishing an algorithm from random noise.

What fascinates me about procedural content is my belief that there another useful boundary between trivially predictable output and effectively random output - what I've called elsewhere biased randomness - that is randomness produced by an underlying discoverable rule set. That is not to say that randomness is uninteresting - given sufficient incentives, we can become horribly addicted to random output - but I think there is more value in exploring biased randomness than coming up with better ways to package completely random content in a compelling format.

You may be thinking here of the mathematical concept of 'chaos' - but while this may be a useful analogy, don't confuse the two. There are plenty of chaotic systems which can be easily comprehended by a person (the outcome just can't be predicted), and just as there are plenty of ordered systems which are similarly incomprehensible. Even the predictable behaviour of two body planetary motion was unknown until the recent past in terms of the overall human evolution of thought.

It is also likely the case that compelling biased randomness is even more complex than the algorithm required to implement effective randomly content - just in the same way that the real world is more complex a place than an aggregation of random elements. This will also be a challenge for biased randomness: justifying the additional time and expense above strictly random content.

So my answer to the question 'what is a procedural game?' is that the game presents a biased randomness where discovering the underlying rules is a necessary part of play. That doesn't help much when it comes to deciding what games should be in the wiki, but at least I have a set of criteria which feels more objective than those I outlined at the start of this article.

Whether the biased randomness in a game is interesting is a subjective exercise: one person's discoverable rule set is another person's fiat from the gods. But I don't believe this is an unsolvable problem: there are definite strategies to discovering whether something is interesting, and ways of dealing with the most common criticisms of procedural content generation. And the question of what people find interesting isn't just an issue for game design; with procedural content, it allows us to build a more precise model of the mind.

And I'll be talking about that in part four.

Question for Game Developer Conference attendees

Anyone at the GDC? I have a sneaking suspicion based on the increase in direct traffic that someone there mentioned the Procedural Content Generation wiki. It'd be good to know if there was a mention - even if it is just someone talking about procedural generation in general...

(And I'm going next year, come hell or high water. A single mention of fellow Australian Ben Abraham getting to sit down and chat to Clint Hocking was enough...)

The Canon of Procedural Games

While updating the PCG wiki today, I've come across the difficult notion of canon in procedural content generated games. I've flirted with this concept before, by defining games which are prototypically procedural, but in general I've tried to be inclusive rather than exclusive when it comes to including games in the PCG wiki.

I've hit a stumbling point writing up an article on adaptive difficulty - always a controversial point in games. I'll quote the whole article to saving you having to go to the original link:

Adaptive difficulty is the process of adjusting the game in reaction to the player. By spawning new enemies or powering up existing enemies if the player is progressing quickly through the game, or by decreasing the frequency and/or difficulty of existing enemies if the player appears to be having problems progressing, adaptive difficulty techniques attempt to create the 'optimal' game experience.

Classically, adaptive difficulty has been seen as a hard problem, requiring a level of artificial intelligence in the game to attempt to model the player to attempt to determine if they are finding the game easy or difficult.

However simpler RPG style mechanisms can also be seen as adaptive difficulty techniques. Allowing the player to level up by playing through additional easier content can ensure the player is able to grind their way through parts of the game in order to decrease the difficulty of sections of the game where the difficulty level increases. Paradoxically, adaptive difficulty techniques which increase the difficulty of the game by scaling up enemy strength have been fiercely resisted by RPG players, as can be seen by the negative reactions to the difficulty scaling in Oblivion.

Adaptive difficulty is not usually seen as a procedural content generation technique, but it has most of the features of such techniques. It could be seen as decreasing a game's randomness instead of increasing it which would make games which feature it without other PCG features to fall outside the 'canon' of PCG games.

Should I include games which have adaptive difficulty in the PCG wiki? There are plenty of examples of games which have adaptive difficulty and are procedural (Oblivion I've already mentioned, Left4Dead) but there are plenty of games which are not (SiN: Episodes). And I don't want to include every RPG, based on the argument I've made above.

The real question is not whether I should include these games, and the answer to that is probably not, but why? What good reason can I give to not include SiN: Episodes, for instance, as a procedural game?

Again, the randomness argument is the most plausible, but it is not completely convincing.

Convince me.

Randomized levels in Diablo III

One of the contributors to the PCG wiki just highlighted a link to Blizzard discussing randomized level generation in Diablo III. Unfortunately, a little light on the detail. I was hoping for more.

PCG Wiki Membership Drive

I'm probably not doing enough to promote it, but the Procedural Content Generation wiki has been growing in leaps and bounds. It has over 600 pages relating to procedural generation created by a hard working team of individuals dedicated to the vision of procedural content generation. It's also the number two spot for the search term 'procedural generation' in Google - with only the entry on procedural generation in Wikipedia ahead of it - with over 1600 visitors and over 6000 page views in the last 30 days. That's excluding any peaks caused by getting mentioned on aggregator sites like Metafilter, Digg, Slashdot or Boing Boing

And I want you to be part of the team.

Well, actually part of the community. One thing that hasn't taken off is the PCG forums - they're a little barren at the moment, and I really need to jump start this part of the site. So I was wondering if you could help out by doing the following:

1. Creating a wikidot account.
2. Joining the site.
3. Introducing yourself on the introduction thread in the forums.

Much appreciate in advance.

More Spore prototypes

Maxis continues to release Spore prototypes with very little fanfare at the rate of about two per week. The latest is WaterBoy - a dynamic fluid simulator on uneven terrain, and GonzagoGL - a more advanced and game-like prototype of the creature phase of the game than the earlier SPUG prototype delivered.

I've added these to the PCG Wiki but haven't had time to review any of them. Volunteers?

PCG Wiki To Do List

With the exception of this first paragraph, this post is a verbatim copy of the current to do list from the PCG Wiki. For those of you who are interested in helping out with the wiki, you'll also be interested in reading the examples page, which was the number one requested poll item. At the moment, of course, it's more of a how to page, but any feedback on how to improve this would be much appreciated.

Ongoing actions and maintenance

There is always an need to update the news items with anything procedurally related. Try to keep each news item to a brief sentence, starting with a single word linking to the external link that describes it, such as Interview with x or Preview of y. Replace x and y with the relevant link within the pcgwiki. Then, once there are more than about 10 items on the page, archive off the older news items to the more news page, which is intended as a reverse chronological list of all news items that have ever appeared on the wiki.

Any upcoming events should be added to the calendar, and have a separate event page created. To create an event page, Add a new page starting with event: and use the event template to describe the event. Any other important recurring dates, such as the release date for a historically significant PCG game, should have a day page created, starting with day: followed by the month space numeric date, such as 'day: august 8'. This will make the day appear in the Anniversary list at the bottom of the events page. To get access to the Google calendar, email [email protected].

The pcgwiki has yet to have a problem with spam, but feel free to check the recent changes and see if all the edits are valid.

To do list

The biggest to do list for the pcgwiki is to add and expand existing entries, particularly the games, software and code pages, particularly by adding code examples to the code pages for other people to follow. If you are not an adept coder, you could simply update an existing game entry to include additional information from wikipedia. Follow the examples to understand how to set up and edit the info boxes.

To discuss any items in the to do list below,

The following items are low-hanging fruit:

• Add the remaining games from the TIG Source Procedural Content Generation Competition. You'll want to go through the list of all 60 games including downloads.
• Expand on existing game entries by including more information in the info box and description fields. Have a look at the linked wikipedia entry for ideas.
• Expand on existing code entries by including more information in the info box and providing code examples. Have a look at the linked wikipedia entry for ideas.
• Expand on existing software by including more information in the info box. In particular, since many of these can be downloaded and played with, writing a review would be ideal.
• Start creating person entries.

The following items require more work and understanding of the wiki design:

• Many of the top menu entries are place holders pending a feature request allowing the module backlinks page to only list some backlinks.
• Investigate the use of categories instead of backlinks to automatically populate pages.
• Consider splitting the article and links pages up.

You'll also want to have a look at the bugs and quirks page for more issues.

Share a little Love

Rock, Paper, Shotgun's Jim Rossignol has pointed out that Eskil Steenberg has a blog, Quel Solaar, that if you are into procedural generation is well worth following. For those of you who don't recognise the name, he is one of those hero-developers who is writing a procedurally generated massively multiplayer game by themselves. I've linked to Love previously, but I recommend you bookmark his site for further perusal, even if it is just to stare in amazement at the beautiful in-game screenshots.

In other news, there has been a huge amount of development on the procedural game front. It seems like every A list game property is including some procedural generation these days (And even old returning favourites like Diablo III).

Here's a brief excerpt from the update I've just put on the procedural generation wiki:

June 29, 2008
Screen shots of Love

June 28, 2008

Comments by Jay Wilson, lead designer of Diablo III

June 27, 2008

Keynote by Chaim Gingold, former lead designer of Spore on Magic Crayon approach to design.

June 26, 2008

Video of game-play from Far Cry 2.

Rescue: The Beagles wins the TIGSource Procedural Generation Competition.

June 24, 2008

Interview of Lucy Bradshaw, executive producer of Spore.

Video of game-play from Left4Dead.

Interview of Gabe Newell on AI director in Left4Dead.

Conclusion to the TIG Source PCG Competition

The Independent Gaming Source procedural content generation competition has concluded: with approximately 49 completed entries. There's been no official announcement on the forums, but I've had a brief look at some of the entries. Rescue: The Beagles (pictured) has already been reviewed elsewhere, and Dyson looks intriguing (Edit: Also reviewed). I'll write up more as I play them.

This is a brief help-wanted request as well. I'm slowly writing up the finished entries on the PCG Wiki. It'd be great if readers of this blog could help out by either:

1. Expanding on an existing entry I've already written, by downloading and playing the game and taking some screenshots.

2. Writing articles for entries I've not already written. If you create a new entry, precede the name by pcg-games: and you'll get the right template and it'll automatically appear in the appropriate game categories.

Thanks in advance.

Minesweeper vs. Solitaire

I was going to write this another day (heh), but I've been preempted by an article in Slate magazine. Amidst the procedurally generated games I listed on the PCG Wiki, I slipped in Minesweeper as a way of leading into a discussion about what constitutes a PCG game.

I was going to argue that Minesweeper is PCG, but Solitaire is not. The reason being that randomness is a necessary but not sufficient condition for a PCG game. What is important is biased randomness. Procedural content is about exploring a set of rules underlying a seemingly random system. I wanted to exclude a game I deemed 'sufficiently random' that was clearly mental junkfood to compare it to a more controversial position that Minesweeper is PCG.

Apparently though, Solitaire is not mental junkfood (supported by an intelligent comment on Slashdot. Now the world has turned upside down, you can return to your regular service).

So feel free to argue for either game as being PCG. And the consider, is Poker a procedurally generated game?

Boing Boing

Rob Beschizza of Boing Boing Gadgets has thoughtfully linked to the fledgling PCG Wiki. He's overstating the number of articles on the wiki already (I think he confused the visitors figure with the articles figure on the last wiki post I made). Many of the articles are stubs which link through to the relevant wikipedia entry, but I'm hoping that contributors (that means you, gentle reader) will fill out the details.

I also hope this isn't premature publicity: I want the wiki to be a long term resource, not a flash in the pan, and don't just want people to turn up, wander around and leave disappointed at the early state of the site.

What they want...

It's been about a week since I announced the Procedural Content Generation wiki, and it has had a few visitors already (350 or so) - thanks to whomever added the site to stumbleupon.com. When I first started, I expect the most popular parts of the site to be the list of articles on procedural content generation and related references but I should have known better. What it appears that people want is lists. Specifically, lists of what games feature procedural content. I've been adding to that list today to try to fill it out a bit, but I'm open to suggestions as to what is missing. I know the majority of roguelikes use procedural content generation, and you're welcome to create an account and add those in, but I don't want the wiki in general to replace the already excellent resource RogueBasin.

So what other games feature procedural content generation that I'm missing off the list? In particular, note that the game can have content generated procedurally in the level designer - it doesn't have to occur at run time. So any games featuring SpeedTree for instance are good candidates. But at the same time, I don't particularly want to include games that use procedural generation for things like graphics and textures.

Also, anyone particularly interested in cellular automata: there is definitely a place in the site for you.

Announcement: Procedural Content Generation Wiki

In what little free time I have at the moment, I've been busy.

A large number of people come to this site looking for information on procedural content generation, and while I'm happy to act as an unreliable source of advice, I know there are greater minds out there than my own. But there is also a gaping hole in the Internet where procedural content generation seems to fall through.

Therefore, I'd like to pre-announce the Procedural Content Generation wiki. This wiki is intended as a home for all things procedurally generated, and over the next few weeks I'll be building up a repository of links and articles that are less focused on what I think PCG is, and more on what the world at large does. You are invited to contribute to what is very much a bare bones project at the moment.

It's also a great opportunity to initiate more of a n-dimensional dialog with you the readers, that the comments section of this blog does not have the ideal design for. That's why in addition to the wiki at large, there is an extensive forums section which you are invited to join and start talking.

I'm always conscious of the balkanisation of the Internet, which is why the forums are intended for discussing about procedural content generation and not necessarily any game in particular. But you may find it as a refuge for the slightly older 8 bit generation, who remember X-Com, Elite and other gaming greats that used these techniques.