Spanning Trees and Maze Design

Mazes are designed to thwart our best intuitions about how to get from one place to another. In a well-designed maze, there is no straight path to the goal, and there are many dead ends along the way.

How would you go about building one?

Making a good maze requires a heavy dose of randomness. We want walls and paths to appear without any apparent order. But we do need there to be some order, otherwise the maze would be insoluble.

One way to provide the minimum necessary order to create a solvable maze is to build the maze as a spanning tree.

A spanning tree is a kind of network. It follows two simple rules: (1) Every available point must be connected to the network, and (2) no point can be connected to itself. Total coverage, no cycles.

There are many ways to generate spanning trees. Since points in a two-dimensional plane each have four neighbors, the easiest way for us will be to radiate outward from the start of the maze, connecting each point to all of its unconnected neighbors, until the whole grid is connected.

This produces a pretty boring maze. How can we do better?

Randomized Growth

Let's inject some randomness into our spanning tree generation. Here's the simplest way, represented as an algorithm:

1. Keep a list of possible path extensions, starting with just the entry point.
2. Pick a random element out of the list.
3. Will adding that point to the maze cause the maze to intersect itself?
4. If not, add that point to the maze, and add all of its unvisited neighbors to the list of possible path extensions.
5. Either way, mark that point as visited.
6. Repeat until the list is empty.

This approach produces mazes like the one seen here.

The maze grows evenly and organically to fill the space. Each next path extension may be randomly chosen, but in any given round, all the available extensions have the same chance of being chosen. This way of structuring our randomness produces locally unpredictable, but globally regular behavior.

If we color the maze based on the path-distance of each segment from the starting point ("the root"), we can get a decent sense of its global structure:

Notice how the color gradient shifts evenly from the top left corner (the root), outward. This tells us that there aren't any crazy backtracking paths in the maze. But what if we wanted a maze that was more chaotic?

Random Weights & Prim's Algorithm

In our simple randomized growth algorithm, we used random selection from the set of candidate extensions to grow the maze. Because every node has a fresh chance in every drawing, the overall tendency is toward unbiased radial expansion outward from the root.

We want to put the randomness into the global structure instead of just the local path expansion. We can do this by assigning every square on the grid a random weight, and then using Prim's algorithm to build our maze.

Prim's algorithm is a method for building a minimum spanning tree. A minimum spanning tree is a spanning tree that's designed to choose the least expensive way of connecting all the tree's nodes, based on the cost of drawing any particular connection.

Prim's accomplishes this by always using the least expensive available path extension. Because each node has a fixed weight, if a node is generated with a high weight, it will be selected against in every successive round until it is the least expensive remaining node.

For the most part, our implementation of Prim's algorithm is identical to our earlier algorithm. We add an initial step before our old step 1,

0. First, assign every potential square a random numerical weight.

and we change step 2,

2. Pick the least expensive element out of the list.

This approach produces mazes like the one seen here.

Let's color the maze to get a better sense of its global structure.

Notice that the randomized Prim's maze is much more complex, but that the local structure remains random.

This maze also constitutes a good maze from a straightforward design perspective: there are long, complex, blind alleys, and the path-distance of any given node is not easily predicted based on its position in the grid.

Restricted Randomness & Depth First Growth

Before solving our mazes, let's try out one more generator. Suppose we wanted mazes with extremely deep, winding paths. How would we change our path-extension algorithm to produce that?

One way to create deep mazes is based on depth first search (DFS), a tree-searching algorithm. DFS sets its search trajectory to prioritize the current branch. In other words, it tries to keep going along a particular path as far as possible before exploring other, earlier options.

A non-randomized depth-first growth maze looks like this:

In order to give our DFS maze some complexity, we choose randomly from the N most recently added elements in our list of possible path extensions.

Let's set N to 4, since any given node can have at most four valid unincorporated neighbor nodes. And here's our maze:

When we colorize the DFS maze, its global structure becomes clear. Compare a DFS maze, top, with our initial random-growth maze, bottom. Notice how many times our DFS maze cycles through the color spectrum before it fills the space.

Depth first mazes are much deeper than random growth mazes of the same size. At this scale, they are generally about five times deeper, but that factor increases with the size of the maze.

However, there's a big downside to our DFS maze. Because DFS is biased in favor of extending the current branch of the tree, our maze ends up dominated by a couple of very long, locally simple corridors.

A we will see below, the solution to a DFS maze may be very convoluted, but it's often not hard to find.

Speaking of solving mazes, let's do some of that!

Maze Solvers

Depth First Search

Depth First Search is a simple algorithm for finding the path to a target node in a tree, given a starting point. DFS uses a stack to maintain a list of nodes to explore.

1. Start at the root.
2. Pop the last (i.e. most recently added) element off the stack.
3. Check for a match. If found, return the target node.
4. Add each of the current node's children to the stack.
5. Repeat until a match is found, or the stack is empty.

The result is a search path that goes as deep as possible down a single branch before trying another branch.

To the right you can see DFS solving each of our three maze types. Whenever a given path segment is explored, the search algorithm colors it white to show where it's been.

I have placed the root of each maze in the exact center to better show the behavior of the algorithm.

Breadth First Search

Breadth First Search is similar to DFS, but it treats the list of nodes to search as a queue instead of a stack. In other words, step 2 of the algorithm listed above becomes:

2. Shift the first (i.e. least recently added) element out of the queue.

The result is the smooth radial expansion you see here.

Comparing BFS to DFS, we see that BFS is potentially much more expensive in terms of the number of nodes explored before finding the solution. This depends in part on the relative position of root and target within the maze.

If the path distance between root and target is small relative to the size of the maze, BFS (left) will tend to outperform DFS (right). Run the demo a few times to get a sense for their relative performance!

Both methods have their weak spots, though. If the root and target are maximally distant from each other within the maze, BFS will have to explore the entire tree before finding the goal, while DFS goes straight for the fringes.

Dijkstra's Algorithm

A* Search

Now that we've built out a Dijkstra maze solver, though, we can use it to implement an intuition-based path-finding-algorithm called A*.

A* keeps track of two different factors. First, how expensive it was to get to a given node from the origin. Second, the minimum predicted cost of getting from that node to the goal. A* predicts the cost of traveling through a given node based on a heuristic function we provide it, which is based on the structure of our graph.

In this case, we set the heuristic function to calculate the diagonal distance between the current node and the target node, so that our search will be encouraged to go as directly toward the goal as possible.

How does A* perform? You can see it in action on the right.

As with DFS I have placed the root of the maze at the center, to better illustrate the behavior of the algorithm.

You can see that when a relatively direct path is available, A* tends to find it, and quickly. A* also has an advantage when the root and target are close together, relative to the size of the graph.

A* doesn't always outperform DFS (or even BFS—intuition can lead us astray!), but it is about as good in the worst case, and better on average.