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.
Their talk at AIIDE was one of my favorites. I hadn’t imagined using a constraint solver in this way and it made me wonder how many other places such an approach would be useful.
Also, thanks for the Saturday Paper series!
Thank you for reading! I agree, it was a great talk and really nice to see constraint solving in PCG again.
The big issue I have with this kind of level generation is that by the time you get to a good enough “quantification” for acceptable results, it’ll need to run for a billion times or more to get a single level. That’s OK for pregeneration (just turn on a box and let it do the hard lifting for a few weeks), but can’t be done for actual runtime dungeon design.
I’m looking for somebody to invent a way to constructively make a dungeon that satisfies some constraints (probably something like an L-system then) and that does not attempt the non-polynomial try-and-check solutions. What’s the worst-case runtime if there’s an incompatible constraint?
I might be wrong but I don’t think this is really generate-and-test per se. Constraint solvers work in slightly different ways and are typically based on very fast and highly optimised SAT solvers. There are some statistics on solving times in the paper and they’re pretty zippy already.
I admit that if you’re doing large levels with lots of constraints it might be a little bit too slow for realtime. But that’s a new area of research – optimising this sort of thing and working out ways to do it more efficiently – and that’s exciting in its own right!
You’re right in that search algorithms, in the worst case, exhibit exponential time performance. Fortunately, the real issue isn’t that our problems are too hard. They just happen to be filled with arbitrary details and requirements that make hand-coding a custom algorithm for each of them simply out of the question.
This is where constraint solvers come in. It’s not about solving “hard” problems at all, which will never run efficiently due to NP-completeness issues (or worse). Instead, it’s about targeting “easy” problems where we’re interested in excluding obviously bad solutions rather than finding a single gem in a huge search space (thus we also can also bail on optimization in favor of satisfaction). Fortunately, PCG has a high density of problems that fit this description; these are the prime target for simple, home-grown constraint solvers that run in-engine, in real-time.
This blog is terrific: really cool ideas presented well. Downside is that some of the flies you’ll catch won’t know what to do with the honey… but I like hovering around it. I’m a writer, and I’d like to use this stuff to generate plot. When I want to practice certain elements of my prose, I don’t want to sit down and spin out a new plot each time, so I figure constraint solving and ASP would fit the bill. I’ll send something along if I ever get it working.
Thanks Michael and commenters — I was just on Red Blob for an hour the other day, Amit, reading about hex grids.