The maze book for programmers!

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

# The Buckblog

## Maze Generation: Weave mazes

4 March 2011 — A way to construct mazes in “pseudo-3D” is presented, wherein the passages weave over and under one another — 7-minute read

This is a “weave” maze:

The name does not describe any specific algorithm for generating mazes, but rather simply identifies the class of maze, where some passages weave over or under other passages. It’s a type of 3D maze but it can be rendered nicely in 2D, as long as you conform to the following rules:

• Passages may only move under or over each other when they are perpendicular to each other.
• A passage may not terminate (dead-end) either under or over another passage.
• Passages may not change direction either over or under another passage.

If you break any of those rules, you’ll wind up hidden or ambiguous corridors when viewed as a 2D projection, and we don’t want that!

Let’s take a closer look at how the algorithms need to be adapted to support weave mazes.

## Weave maze adaptation

The key change that needs to be made is that when you determine whether a particular move is valid, you no longer get to ignore a cell if it has already been visited. If the candidate cell has been visited, you need to compare it against the three rules above, and rule it out only if it fails one of them.

Consider the following scenario:

The highlighted cell is the current one, the one we need to move from. In a non-weave scenario this would be a deadend, and we’d be done with that cell, but with weaves to consider, we can’t be so hasty.

So, we slow down and check it out. North? No, because the northern passage is not perpendicular to that direction. We’d wind up with an ambiguous passage if we tried to weave in that direction.

West? Nope, that takes us out of bounds.

South? Again, nope, because the passage south is not perpendicular to that direction.

Alright, so: east, our last and best hope? Ah, this one passes the perpendicular test—the corridor to the east moves north-to-south! The space on the far side of the corridor is empty, so we wouldn’t have to worry about deadending underneath the corridor, so again, we’re okay. And because we plan to just tunnel straight east, there’s no danger of changing direction mid-tunnel, either.

We have a winner! At this point, the algorithm would indicate that the passage moves under the north-south passage, and joins to the next cell over.

That’s really the gist of it. As long as the base maze algorithm can be adapted to accomodate this logic, you can implement weave mazes with it.

Try playing with this interactive demo (using the Growing Tree algorithm) to see how this approach to weave mazes works with different settings:

Cell selection method:

Now, let’s look at an implementation.

## Implementation

I’m going to be sticking with the Growing Tree algorithm, but it ought to be possible to adapt most of the maze algorithms I covered to generate weave mazes.

(I’ve not tried it with all of them, and some, like Eller’s, might be difficult to adapt. Also, while you can probably adapt Aldous-Broder or Wilson’s for this, you’ll probably no longer get a uniform spanning tree out of them, if that’s important to you.)

Now, what follows is just one way to implement a weave maze. I’m kind of a bit-twiddler at heart, so that’s the approach I took. If a passage moves under the cell, I just set another bit on that cell, indicating the presence of the tunnel.

The Growing Tree algorithm itself is exactly as I described before, but we add an else clause to check whether a weave is possible, and if so, to perform it:

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```nx, ny = x + DX[dir], y + DY[dir] if nx.between?(0, width-1) && ny.between?(0, height-1) if grid[ny][nx] == 0 # here's the original case, carving into an unvisited neighbor # ... elsif can_weave?(grid, dir, nx, ny) # here's where we perform the weave # ... end end ```

The “can_weave?” helper method is straight-forward. It just checks whether it is allowable to move from the candidate cell (nx, ny) in the given direction. (Remember that nx and ny are the coordinates of the cell we want to tunnel under!)

 ```1 2 3 4 5 6 7 ``` ```def can_weave?(grid, dir, x, y) cell = grid[y][x] return false unless cell == CROSS[dir] nx, ny = x + DX[dir], y + DY[dir] return ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0 end ```

The first check we do is to see if the passages in the indicated cell are perpendicular to the given direction. (That’s what the CROSS variable is all about; it’s just a hash returning which directions are perpendicular to one another.)

If that test passes, we now need to make sure that the next cell over in that direction is both in bounds, and unvisited. If both of those conditions hold, then we have a winner.

Once we know that a cell can be weaved under, it’s time to perform the weave. At it’s simplest, this is just a matter of setting the “under” bit, and then setting the necessary directions on the origin and target cells:

 ```1 2 3 4 5 ``` ```grid[y][x] |= dir grid[ny][nx] |= U nx, ny = nx + DX[dir], ny + DY[dir] grid[ny][nx] |= OPP[dir] ```

To clarify: (x,y) is the originating cell, the one we’ve carving away from. The first (nx,ny) is the cell we want to carve under. Then, we compute the target cell, on the far side of the cell we’re carving under; that’s the cell we’re going to end up at, after tunneling.

That’s really all there is to it. However, for variation, it’s nice to sometimes carve over the cell, instead of under it. This gives you some more interesting patterns, and it’s really not too hard to do. You just need to look at the cell to see which direction the passage is currently heading, and then change it so that the passage is rotated 90 degrees. Then you set the “under” bit. This has the effect of making the perpendicular passage (the one you’re adding) be the “over” passage, and the original passage the “under” passage.

Here it is in code:

 ```1 2 3 4 5 6 7 ``` ```if rand(2) == 0 grid[ny][nx] |= U elsif (grid[ny][nx] & N) != 0 grid[ny][nx] = E|W|U else grid[ny][nx] = N|S|U end ```

That’s really all there is to it! However, there’s one more interesting bit we need to consider, and that is how to render your weave maze.

## Rendering

The display methods I used in my previous maze posts are not sufficient for rendering weave mazes. This is because there is no space between passages, the walls have no width. This makes it impossible to see whether a passage terminates at a given wall, or moves under it.

To work around this, my program uses unicode characters from the box drawing range (x2500—x257F). The result is still not ideal (in larger mazes, the eye tends to lose track of what is a passage and what is the space between passages), but it lets us do a quick-and-dirty display.

For best results, we treat each cell as a 3×2 ASCII grid. For example, a N/S/E/W intersection would be rendered like this:

┘ └
┐ ┌

First, I define the set of tiles for each possible cell configuration:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ```EW, NS, SE, SW, NE, NW = [0x80, 0x82, 0x8C, 0x90, 0x94, 0x98].map { |v| "\xE2\x94#{v.chr}" } NSE, NSW, EWS, EWN = [0x9C, 0xA4, 0xAC, 0xB4].map { |v| "\xE2\x94#{v.chr}" } TILES = { N => ["#{NS} #{NS}", "#{NE}#{EW}#{NW}"], S => ["#{SE}#{EW}#{SW}", "#{NS} #{NS}"], E => ["#{SE}#{EW}#{EW}", "#{NE}#{EW}#{EW}"], W => ["#{EW}#{EW}#{SW}", "#{EW}#{EW}#{NW}"], N|S => ["#{NS} #{NS}", "#{NS} #{NS}"], N|W => ["#{NW} #{NS}", "#{EW}#{EW}#{NW}"], N|E => ["#{NS} #{NE}", "#{NE}#{EW}#{EW}"], S|W => ["#{EW}#{EW}#{SW}", "#{SW} #{NS}"], S|E => ["#{SE}#{EW}#{EW}", "#{NS} #{SE}"], E|W => ["#{EW}#{EW}#{EW}", "#{EW}#{EW}#{EW}"], N|S|E => ["#{NS} #{NE}", "#{NS} #{SE}"], N|S|W => ["#{NW} #{NS}", "#{SW} #{NS}"], E|W|N => ["#{NW} #{NE}", "#{EW}#{EW}#{EW}"], E|W|S => ["#{EW}#{EW}#{EW}", "#{SW} #{SE}"], N|S|E|W => ["#{NW} #{NE}", "#{SW} #{SE}"], N|S|U => ["#{NSW} #{NSE}", "#{NSW} #{NSE}"], E|W|U => ["#{EWN}#{EW}#{EWN}", "#{EWS}#{EW}#{EWS}"] } ```

Displaying the maze then becomes very straight-forward, just interating twice for each row so that each line of each tile gets drawn:

 ```1 2 3 4 5 6 ``` ```height.times do |y| 2.times do |row| width.times { |x| print TILES[grid[y][x]][row] } puts end end ```

The result:

```┌───────┐┌────┐┌───────┐┌────┐
│ ┌───┐ ││ ┌┐ ││ ┌───┐ ││ ┌┐ │
│ │┌──┴─┴┤ ├┘ ││ └───┤ ├┴─┴┘ │
│ ││ ┌┬─┬┤ ├──┘└─────┤ ├┬─┬──┘
│ └┘ ││ ││ │┌───────┐│ ││ │┌─┐
└────┘│ ││ │└──┐ ┌──┘│ ││ ││ │
┌─────┤ ├┘ │┌──┤ ├───┘ └┴─┴┘ │
│ ┌───┤ ├──┘│ ┌┤ ├──────┬─┬┐ │
│ └───┤ ├───┤ ├┘ │┌────┐│ ││ │
└─────┤ ├┐ ┌┤ ├──┘└──┐ ││ ││ │
┌─────┴─┴┘ ││ └─────┐│ ││ ││ │
│ ┌───┬─┬──┘└──┐ ┌──┘│ ││ │└─┘
│ └───┴─┴──┐┌──┤ ├──┐│ └┤ ├──┐
└─────┬─┬──┘│ ┌┤ ├┐ │└──┤ ├┐ │
┌────┐│ └───┴─┴┘ └┴─┴──┐│ ││ │
│ ┌┐ │└─────┬─┬┐ ┌┬─┬──┘│ ││ │
│ ││ └──────┘ ││ ││ └───┘ ││ │
│ │└──────────┘└─┘└───────┘│ │
│ └────────────────────────┘ │
└────────────────────────────┘
```

## Conclusion

Weave mazes can produce some very pretty designs, but randomly generated ones are not generally practical for most applications. Because the generator can “escape” from many dead-end situations by moving over or under a neighbor, the mazes tend to have very long passages (with a high “river” factor, meaning they can be quite windy), and very few junctions. Solving such a maze is not really very difficult.

That said, they can look quite impressive! In general, I’ve found that algorithms that encourage longer passages produce the best weave mazes. Algorithms like Kruskal’s and Prim’s (which produce mazes with lots of short deadends) will have a harder time meeting the “passages must not deadend over or under another passage” criterion, and as a result will have fewer over/under passages.

Give weave mazes a shot in the language of your choice, and share what you come up with! My own implementation, in Ruby, is given below.

Enjoy!

Cool as always!

I’d have loved to see the generation-animation for a weave maze too.

@Jamis I can imagine. I long for your next post ;)

Well, there is certainly another general class of algorithms for generating weave mazes. Place the crossings first — perhaps at random, but perhaps you want to place them in particular locations for aesthetic reasons — and then use the algorithm of your choice to find a spanning tree of the resulting graph. (All the algorithms you have described on this blog will work for general graphs, with the exception of Eller’s and recursive subdivision.)

To give a bit more detail, place a crossing as a cross shape covering five cells, then treat each passage of the crossing as a node in your graph, each having up to six neighbours (up to three at each end of the passage). Any cell that isn’t covered by a crossing is just a node in the usual way, of course.

Regarding the harder problem of how to generate weave mazes perfectly uniformly, I do have an idea that might work, but (assuming it does), it’s not going to be terribly fast.

Anyway, keep these coming. Wonderful food for thought!

PS. I should have mentioned that clusters of adjacent crossings need special treatment in this framework.

I hope it’s clear how this ought to work. For example, two adjacent crossings make a “fat cross” covering eight cells of the grid, and are represented as three nodes in the graph. Three crossings in an L shape cover ten cells, and make three passage nodes (one with a bend in it). And so on.

@Jamis No, I haven’t implemented it. If I can find the time this weekend, I’m going to play with the uniform algorithm. But I’m sure I won’t have time to implement this approach as well, so I’d be thrilled to see what you can do with it.

(Another minor caveat: some crossing clusters are impossible in the sense that they are inherently loopy, such as a cluster of five crossings together in a + shape, so these would have to be excluded.)

@Jamis Nice! I enjoy the “something old, something new” combination of ANSI escape sequences with UTF-8 encoded box drawing characters.

Here’s a version that permits adjacent crossings: https://gist.github.com/856316

Eh, so what’s wrong with this blindingly obvious way of creating weaves?

For each cell in a normal maze, if it is a crossroads (all four entrances open), randomly assign it to be NS-under, NS-over, or remain a crossroads.

And that’s it. Obviously this doesn’t work for algorithms that never generated crossroads, and I’m not sure that the maze will not be disjoint; although it does seem that you could ensure that quite easily by adapting Eller’s algorithm.

I thought that was what you were hinting at in the previous blog entry, since the 3 rules just ensure that a weave point looks like a crossroads.

http://s3.boskent.com/mazes/very-woven.png

@Baz If you take a perfect maze and convert a crossroads into a weave, the result will always be disconnected.

There will never be a path connecting the “under” and “over passages of the weave: if there were, the original maze would have had a loop going through the crossroads.

Obviously you could then reconnect it by adding a new passage somewhere, from one component to the other. Then you have a perfectly good algorithm, albeit one that will produce mazes without much weaving.

@Jamis The connectedness check is necessary. Think about what happens if we were to place crossings at (0,1), (1,0), (0,-1), (-1,0), say.

@Jamis I was struggling to work out what you meant, but I think I see it now! You were confused by my coordinate system. (I was imagining the origin being in the middle of the maze, rather than at the corner.)

Let’s call it (5,6), (6,5), (5,4), (4,5), in that case.

@Jamis Ha ha, yes. Exactly!

(I like that we each simultaneously worked out what the other was getting at.)