The Buckblog

My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm.

If you recall, the random variant of Kruskal’s algorithm worked by randomly selecting edges from the graph, and adding them to the maze if they connected disjoint trees. Visually, this had the effect of growing the maze from many random points across the grid.

Prim’s approaches the problem from a different angle. Rather than working edgewise across the entire graph, it starts at one point, and grows outward from that point. The standard version of the algorithm works something like this:

1. Choose an arbitrary vertex from G (the graph), and add it to some (initially empty) set V.
2. Choose the edge with the smallest weight from G, that connects a vertex in V with another vertex not in V.
3. Add that edge to the minimal spanning tree, and the edge’s other vertex to V.
4. Repeat steps 2 and 3 until V includes every vertex in G.

And the result is a minimal spanning tree of G. Straightforward enough!

With one little change, it becomes a suitable method for generating mazes: just change step 2 so that instead of selecting the edge with the smallest weight, you select an edge at random, as long as it bridges the so-called “frontier” of the maze (the set of edges that move from within the maze, to a cell that is outside the maze).

As before, let’s walk through an example and see how it works in practice.

An example

Let’s start with a simple 3×3 grid:

Now, we choose a point at random and add it to the maze:

For efficiency, let’s call the set of all cells that are not yet in the maze, but are adjacent to a cell that is in the maze, the “frontier”. We’ll color the frontier cells red:

Now, we choose one of these frontier cells at random and carve a passage from that frontier cell to whichever adjacent cell is already part of the maze. Then we’ll mark the neighbors of the formerly frontier cell, as “frontier” cells themselves.

Rinse and repeat:

Now, here’s an interesting bit. Look what happens if we (ahem, “randomly”) choose the cell at (1,0) (the top middle). It is adjacent to two cells that are already “in” the maze. The algorithm resolves this by simply choosing one of the “in” neighbors at random. Prim’s doesn’t care which neighbor is picked, only that each frontier cell eventually be connected to a cell already within the maze.

Let’s just keep it going to the end, now, chug chug chug:

The algorithm terminates when there are no more frontier cells to choose from, giving us the anticipated perfect maze.

Implementation

The largest bit of implementing Prim’s algorithm (for me) seems to go toward managing the interactions with that frontier set. Maybe your experience will be different. You basically need two operations: mark a cell as “in” (which then marks the “out” neighbors as frontier cells), and one that returns all the “in” neighbors of a given frontier cell. Something like this: (and please excuse the apparent hand-waving around the add_frontier method; it’s not complicated, just not entirely relevant. The full implementation is given at the end of the article.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def mark(x, y, grid, frontier)
  grid[y][x] |= IN
  add_frontier(x-1, y, grid, frontier)
  add_frontier(x+1, y, grid, frontier)
  add_frontier(x, y-1, grid, frontier)
  add_frontier(x, y+1, grid, frontier)
end

def neighbors(x, y, grid)
  n = []

  n << [x-1, y] if x > 0 && grid[y][x-1] & IN != 0
  n << [x+1, y] if x+1 < grid[y].length && grid[y][x+1] & IN != 0
  n << [x, y-1] if y > 0 && grid[y-1][x] & IN != 0
  n << [x, y+1] if y+1 < grid.length && grid[y+1][x] & IN != 0

  n
end

Once you’ve got that implemented (along with the necessary supporting methods and data structures), the algorithm itself is remarkably straightforward.

You start by marking a random cell:

1

mark(rand(width), rand(height), grid, frontier)

Then, you simply iterate until the frontier set is empty:

1
2
3

until frontier.empty?
  # ...
end

Within the loop, we choose a frontier cell at random:

1

x, y = frontier.delete_at(rand(frontier.length))

Then we choose a random “in” neighbor of that frontier cell:

1
2

n = neighbors(x, y, grid)
nx, ny = n[rand(n.length)]

Then, we record a passage from the neighbor cell to the frontier cell:

1
2
3

dir = direction(x, y, nx, ny)
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]

And finally, we mark the frontier cell as being “in” the maze (and add any of its outside neighbors to the frontier):

1

mark(x, y, grid, frontier)

And you’re done! For those of you not using IE (which will make a total mess of this), here are two demos you can play with to see Prim’s in action:

My complete implementation (in Ruby) is here:

Conclusion

Mazes generated by Prim’s algorithm share many of the characteristics of those created via Kruskal’s algorithm, such as having an abundance of short cul-de-sacs. Such an aesthetic appeals to some, and not to others, but it definitely has this to say for it: for large mazes, the short cul-de-sacs make the maze harder to puzzle out at a glance!

Whether you enjoy the look of these mazes or not, I encourage you to try your hand at Prim’s algorithm. It’s a fun algorithm to code, not least of all because it comes together so easily. Personally, I enjoy watching the animation: it puts me in mind of a flame consuming a sheet of paper.

Please do share what you come up with. Have fun!