Thursday 18 August 2011

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.


Andrew Doull said...

I've deliberately ignored some of the exciting stuff happening in academia around e.g. rhythm based platforming for instance. I don't have the time to go into it in this post - which also explains why this isn't as smoothly written as some previous articles. Sorry.

VRBones said...

Sounds like a green light for levels designed by importance. I really need to get back to that ...

James McNeill said...

Ouch... I am working on a key-and-lock level generation thing right now. May have to rethink my priorities!

My current (as yet unimplemented) thinking for the key/lock gameplay is that you experience a fair chunk of the environment under one set of conditions. It's vital that in doing so you also see things that you cannot yet reach. Ideally you don't just see a locked door; you see something that you want (through a window, or on a viewscreen, or across a chasm).

When you get the key it allows access to the previously inaccessible regions, but ideally it also changes the experience of traversing the level as you retrace your steps. (The cheater way that we do this in the commercial games I've worked on is to just respawn a fresh batch of enemies in the visited areas. The experience isn't fundamentally different, but maybe it gives you a chance to exercise the new fire mode you picked up on your kill-o-blaster.)

My game's set in spacewrecks, so I'm thinking of keys in terms of things like controlling power, light, gravity, and air pressure. Or maybe there is sunlight coming from one direction and the space vampires (or whatever) don't like it as it shines through the gaping holes in the hull. And there is a control somewhere that allows you to rotate the ship (thus changing the impinging angle of the sunlight).

I've loved reading your ongoing series of series about proceduralism and your experiences developing Unangband. Keep it coming!

Andrew Doull said...

James: anna anthropy just posted some more insight into lock and key puzzles in Metroid and points out the original Metroid played a lot more like roguelikes.

Andrew Doull said...

Just a quick update to people who've already read this that I've amended the article to include an apology about some ill-judged generalisations I made in haste.

Amit said...

Some of the academic research I've seen was inspiring. The first time I saw key-and-lock level generation was in academic research. Other research wasn't interesting to me at all.

Many of the projects I work and share are for my own explorations, inspired by research or by a game I'm playing or by a conversation with a game developer. They're not necessarily something novel or groundbreaking or interesting to others. I find the best way to learn things is to do them, even if it's not the path recommended by others. When I learned to ride a bike it wasn't enough to be told what to do and not do; I had to try it myself. I feel the same way with many of the things I want to learn. I just have to try it, even if someone else already has.

A disagreement with the post: I think we're not very good at building procedural worlds. Yes, there are lots of pretty worlds but there's a lot more to a world than how it looks. I've love to see more people exploring how the worlds work and how the parts fit together.

However, as much as I want other people to explore things I'm personally interested in, I have to keep in mind that they're not doing their projects for me. They're doing it for themselves. And good for them! I'm glad people are trying things, even if other people have tried similar approaches, even if they're not exploring the topics I'd like to see explored. There are lots of good things that came out of projects I thought would never go anywhere. My discouraging them probably wouldn't have made things any better. I'm happy to see people writing and talking about things they're working on instead of keeping quiet.

nullpointer said...

Isnt this a bit like saying game based on just vehicle physics will probably be dull, or games based on just stats levelling will be boring. Procedural methods are just another tool in the box. Of course they can influence the direction of a design to a greater or lesser degree, but its just about how well they are integrated into a larger vision of game design. Minecraft doesnt actually do that much on top of its procedural core, it just makes its gameplay actively involve the procedural aspects of its world. I admit that just having 10 million similar castles to explore, or having thousands of similar islands isnt necessarily going to make a great game, but neither is having 100s of cars to drive or millionsof guns to use. Its what you do with them that counts. I think there are quite a few games based on procedural tech that are very successful and fun to play.
COncerning the many WIP procedural games, perhaps one of the issues is that the coding involved appeals to a specific mindset of programmers who are interested in the systems first and the game second. But a lot of the projects you mention are as much about research as they are games, and research is just as important imo.

Rune Skovbo Johansen said...

I agree with some points in this article but disagree that an interest in procedural generation based on keys and locks, mazes, or unlockable regions is "putting the cart before the horse". I also don't understand what you find superior about the rooms and corridors type of generation. It seems based on a very narrow view of what maze algorithms can be. I wrote a full length reply in my own blog here:

Andrew Doull said...

nullpointer: Of course. But your words would have a lot more weight if there was a corresponding plethora of PCG research on procedural puzzles, plots, AI director etc. Outside of academia, there is not. The attraction of beautiful worlds is too strong...

rune: That article's brilliant: a great read and defence - I was thinking specifically of your game when writing that lock and key puzzle paragraph :). If me quickly dashing off some thoughts about PCG without filling in all the blanks is going to get this quality of response I'm going to have to do it more often.

I'll comment more on your blog.

Rune Skovbo Johansen said...

Andrew: Thanks for the kind words! I wrote a reply to your comment on my own blog.

nullpointer said...

"nullpointer: Of course. But your words would have a lot more weight if there was a corresponding plethora of PCG research on procedural puzzles, plots, AI director etc. "

I disagree, I think that some of these things are already quite procedural, we just dont call them that. AI is full of emergent proceduralism and is vital for plenty of contemporary games. It could also be argued that many puzzle games, and strategy games are also procedural in erms of balancing of rules and outcomes. Just because they arent talked about in the same space as the 'pretty geometry' doesnt mean they arent part of a similar practice.