The Buckblog

My previous post showed one way to create “weave mazes”, or mazes in which the passages weave over and under one another. The technique I showed was flexible, and could be implemented using several different maze algorithms, but it has (at least) one big drawback: it’s not predictable. You don’t know how many over/under crossings you’ll get until the maze has been generated, and for small mazes (5×5, for instance) you may very often get no crossings at all.

In the comment thread for that post, Robin Houston described an alternate algorithm. Instead of building the crossings as you generate the maze, you do it as a preprocessing step. You scatter crossings (either at random, or deliberately) across the maze, and then generate the maze so that they connect correctly.

Sounds like it could be tricky, yeah? You’ve got all these independent connections, like little graphs floating around, all disjoint... If only there were a way to generate a maze by connecting disjoint trees into a single graph…

What’s that? Oh, right! Kruskal’s algorithm does just that! Let’s take a look at how easy Kruskal’s makes this.

Weave mazes via preprocessing

I’m not going to review Kruskal’s algorithm here. If you don’t remember the details, I strongly recommend you read (or re-read) my article on Kruskal’s algorithm. Don’t worry, I’ll wait.

Seriously, read it. The rest of this post won’t make much sense unless you understand how Kruskal’s works.

Got it? Alright, let’s proceed.

So, let’s assume you’ve got your blank grid, and you’ve set it up (just like Kruskal’s wants) so that each cell is the root of its own (one-node) tree. You’re about to generate the maze…

First, though, we do the preprocessing step: let’s scatter over/under crossings about the grid. We have a few constraints:

1. no crossing can be placed on the edge of the grid (because that would imply a passage moving outside the grid).
2. no crossing can be placed immediately adjacent to another crossing (this just simplifies things—allowing adjacent crossings appears to introduce a surprising amount of complexity).
3. if the y-1 and y+1 (north and south) cells are already connected (in the same set), the crossing must not be allowed (because it would create a loop).
4. similarly, if the x-1 and x+1 (west and east) cells are already connected, the crossing must not be allowed.

So, we place a crossing. We randomly decide whether the over-passage is north/south or east/west, and then carve the appropriate values into the grid.

However, since we’re dealing with Kruskal’s algorithm, we also need to update the connection sets, and then remove the relevant edges from the edge set. Because we don’t allow adjacent crossings, we don’t ever have to worry about things connecting directly to the cross-over cells (this is why allowing adjacent crossings gets complicated). So, to update the sets, we just join the north/south cells, and the east/west cells. And then we remove the edges connecting the cross-over cell, and its adjacent cells.

A lot of words, but not so much work, in practice!

Once you’ve set all the over/under crossings, you’re ready to actually generate the maze. And the ahem amazing thing about Kruskal’s algorithm is, if you’ve correctly handled the edges and connections in the preprocessing step, you can run it without modification at this stage. The result will be a perfect, weave maze!

For your enjoyment, here are some demos to play with. Try the different settings to see how the output changes: particularly, notice how Kruskal’s using the naive “weave as you go” approach generates far fewer crossings (on average) than the approach described here.

Recursive Backtracker (in-process weave):

Kruskal's (in-process weave):

Kruskal's (pre-processed weave):
Density: very moderate light very light

Implementation

Since the only thing that changes between this weave technique and the non-weave Kruskal’s algorithm is the pre-processing step, I’m just going to go over the pre-processing step here.

You will probably also want to use a rendering method that allows you to unambiguously show the over/under crossings, such as the method using unicode characters that I described in my previous article.

Now, there are a lot of ways you could go about scattering crossings across the grid. For simplicity, I’m going to just iterate over each cell and randomly decide whether a crossing should be placed there. (This makes it easier to parameterize the process, allowing you to provide a “density” parameter to control how many crossings get placed.)

So, the first thing I do is just iterate over the possible cells:

1
2
3
4
5

1.upto(height-2) do |cy|
  1.upto(width-2) do |cx|
    # ...
  end
end

We start at 1 and go to n-2, because of the first constraint: crossings cannot be placed on the grid boundary.

Within the loop, I then use the “density” parameter (an integer from 0 to 100) to determine whether to skip this cell or not:

next unless rand(100) < density

Next, I compute the coordinates of the adjacent cells, and then check to make sure the cell really is eligible for a crossing:

1
2
3
4
5
6
7
8

nx, ny = cx, cy-1
wx, wy = cx-1, cy
ex, ey = cx+1, cy
sx, sy = cx, cy+1

next if grid[cy][cx] != 0 ||
  sets[ny][nx].connected?(sets[sy][sx]) ||
  sets[ey][ex].connected?(sets[wy][wx])

(Remember that sets is a two-dimensional array of Tree objects that allow us to quickly query and join sets.)

If the grid at the chosen point is non-zero, then (by implication) we are adjacent to another crossing, and that isn’t allowed. And if the north and south sets are already connected, or the east and west sets, then we can’t allow a crossing here either (lest we introduce a loop into the graph).

Now that the sets have been updated, we can carve the new passages into the grid:

1
2
3
4
5
6
7
8
9
10

if rand(2) == 0
  grid[cy][cx] = E|W|U
else
  grid[cy][cx] = N|S|U
end

grid[ny][nx] |= S if (grid[ny][nx] & U) == 0
grid[wy][wx] |= E if (grid[wy][wx] & U) == 0
grid[ey][ex] |= W if (grid[ey][ex] & U) == 0
grid[sy][sx] |= N if (grid[sy][sx] & U) == 0

Recall that the U constant is just used to indicate the presence of an “under” passage. Thus, “E|W|U” means an east/west passage with an implied north/south passage beneath it, and “N|S|U” means a north/south passage with an implied east/west passage beneath it.

Further, we only carve on an adjacent passage if it doesn’t already have the “under” bit set. (If it does, then it is already a four-way crossing, and the passage we’re trying to add is already present, either explicitly or implicitly.)

Finally, we just need to update the edge list, to account for the edges we’ve now implicitly processed by adding this crossing:

1
2
3
4
5

edges.delete_if do |x, y, dir|
  (x == cx && y == cy) ||
  (x == ex && y == ey && dir == W) ||
  (x == sx && y == sy && dir == N)
end

Remember that the edge list is just a collection of 3-tuples, with each tuple consisting of the x and y coordinates of a cell, and the direction that the edge exits that cell. It only contains edges that exit cells to the west, or the north (otherwise, we’d get duplicate edges: west from cell x is the same edge as east from cell x+1).

Thus, we’re deleting any edge connecting to the crossing cell itself, the west-facing edge from the eastern cell, and the north-facing edge from the southern cell.

When these loops finish, you’ll have a grid containing randomly-scattered crossings, ready for Kruskal’s algorithm to finish up.

Conclusion

This approach allows you to have weave mazes with a much higher density of crossings than the in-process approach. However, while the in-process approach can generate weave mazes with adjacent crossings, the algorithm described here cannot. I’ve spent some time trying to fix this flaw, but quickly found myself mired in complexity: I’m hoping brighter minds than mine can find an elegant solution to this!

Still, the biggest lesson I took away from this experience is this: it pays to know multiple different ways to solve a problem. I’m not a big fan of Kruskal’s algorithm in general (I don’t like the esthetic of the mazes it generates), but if I had never bothered to learn how Kruskal’s operates, I would never have been able to recognize it’s suitability for connecting the pre-processed crossings.

Stated more generally: the key to appearing smart is not knowing everything, but rather knowing the right thing.

Just because an algorithm may not be your favorite way of solving a problem most times, does not mean it won’t eventually be the best way to solve a problem. You just wait: one of these days I’ll encounter a problem while writing a web app that one of these maze algorithms will be perfect for!

So, give this algorithm a try, if for no other reason than it’s good exercise! And we all know exercise is good for you. ;) My own implementation is given below:

Enjoy!