The maze book for programmers!

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

The Buckblog

Maze Generation: More weave mazes

17 March 2011 — A technique is demonstrated, giving finer configuration of weave density in random mazes, courtesy of Kruskal's algorithm — 7-minute read

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:

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!

Is it really so hard to allow adjacent crossings? What’s wrong with this: https://gist.github.com/874649 ?

Never mind! I see what’s wrong with it. Sorry…

Okay, so I’ve had another chance to look at this, and it seems there’s a pretty simple way to fix the problem I had before. I’ve updated the gist.

It’s really a very small change from your version. Here’s the diff: https://gist.github.com/875502

Does that look all right to you?

Argh, no! This doesn’t work either you can get loops in the maze because the sets aren’t maintained properly. I see I shall have to actually think about this…

Animated weave mazes… Great!

The final results of the Kruskal-pre-processed-weave are really nice.

Can you extend your posts to 3D mazes? (hard to animate or even display, though).

@Jamis Don’t be sorry! I wouldn’t be here if I didn’t like puzzlers. Why do you think the twisty mazes appeal to me? :-)

I did wonder about doing something like what you describe, but it seemed likely to get complicated pretty quickly.

But there does seem to be a reasonably simple solution, taking advantage of the fact that a passage can never turn a corner within a crossing cluster. So when a new crossing is added to a cluster, just walk in a straight line to the far edge of the cluster to see where the passage comes out again (i.e. to find which node to join with).

I’ve updated the gist, and I’m crossing my fingers that it actually is right this time!

I had to turn “grid” and “sets” into instance variables of the main object so the next_non_U method could see them. I suspect my limited experience of Ruby is letting me down here: how would you have done it? (As something of a newcomer to Ruby, I find it rather weird that methods don’t close over the variables of their outer scope, but I imagine it’s one of those things you get used to pretty quickly.)

I like Kruskal’s for things like this. It lets you put in buildings (inaccessible places) and large rooms. I’ll have to add weaves to my implementation, which will be nice because I am using it to drive a 3D maze game.

@Jamis Sadly I haven’t had any more time to look at this today, and now I’m going to be offline for the next week. Your three-phase idea sounds pretty sensible — but I guess it has the problem that it can create a loop out of crossings, since you’re laying down the crossings before you know what is connected to what? (I don’t have a computer with me now, so I can’t try your example to see whether that is indeed the problem you found.)

This is surprisingly hard! If you haven’t cracked it in the next week, then I swear I won’t rest until I do.

PS. I have given up on the problem of uniform weave-maze generation. None of my ideas worked, and I haven’t any more. Ah well.