The Saturday Paper: Dungeon Feng Shui

Level design is a tricky business. As you creep around Dunwall or drive through Liberty City, you’re influenced by the architecture, the passageways, the placement of other characters and the location of treasure. Handcrafted levels benefit from the attention and refinement of many human designers, while procedural systems sacrifice human intuition in exchange for limitless content and unpredictable outcome. It’s only natural to ask – can we have both? This week The Saturday Paper is about building procedural level designers that can work to the kinds of intelligent, flexible constraints that designers use every day.

We’re reading Fast Procedural Level Population With Playability Constraints, by Ian Horswill and Leif Foged. The paper describes a way of placing objects like enemies, items and treasure inside a level procedurally, using some clever programming and maths tricks to make sure certain rules are always followed. It lets you add quite loose rules like “make sure the player has to fight at least three monsters before they find any treasure”, and still get randomised, unpredictable level outputs. It deals with a few concepts that might be new to you, but stick with it – it’s got some great ideas.

First, a little background on constraint solving. Most of the time in programming you’re asking the computer to do things for you quite specifically – for instance, you might set the player’s health to be currentHealth + 20 if they pick up a health potion. There’s no ambiguity there. Sometimes it’s easier to describe what your answer looks like instead of writing it explicitly though. So you might say that when a player opens a chest, they receive an item, and that item is worth less than 100 gold. That’s a constraint. You’re not saying exactly what the item is, but you’re specifying something you want to be true about it. Special constraint solvers can take rules like this and find you all the results that satisfy them (maybe you have a list of possible items and values in this case). I wrote a post on something related (but not quite the same) a while back.

Constraints are interesting for procedural generation, because they let the designer very elegantly state rules (“This map need a waterfall.” “This village needs a graveyard next to a mine.”) and suddenly all the other details are left to randomly vary. It’s even been used to great effect in automated game design – but that’s a paper for another day.

Ian and Leif’s paper shows a system they built for describing a dungeon in a way that, given a dungeon map, allows constraint solvers to place objects and enemies and finish the dungeon design for them. With a few simple definitions their solver can look through the dungeon, work out the possible paths from start to finish, and make conclusions about which layouts would fit the rules the designer set for it. It’s really customisable, too. To show you how it works, let’s take a very simple example. Here’s our starting dungeon:

To simplify things, let’s assume each room has one thing in it – either a monster, some treasure, or a health pack. How do we want the dungeon to be laid out? A simple example (straight out of the paper) might be “Make sure the player can survive the dungeon.” It’s the first level, after all. To check this, the system will check every path that makes progress of some kind through the dungeon (so no doubling-back or going in circles), and score it based on however we define ‘survive’ mathematically. First, you define a way of scoring each possible room. Since we’re looking at survivability, we could score the rooms based on how much health you gain or lose by being in the room. So if the room has a monster in it, the score is -15. If the room has a health potion in it, the score is +20.

Now we can say what it means for the player to survive the dungeon. It means that for any path from the start to the finish, if you add up the score of each room in the path going along, you should never have a negative score. So the dungeon layout below works because the health potion bumps the player’s health up again before they fight the next monster:

It might seem obvious with my terrible example, but this can get quite tricky quite quickly. Here’s a non-linear example from a talk Ian and Leif gave (click to make it bigger):

You can see each room has many possible exits, with different strengths of monster (meaning there are even more choices for the constraint solver to place in each room). What’s great about this approach is that the constraints are very customisable. In my simple example, I said the entire level must be survivable. But we can ask for levels where only half of the paths through the level are survivable. Or levels that aren’t survivable at all (with maybe an additional constraint that says the player has to go into another level to find an item that makes them strong enough to get through).

If you can find a way to represent your constraint, the system can solve for it, so it’s not restricted to a few measly health points. In the paper there’s a great example about locks and keys – you can write constraints that make sure the keys are behind rooms with boss monsters in, or write ‘safety conditions’ that make sure the keys are never behind their own locked doors.

The idea of using constraints on paths through a dungeon – or any world where the play areas are cleanly arranged, like Metroidvania games – is really nice indeed. Approaching procedural content generation by specifying some starting blocks and letting a machine do the rest gives a great compromise between developer control and machine generation. It has scope to expand far beyond level design, too. I could see the same ideas being used to procedurally generate narratives, where paths are checked to ensure that the critical plot events occur in sequence, leaving the rest to be autogenerated. Or point-and-click adventures where the important plot items are guaranteed to be picked up by certain points in the game, but the puzzles in-between those points are selected from a database at random.

Constraint solving is a great tool that hasn’t yet caught on in a big way in procedural generation circles, but there are a lot of great researchers out there, like Ian and Leif, working to make it happen. It’s not just about offering easy customisation for game developers, though. It’s about providing easier ways for non-programmers to customise procedural systems. If you can work out how to express a simple rule or two, you can completely change the way a constraint-based procedural generator works. That’s exciting, and it could mean a lot for people trying to get into game development for the first time.

Where To Find More

Ian and Leif are really friendly people and hugely enthusiastic about their research. Leif developed the tool alongside a tech demo where the tool designed layouts for a proto-roguelike. They’ve given a GDC talk about the work, and been interviewed on Roguelike Radio and AIGameDev. In short – they’re very approachable, and they really want people to use their ideas! Constraint solving isn’t something you come across very often in game development, but if people are willing to take the plunge I think they’ll be excited by what they find. If you want to know more, but aren’t sure where to start, I really suggest getting in touch with them.

There are some finer details that really make the paper technically interesting that I don’t have the space to go into now – how do you deal with looping paths, for instance, or dead ends where the player doubles back on themselves? If you want to know more about constraint solving generally, I really like Adam Smith’s Map Generation Speedrun. Leif himself wrote a tutorial on how to build a constraint propagator in a weekend. Constraint solving isn’t the easiest jump to make if you’re used to everyday programming stuff, but it can be great fun, and the simplicity of the programs at least means there’s not too much to read (Adam writes engagingly too).

Thanks to Ian and Leif for their support this week, and Darren Grey for proofreading this article too. As ever, let me know what you think – @mtrc on Twitter or email mike@gamesbyangelina.org. And please so share this around if there are game developers you know who might be interested! It’s great to get research further out there to people who might not normally come across it. Thanks for reading.

Addendum I – Procedurally Generated Narratives

I first heard about The Kingsport Cases over on Reddit’s /r/gamedev, and I’ve been following it ever since. It’s a horror game with a procedurally generated cast and plot, using a really nice approach that I desperately want to see get implemented and released. If you’re a fan of cool ideas being developed into real games, you should take a look at their Kickstarter they recently put up and seriously consider funding them!

Addendum II – Play Games, Help Science

If you follow me on Twitter you’ll already know about Alex Zook’s experiment in adaptive games. If not, check this post I made earlier in the week for two links to some 2D shooter games. Playing them for ten minutes will help Alex’s research into adaptive games, and make some great science even more awesome by providing lots of lovely data to crunch and make pretty graphs out of. As we all know, graphs are the best bit of science, so if you’ve got some spare time this weekend do go and give it a play.