Maze Generation: More weave mazes

Posted by Jamis on March 17, 2011 @ 09:26 AM

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!

Posted in Under the Hood

Comments

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

17 Mar 2011

1. Robin Houston said...

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

2. Robin Houston said...

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

3. Robin Houston said...

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?

4. Robin Houston said...

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…

5. Jamis said...

@Robin, sorry to put a puzzler on your plate! I’ll admit I had hoped you would see a simple solution that I had missed. :) I spent a few hours on it, and got “close”, eventually winding up with a design in which there were two tree nodes for each cell (one over, one under), but hit a dead-end trying to solve a problem where the sets were being merged with the wrong neighbor set. It’s definitely not intractable, but it sure feels a lot more complicated than it ought to be!

18 Mar 2011

6. Fref said...

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

7. Jamis said...

@Fref, almost all of the algorithms I covered extend very cleanly to 3D; you just need to use a 3-dimensional array instead of a 2D array, and add UP/DOWN to the possible list of directions, and the rest “just works”. Some algorithms, like Eller’s, might be harder to extend into 3D, though (I haven’t tried, that’s just my suspicion).

8. Robin Houston said...

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

9. Jamis said...

@Robin, that’s a great observation. It seems like that could definitely be a promising avenue to explore. Sadly, the gist still isn’t quite right: try “kruskals-weave.rb 10 10 50 2762126207”, and you’ll see there are subtrees that are disconnected from the rest of the graph (the bottom-right corner, for instance, is part of one such subtree). I’m going to play with this approach some today, though, it seems like it ought to work!

Regarding the grid/sets instance variables, at this point, the script is getting big enough that I would probably refactor everything into an object so that the state can be shared more easily. Barring that, I would probably have just passed the grid and sets variables to the method as arguments. I definitely agree that there have been times where I’ve wished Ruby methods were closures.

10. Jamis said...

@Robin, how about this?

https://gist.github.com/876334

This tries it as a 3-phase approach, where the first phase just lays down the crossings (without connecting them to adjacent cells). The second phase then uses your next_non_U to connect sets based on the crossings. And the third-phase is just Kruskals.

Empirically it seems to work, but I’m still trying to see, more formally, if it will actually generate perfect mazes every time.

11. Darren said...

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.

http://www.youtube.com/watch?v=X2mkwcfEd_8

12. Jamis said...

@Darren, very nice! Let me know how doing weaves in a 3D environment works; you might have better luck just implementing a true 3D maze.

@Robin, alas, I found a counter-example in my proposed 3-phase implementation: “kruskal-weave-2.rb 10 10 40 77682634”. There’s an artifact just above the center. I see how it happens, and I have some ideas for how to work around it, but it does suggest that my idea was flawed. :)

13. Robin Houston said...

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

14. Jamis said...

@Robin, enjoy your time offline! I’ll keep tinkering on this. Sorry to hear you’ve given up on the uniform weave-mazes, but I totally understand; that’s a very hard problem. :)

The problem I saw with the 3-phase was indeed a result of loops being added because of the blind first-phase. There must be happy medium between laying the crossings down blindly, and setting the connecting passages in stone. Anyway, I’ll keep at it.

31 Mar 2011

15. Robin Houston said...

All right, then! How about this? https://gist.github.com/896124

16. Robin Houston said...

Problems worthy of attack prove their worth by hitting back. — Piet Hein

kruskal-weave-3.rb 15 15 50 4146911113

:-(

01 Apr 2011

17. Robin Houston said...

Ah, it’s all right! There’s an easy fix this time.

I’m starting to think this might be correct, at last. The only innovation is that it deals with the crossings a row at a time, and doesn’t update the ‘sets’ until it’s checked that a candidate row can be inserted without creating any loops. If there’s a loop, it just generates another row of random crossings and tries again.

05 Apr 2011

18. Jamis said...

@Robin, that’s excellent! That seems to work very nicely. Thanks for working that out! It’s pretty amazing how busy the mazes look with the crossings so tightly packed. :)