Generating a maze with linear constraint programming
I don’t know why, it’s fun I guess.
Taking a look at the Wikipedia entry for maze generation algorithms I noticed a lack of linear (or constraint) programming approaches. I personally enjoy constraint programming, so let’s give it a shot. Hopefully we will learn a thing our two about this kind of approach along with way.
In constraint programming we define a solution space and then provide constraints on that space for a solver to explore. It’s a fairly straightforward form of “Artificial Intelligence”, and the basis for some of the more complex natural language AI.
Let’s start by defining a grid that we will fill in with maze content. We will use the variable “x” to store information about each square on the grid.
Let x[i][j] be equal to 0 when the square located at row i, column j is blank. Let it be 1 when there is a wall.
Now I’ll start with a basic formulation of a constraint program. I’m using ruby along with a nice language wrapper called opl. I do not recommend using this gem in production as it is woefully un-maintained. I wrote the gem so I’m allowed to say that. You should use Python if you are just getting into the game.
require "opl"# size of the maze
n = ARGV[0].to_i# maximize the number of walls in the maze
objective = "sum(i in (0..#{n-1}), j in (0..#{n-1}), x[i][j])"constraints = []# ensure that we have a value for each square
constraints << "forall(i in (0..#{n-1}), j in (0..#{n-1}), x[i][j] >= 0)"$lp = maximize(objective, subject_to(constraints, ["BOOLEAN: x,y"]))
pp $lp.matrix_solution["x"]
With this template the output looks like this
We told the optimizer to maximize how many squares have walls, and since there are no meaningful constraints the optimizer just filled the entire grid with walls. Now that we have a baseline, we can start adding constraints that together form the definition of a maze.
This is the fun part. Now we have to answer the question: “what exactly is a maze”? Let’s start by creating an entry and exit point in the maze. this is as simple as setting the value of a pre-determined entry point and exit point to zero:
# enter
constraints << "x[1][0] = 0"
# exit
constraints << "x[#{n-2}][#{n-1}] = 0"Adding these to the model yields
Let’s render this a bit more clearly. Zero’s will be blank and one’s will be walls.
Cool! Now let’s build on those entry and exit points. A clear rule of mazes that we can implement is that whenever a square is empty, there must be at least one adjacent empty square.
# if a square is empty, then there is at least one adjacent empty square
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), x[i-1][j] + x[i + 1][j] + x[i][j - 1] + x[i][j + 1] - x[i][j] <= 3)"# for left side
constraints << "forall(i in (1..#{n-2}), x[i][0] - x[i][1] >= 0)"# for right side
constraints << "forall(i in (1..#{n-2}), x[i][#{n-1}] - x[i][#{n-2}] >= 0)"
This starts to draw a more discernible path. Now let’s guarantee some more spaces open up by disallowing a group of 5 walls:
# don't allow for a wall to be surrounded by four walls
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), x[i-1][j] + x[i + 1][j] + x[i][j - 1] + x[i][j + 1] + x[i][j] <= 4)"
We’re opening up more space in the maze, but it’s still not drawing a path. A bit of ingenuity is required. Let’s create a separate concept called the “correct” path and then ensure that it is drawn.
Let y[i][j] be equal to 1 when the square located at row i, column j is on the correct path. 0 otherwise.
# entrance is on the correct path
constraints << "y[1][0] = 1"# entrance has a correct path square to the right of it
constraints << "y[1][1] = 1"# a square on the correct path is surrounded by exactly 2 other squares on the correct path
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), y[i-1][j] + y[i + 1][j] + y[i][j - 1] + y[i][j + 1] - 2*y[i][j] >= 0)"
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), y[i-1][j] + y[i + 1][j] + y[i][j - 1] + y[i][j + 1] + 2*y[i][j] <= 4)"# a square on the correct path is empty
constraints << "forall(i in (0..#{n-1}), j in (0..#{n-1}), y[i][j] + x[i][j] - 1 <= 0)"
This set of constraints guarantees a fully connected path will exist through the walls. Let’s use “*” to denote the “correct” path.
Hah! There are two “correct” paths available in this maze, but they are so dead simple as to be uninteresting.
This is a good time to point out the adversarial nature of constraint programming. If you remember, we defined an optimization function and told the program to maximize it. The program is going to do this at all costs. Often times you will add a constraint that you feel is particularly clever to knock the program in the right direction, but it just hits you right back with the obvious, lazy answer.
Let’s close off the edges of the maze so that this kind of trivial answer is not produced.
# top and bottom rows of the maze are blocked off
constraints << "sum(j in (0..#{n-1}), x[0][j]) = #{n}"
constraints << "sum(j in (0..#{n-1}), x[#{n-1}][j]) = #{n}"# left and right (except for entry and exit)
constraints << "sum(i in (0..#{n-1}), x[i][0]) = #{n-1}"
constraints << "sum(i in (0..#{n-1}), x[i][#{n-1}]) = #{n-1}"
Well hey! We have a really stupid maze.
Increasing complexity
Getting to this point was fairly simple, but the maze itself is trivial. Let’s at least force the program to open up more space by adding a constraint:
# every row must have at least n/2 spaces
constraints << "forall(i in (1..#{n-2}), sum(j in (0..#{n-1}), x[i][j]) <= #{(n / 2.0).ceil})"
Hey not bad! We have a “correct” path and one dead end. For a maze of size 6 that’s probably as good as we will get. The constraint we just added is what I find beautiful about constraint programming. I didn’t tell the program how to build the maze. I just told it a property of the maze that it had to respect: that every row needs to have a certain amount of space. The program will go ahead and keep optimizing subject to this new constraint. If you are really clever about how you describe what a maze is, you can produce some really great things.
Let’s build a bigger one and see where this approach takes us.
This is technically a maze, but far more trivial compared to the size of the grid. Can we come up with constraints that might increase the “complexity” of the maze? Let’s get rid of that cluster of spaces.
# don't allow for a set of four spaces to form a "space square"
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), x[i][j-1] + x[i-1][j-1] + x[i-1][j] + x[i][j] >= 1)"
OK! In this maze we have at least one non-trivial dead end. However we also have the entire lower left side of the maze as an alternate correct path. That’s a lot of lost real estate.
At this juncture I have to point out the weakness of the constraint programming approach. In the screenshots above I neglected to show how long it took the program to run. Here’s a brief overview:
That curve gets pretty bad pretty fast. There are optimizations we can do, but fundamentally the algorithm behind linear constraint programming (SIMPLEX) will have poor scaling performance compared to a deterministic algorithm. I theorize, but won’t bother to prove, that maze generation falls into a niche category for which the SIMPLEX algorithm is known to be inefficient.
Finishing the maze
For the sake of completeness, I will add the final set of constraints to define a real maze.
In the maze above, the alternate path meets the correct path at two points. To ensure this never happens, I want to tell the program that it can’t connect an “incorrect path” to the “correct path” at more than one location. However we have no concept of “incorrect path” encoded in our constraints. We have the “correct path” concept, but if a square is “not correct” it can also be a wall. So we need to add a new potential state for a square to be on an “incorrect path”. This turns out to be pretty complicated.
Let p[i][j][v][w] be 1 if square i,j is on the incorrect path originating at v,w. 0 otherwise.
# edges cannot be on an incorrect path
constraints << "sum(j in (0..#{n-1}), v in (1..#{n-2}), w in (1..#{n-2}), p[0][j][v][w]) = 0"
constraints << "sum(j in (0..#{n-1}), v in (1..#{n-2}), w in (1..#{n-2}), p[#{n-1}][j][v][w]) = 0"
constraints << "sum(i in (0..#{n-1}), v in (1..#{n-2}), w in (1..#{n-2}), p[i][0][v][w]) = 0"
constraints << "sum(i in (0..#{n-1}), v in (1..#{n-2}), w in (1..#{n-2}), p[i][#{n-1}][v][w]) = 0"# all squares on the correct path spawn their own incorrect path
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), p[i][j][i][j] - y[i][j] = 0)"# a square can either be on an incorrect path or it is a wall
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), sum(v in (1..#{n-2}), w in (1..#{n-2}), p[i][j][v][w]) + x[i][j] = 1)"# a square can be on at most one incorrect path
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), sum(v in (1..#{n-2}), w in (1..#{n-2}), p[i][j][v][w]) <= 1)"# an incorrect square is surrounded by squares that are either
# also on that incorrect path, or
# are walls, or
# the square is on the correct path
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), v in (1..#{n-2}), w in (1..#{n-2}), 4*p[i][j][v][w] - 4*y[i][j] - p[i+1][j][v][w] - p[i-1][j][v][w] - p[i][j+1][v][w] - p[i][j-1][v][w] - x[i+1][j] - x[i-1][j] - x[i][j+1] - x[i][j-1] <= 0)"# square i,j cannot be on incorrect path originating at v,w if v,w is not on the correct path
constraints << "forall(i in (1..#{n-2}), j in (1..#{n-2}), v in (1..#{n-2}), w in (1..#{n-2}), p[i][j][v][w] - y[v][w] <= 0)"# if there is a square on incorrect path originating at v,w then there is a square adjacent to v,w also on that incorrect path
constraints << "forall(v in (1..#{n-2}), w in (1..#{n-2}), sum(i in (1..#{n-2}), j in (1..#{n-2}), p[i][j][v][w]) - #{n}*p[v-1][w][v][w] - #{n}*p[v+1][w][v][w] - #{n}*p[v][w-1][v][w] - #{n}*p[v][w+1][v][w] - p[v][w][v][w] <= 0)"
Whew. That is a lot of new constraints. Unfortunately these constraints make the program even less performant. This makes sense because I added two more dimensions to the solution space. Even after some improvements I was still not able to get to a size 12 maze in reasonable time.
Conclusion
As you might expect, linear constraint programming is not a recommended way to generate a maze. There are O(n) algorithms to generate complex mazes of any size — this isn’t one of them. But I hope we all had some fun learning a bit about constraint programming.
