The Buckblog

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: Newest (Recursive Backtracker) Random (Prim's) Newest/Random, 75/25 split Newest/Random, 50/50 split Newest/Random, 25/75 split Oldest Middle Newest/Oldest, 50/50 split Oldest/Random, 50/50 split

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!