# 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

1. Andrew Pennebaker
Posted October 5, 2011 at 10:41 AM | Permalink

How does Gringo/Clasp/Clingo compare with Prolog?

Posted October 5, 2011 at 10:59 AM | Permalink

@Andrew: The syntax of Gringo is certainly related to Prolog (with facts, rules, variables, and negation), but most answer set solvers use a distinct language called called AnsProlog (with ASP-specific features like choice rules and integrity constraints). If you get below the syntax level, answer set programming and traditional logic programming are very different. Whereas a Prolog interpreter will usually evaluate a single top-level query in a depth-first, left-to-right fashion (potentially getting lost in infinite loops), answer set solvers transform your domain into something like a SAT problem and use constraint propagation and boolean satisfiability solving techniques to determine which answer sets it will output.

I suppose the biggest difference between answer set programming and traditional logic programming is in the kind of reasoning they implement. Prolog is all about deduction (determining what Must be true in the domain) whereas ASP is all about abduction (determining different sets of what Might consistently be true in a domain). The focus on abduction is what makes ASP an interesting tool for doing artifact generation.

2. Ryan Fox
Posted October 12, 2011 at 4:02 PM | Permalink

I’ve been playing with this since you first posted this, and it is pretty cool. Really hard, but cool. Unfortunately, what works nicely for a 20×20 map fails with a std::bad_alloc for 80×80!

Do you know of any good resources and/or IRC channels for ASP?

Thanks!

Posted December 12, 2011 at 5:46 PM | Permalink

Another introductory article on Answer Set Programming appeared in the December, 2011 issue of Communications of the ACM:

Answer Set Programming at a Glance
Gerhard Brewka, Thomas Eiter, Miroslaw Truszcznski
http://dl.acm.org/citation.cfm?id=2043195
http://mags.acm.org/communications/201112/?folio=92&CFID=57669445&CFTOKEN=76940163#pg94

Posted January 6, 2012 at 3:32 PM | Permalink

Thanks for linking to this, Jim. I didn’t know it was out there and it’s good to see an introduction in magazine form with code samples instead of only journal articles and conference proceedings with only abstract symbols and proofs.

Here’s a quote from it that stood out to me:

As it turned out, thanks to its features—high expressiveness, nondeterminism via multiple answer sets, and high declarativity—ASP is a valuable host language for domain-specific AI formalisms, allowing for quick experimental prototyping.

4. Srujal
Posted February 16, 2012 at 3:00 AM | Permalink

Thanks for this, it was really helpful….

5. Andrew
Posted May 14, 2012 at 7:39 PM | Permalink

I tried hard to understand this I really did. Only so much made it all the way into the part of my brain that actually understands stuff. But I really do like the idea that you can make a map generator with just 27 lines of code. I don’t know how long this would take in a traditional programming language (actually I might try that out). Anyways, this is something I would definitely like to learn in the future.

Posted May 15, 2012 at 2:01 PM | Permalink

And 27 lines means this was a tricky problem. “Difficult” classic problems like graph coloring or hamiltonian cycle are both solved in just two lines (see wikipedia)

6. Peter K.
Posted May 14, 2012 at 10:25 PM | Permalink

Thanks for the straightforward introduction, and forgive me if my questions are really low-level!

Allow me to get this straight… with logic programming (unless if answer-set programming is completely different), instead of a building up a universe from top down, does one instead build the constraints of a universe so that everything inside is generated? Additionally, what are other examples of answer-set/logic-based programming application (or at least interesting/fun ones).

I was totally unaware people still played Warzone 2011… knowing that just now is pretty awesome.

Posted May 15, 2012 at 2:36 PM | Permalink

Beyond syntax, ASP is quite different than traditional logic programming in Prolog — but nobody seems to be familiar with Prolog these days, so that’s not a big deal.

Sure, I might say ASP provides is bottom-up way of building things (like maps). When programming in ASP, you can think in terms of a generate-and-test process if you like. Choice rules define a generator, and the other rules and integrity constraints define a tester that filters out bad combinations. If you had a million monkeys picking elements out of the choice rules, the rest of the rules and constraints would tell you when one of the monkeys had finally produced an interesting result. That is, your answer set program doesn’t say how to generate something, but it does describe what space to search in and how to detect when you’ve found what you want.

In reality, the answer set solver will tightly interleave making individual choices (whether a particular tile in the map is solid or not) with testing (whether a nearby tile can be reached). Deciding whether most answer set programs have a valid answer set is an NP-complete problem. So, if you’ve ever seen an algorithm that could solve the graph coloring problem or the traveling salesman problem (in the case of optimization), then you’ve seen an algorithm that can be abused to search for or optimize over answer sets.

Other interesting applications? (none of these projects has a good landing page…)
- music: various renaissance styles (with counterpoint); trance
- mazes: evil, chromatic, irregular, perfect, run-free, perfect
- compilers: superoptimization
- stories: model of dramatic roles
- games: machine playtesting; minigame ruleset generation
- plenty of others I can’t think of right now