Maze Generation: Weave mazes

Posted by Jamis on March 04, 2011 @ 07:48 AM

This is a “weave” maze:

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!

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

04 Mar 2011

1. Gordon said...

Cool as always!

2. Fref said...

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

3. Jamis said...

@Fref, I’m still working on that. It’s a lot harder to do than the other grid-based animations, because the weave mazes require space between the cells in order to disambiguate the over/under passages. I figured it was better to get something out sooner, rather than wait until I worked out how to animate the process. :)

4. Fref said...

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

5. Robin Houston said...

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!

6. Robin Houston said...

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.

7. Jamis said...

@Robin, neat approach to the weave maze problem! Thanks for sharing that. If you do figure something out regarding uniform spanning trees, let me know!

8. Jamis said...

Btw, Robin, I meant to ask: have you implemented the approach you described? I may have to give it a try this weekend.

9. Robin Houston said...

@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.)

10. Jamis said...

@Robin, it turns out that Kruskal’s algorithm is particularly well-suited to building out weave mazes as you describe, since it works by joining disparate trees together into a spanning tree. By scattering the over/under crossings throughout the grid and joining their component cells appropriately into sets, Kruskal’s can then take over and flesh out the rest of the maze with literally no alterations.

Here’s my implementation, if you’d like to see:

https://gist.github.com/856138

Thanks for the idea! That’s a neat approach.

05 Mar 2011

11. Robin Houston said...

@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

12. Baz said...

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.

13. Robin Houston said...

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

14. Jamis said...

@Robin, very nice, I love how it’s actually simpler to allow adjacent crossings. I’ll bet it could even be simpler: we probably don’t even need to check the connected status of east/west and north/south pairs during the crossing phase, since they can only be connected if the center cell is non-zero, and that’s already grounds for dismissal all by itself.

@Baz, the problem is just what you said, you’ll wind up with disjoint trees. Think of it this way: if the maze is perfect (and all of these algorithms are guaranteed to make perfect mazes), then there will be exactly one path between any two pairs of cells in the maze. In other words, the maze can be considered a tree. Now, if you make an intersection into an over/under crossing, you are erasing the path between two cells, and since those two cells were previously connected, that must have been the only way they were connected. Disconnecting a branch from the tree makes it impossible to reach the cells in one tree from any of the cells in the other. The maze is no longer perfect. Sorry to burst your bubble. :(

15. Robin Houston said...

@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.

16. Robin Houston said...

@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.

17. Jamis said...

@Robin, except you can’t place a crossing with the center on any edge, because then you’d wind up with the center being a dead-end, and you’d violate one of the rules: no dead-end either over or under another passage.

Unless I’m misunderstanding what you mean?

18. Jamis said...

@Robin, ah, nevermind. I see what’s going on. North and south may not be directly connected, but may still have a path between them, because the algorithm now allows adjacent crossings.

Got it. Sorry to be slow on the uptake there. :)

19. Robin Houston said...

@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.

20. Robin Houston said...

@Jamis Ha ha, yes. Exactly!

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

21. Jamis said...

@Robin, I’ve updated my csMazes project to support weave mazes for several of the algorithms, as well as this two-phase algorithm you describe (only supported in Kruskal’s at the moment, though). Quite fun to play with! The two-phase approach is really nice; I especially like how tunable it is, so you can generate either densely woven mazes, or lightly woven mazes. And being able to manually place crossings is neat, too (though csMazes doesn’t directly support that), since you can get some interesting textures that way.