A Map Generation Speedrun with Answer Set Programming

There’s nothing really special about this map-looking thing, other than that you can’t get from the top-left corner to the bottom-right corner in less than 42 steps (I looks to take 56 or so). What is special here is how quickly we’re going to develop a flexible, style-ready generator for it. Set the clock for 50 lines-of-code, and let’s get started.

That’s right, we’re going to write this map generator right here in the blog post. If you want to follow along at home, download Clingo (a state-of-the-art answer set solver) and fire up your favorite text editor.

First up, let’s specify the parameters for our map generation task. If we want to create something like the example above, the figures of note are how wide/tall the map is and a specification of which lengths count as too short for our interest. Note the full stop at the end of each line — everything we type is a sentence that specifies a logical fact or rule.

#const width=21.
#const length=42.

Defining a symbol doesn’t trigger any magic. We have to use them somewhere else in our program.

dim(1..width).

Cool, this was is our first productive line. If you take the three lines above and pipe them into Clingo you’ll actually get some output. Unfortunately, all it will say is “dim(1) dim(2) dim(3) … dim(21)”. We told it that the numbers 1 through 21 are dimension values (to be used later), and it believed us and echoed this back at us. We didn’t call any sort of library function here, what we did is more like building a data structure. You can read “dim(21)” as if it were “<dim>21</dim>” in XML-land (i.e. just some data).

This next one does something useful, I promise. It’s what answer set programming people call a choice rule.

{ solid(X,Y) :dim(X) :dim(Y) }.

It says if you form a collection of terms named “solid” (representing which areas of our map you can walk on) by considering all possible assignments for X and Y from the dimension values, any number of those can be considered true facts in our imaginary world. Feeding Clingo just these four lines together, you’d be surprised to learn that we’ve got a functional (but tasteless) map generator! Er, it’s more of a nonsense 2D barcode generator, but let’s continue.

Clingo’s output now specifies facts like “solid(5,6) solid(5,7) solid(5,8)”. This set of things that are true (answer sets, for which the programming paradigm is named) can be piped into some straightforward Python program for rendering the ascii-art figure that opened the post, or, for those who can decode The Matrix  from glowing symbols in the terminal, it can be read directly and imagined for now.

To take some of these other concepts like reachability and path lengths out of our imagination and into the code, we need to lay down some background information about our grid-world.

start(1,1).
finish(width,width).
step(0,-1 ;; 0,1 ;; 1,0 ;; -1,0).

Now that we’ve nailed down our start and finish reference points along with what counts as a single step on the grid (i.e. cardinal directions, no diagonals), we can finally start building up some logical rules instead of just typing in obvious facts.

reachable(X,Y) :- start(X,Y), solid(X,Y).

That was an obvious rule – some position is reachable if it happens to be the starting location and the ground there is actually solid. You can imagine the if-operator “:-“ as kind of like a little left-pointing implication arrow with its pointy head snipped off (it says the left side is true if the right side is true). Sometimes it’s called the neck because it connects the head of a rule to its body. Over in the body of the rule, the comma between the two terms forms a conjunction – it means “and”.

Let’s explain how you can reach a new location by taking a step from some other reachable location.

reachable(NX,NY) :-
  reachable(X,Y),
  step(DX,DY),
  NX = X + DX,
  NY = Y + DY,
  solid(NX,NY).

We’re almost ready to cash out here, we just need to explain how reaching the finish counts as a complete path.

complete :- finish(X,Y), reachable(X,Y).

If you take all of the above, pipe it into Clingo with the arguments “-n 0” (which means generate all solutions), eventually you’ll see some answer sets scroll by which include “complete” in them (meaning there really was a start-to-finish path). I hope you didn’t actually do that, however, because with 2^(21*21) = 5.6e132 possible selections for which cells are solid (which is itself 10^52 times greater than the estimated number of protons in the observable universe) you could be waiting quite a while to see something interesting.

To zoom in on the well-beyond-astronomical number of maps that are guaranteed to be connected, let’s add an integrity constraint.

:- not complete.

Integrity constraints are like rules with no head. Or maybe they are like rules with heads that are so unspeakably horrible that we dare not write them. Either way, this constraint says that if a candidate map does not contain the “complete” fact, we aren’t interested in it (and thus the copy of the universe that contains it should be annihilated). Pipe our new program into Clingo with “-n 0” again and now you’ll get a near-inexhaustible supply of maps with start-finish connectivity. I say near-inexhaustible because answer set solvers really will terminate (theoretically guaranteed!) once they’ve enumerated all possible solutions. It’s just that we usually lose interest after the first five or so. Besides, the enumeration algorithm is a doubly-exponential beast in the worst case, we’d best keep moving along.

The space of corner-connected maps has some pretty lame maps in it. The all-solid map happens to fit all of our rules so far, so let’s find a way to reject (with another integrity constraint) maps for which the two corners are too close. We know the finish is too close if someone could walk there in a number of turns less than that “length” constant we setup at the very start, so let’s make a version of our reachability logic that counts steps as it explores.

at(X,Y, 0) :- start(X,Y), solid(X,Y).
at(NX,NY, T+1) :-
  at(X,Y, T),
  T < length,
  solid(NX,NY),
  step(DX,DY),
  NX = X + DX,
  NY = Y + DY,
  solid(NX,NY).

Because we want to forbid the situation where a player specifically reaches the finish tile, we need to give that situation a name.

speedrun :- finish(X,Y), at(X,Y,T).

Nolan Speedrun, by your True Name, I hereby banish you!

:- speedrun.

And with that last line, our basic map generator is complete. The picture at the start was generated from just the rules above (and some tedious manual photoshopping of the text to make it all round and colorful). The green zones are tiles that are reachable within our length bound, blue are reachable tiles beyond the bound, and red are unreachable tiles that happen to also be solid.

Did I say 50 lines of code? I only count 27 so far, we must have finished early. Let’s open things up a bit and explore some things you can build on top of this basic generator without making any major changes to the description of the map design space we’ve built so far.

Suppose we wanted to enforce horizontal and vertical symmetry (maybe we’re getting into the rug business). Three new lines:

horizontal_mismatch(X,Y) :- solid(X,Y), not solid(width-X+1,Y).
vertical_mismatch(X,Y) :- solid(X,Y), not solid(X,width-Y+1).
:- 1 { horizontal_mismatch(X,Y), vertical_mismatch(X,Y) }.

It says if the collection of all possible symmetry mismatches is populated by one or more true facts, explode. The result is now only those tastefully symmetric maps. One new thing I’ve done here is put some numerical bounds around the expression in braces. Without specifying any bounds, it means any number is fine, but sometimes you actually have a lower or upper bound in mind.

Would you like really heavy maps where at least 75% of the map is made of solid tiles? Try this in place of our original choice rule:

3*width*width/4 { solid(X,Y) :dim(X) :dim(Y) }.

Do you like the look of those little one-tile inland lakes on the northern-ish continent? Are you uncontrollably obsessed with them and demand that you have the mathematically absolute maximum number of them in your generated map? OK, man, I can do that for you. (Though I hope you like degenerate checker patterns in the middle of one giant continent.) Run the rest with “-n 0” and you’ll see Clingo print out a sequence of increasingly more lake-ridden maps that eventually culminates with an optimal map. I personally lost interest around 165 lakes in, after about 30 seconds of search.

lake(X,Y) :- dim(X;Y), solid(X+DX,Y+DY):step(DX,DY), not solid(X,Y).
#maximize [ lake(X,Y) ].

If you can name it, you can tame it! (By the way, you can combine different types of terms in an optimization statement and assign them different weights and priorities.) Given that I didn’t actually care what the the actual maximum number of lakes was, I’ll replace the last line with a more reasonable encoding of my interest. I’d like at least thirty-five inland lakes, please.

:- not 35 { lake(X,Y) }.

By now, you are getting the idea that “:- not good_thing.” is the way to express what you would like to see and “:- bad_thing.” is how you express what you wouldn’t. Between choice rules (the way you allow new things to come into existence), traditional logical rules and facts (the way you infer the properties of an artifact), and integrity constraints (the way to express your interests / your universe-annihilation policy) you’ve seen all of the major code-level elements of using answer set programming (ASP) for artifact generation.

For a slightly more formal introduction to using ASP for generating game content, check out my TCIAIG article Answer Set Programming for Procedural Content Generation: A Design Space Approach. If you’d rather play videogames than read articles from an academic journal, checkout the Warzone Map Tools, an awesome ASP-based map generator for the awesome (and open-source) realtime strategy game Warzone 2011.

Looks like we’ve still got 13 lines left. What nameable properties would you love/hate to see in a map?

(Here’s the basic generator source, sans symmetries and inland lakes: http://pastie.org/2636638 And here’s my ascii-art renderer, it assumes input is coming from Clingo: http://pastie.org/2636598)

About the author:  Adam is a PhD student, research scientist, software engineer, musician, artist, and hacker. He has a very special kind of respect for those elegant weapons like lisp (pronounced "scheme") and prolog, for a more civilized age. Read more from this author

Be Sociable, Share!

•