This is companion piece to “how to solve a maze”.

I’ve spent far too much time playing with mazes, both when I was young, and now later in life. I’ve wondered if this would fall under a “special interest” and I think there’s some argument that it could.

While I was playing with code for solving a maze, I had to have some maze for it to solve. Initially I just had the code take out walls at random, knowing that while this wasn’t the best approach by any means, it was probably good enough to test the solver code (assuming enough walls were taken out). I also resorted to hardcoding a set of walls to remove on a small maze.

But that wasn’t good enough, and I wanted to create good and fun mazes, though those attributes are hard to define.

Now, if a maze has a single path from start to finish, then a deterministic algorithm as described in the other post will find it. Unfortunately the creation of a good and fun maze isn’t so deterministic as the generation of it must incorporate some amount of randomness that ends up presenting a good number of long-ish wrong paths. Additionally maze creation has a few constraints that make it a bit less straightforward: all cells should be reachable from the start, and there should (ideally) be exactly one path through it.

False starts

Sometimes I rush into coding without thinking enough. I think this happens when I think the problem is easier than it really is, and because I’ve coding long enough that I think I don’t need to stop and think. In any case, that’s what I did at first–I didn’t think enough and ended up going down some blind alleys, which is totally apropos solving mazes.

My first attempt was to use recursion to create a path (I guess recursion was on my brain). My code notes describe the idea:

    /**
     * The real maze maker recursive algorithm.  Not sure if it will work
     * but the idea is that each invocation of this method the current
     * position is a newly entered square and we have to randomly decide
     * which direction to go (if we move at all), subject to the following
     * conditions:
     *
     *  * each cell must have at least 1 wall
     *  * we can't open up a wall to an adjacent cell that's already been visited
     *
     * We will rotate through the 4 directions and each time we have
     * a low probability of opening up a wall in that direction.  Once
     * we open up a wall, we recurse into this method.
     */

It kept track of the “ends” of the path and if the processing of the current “end” didn’t end up reaching the finish of the maze, it reprocessed it. I graded it as a failure because it left some cells isolated and it produced more than one path through the maze (at least that specific implementation did that–it might have been able to be modified to avoid one or both of those conditions, but I didn’t pursue that).

When it was clear that that approach didn’t work, I changed the code to choose cells at random, checking if they had at least one wall missing (meaning they were connected to the start cell through some path) and then opening up one of the remaining walls at random. The code would then, using my solver, check if there was a path from start to finish, and if there was, then the first phase of the construction was done. The second phase consisted of finding all the isolated cells (those that had 4 walls still), and opening up one of those walls at random, repeating until there were no isolated cells left.

Unfortunately that didn’t work all that well either for similar reasons.

A solution?

I don’t have enough notes in code left to reconstruct the different attempts between the recursive non-solution and the queue-based one that actually does a pretty good job so I’m just going to skip to describing this workable solution.

One of the issues noted above is how the recursive algorithm(s) left some cells isolated and one of the reasons for this happening is that there’s nothing that keeps track of what to try next other than the details in the stack of recursive calls and that information is lost bit by bit when a recursive call returns.

The way around this is to explicitly keep track of the cells that are still open to being extended, where this means specifically that it’s possible to open up another wall in the cell, where opening up a wall is allowed only if there’s a cell on the other side of the wall (i.e., not off the edge of the maze) and that cell has all four walls in place. This idea of keeping a cell “in play” if it’s possible to open up another wall is key to creating a maze that doesn’t leave any isolated cells.

Now, it’s possible to keep track of these in-play cells by examining each and every cell each time it’s time to try to open up another cell/wall, but there are some downsides to this:

1. it’s expensive in time to do this as cells will be needlessly evaluated multiple times once it’s not possible to open up any more of its walls
2. there’s no way to try to create a long path by continuing to try to extend from the just-opened cell. The control of this turns out to be an important parameter of how the final maze looks.

All queued up

The idea of the queue-based solution is to retain in the queue only those cells that might be able to have another wall opened up. We first push the start cell onto the queue, as it’s by definition it has all four walls intact, then we go into a loop that does the following:

1. terminate if the queue is empty
2. pop the first cell from the queue
3. check if the cell can have another wall opened up
4. if the cell can have one or more walls opened, then randomly choose one of the possibilities and open it up, putting the just-attached cell onto the queue, and put the original cell back onto the queue
5. if the cell doesn’t have any walls that can be opened, just drop the cell by not putting it back onto the queue.

That will produce a maze with a path from start to finish. And, interestingly, it doesn’t have to check if it’s solvable as it will always be solvable.

The details of step 4 determine if the maze is interesting or not, so it’s important to look at the possibilities in step 4. Given that there are two new items to push onto the queue (the just-examined cell–call this “current”–and the just-opened cell–call this “target”) and two ends to push them onto (which is possible using Java’s Queue class), the following enumerates the raw combinations:

1. “current” at the head of the queue, and “target” at head+1
2. “current” at the head of the queue, and “target” at the tail
3. “current” at the tail, and “target” at tail-1
4. “current” at the tail, and “target” at head
5. “target” at the head, and “current” at head+1
6. “target” at the head, and “current” at tail
7. “target” at the tail, and “current” at tail-1
8. “target” at the tail, and “current” at head

There are duplicates: (4) and (6), and (2) and (8), so there are six unique ways of pushing these two cells in step 3 (this ignores the strategy of inserting both at random positions in the queue).

Since the algorithm pulls the next cell to try to extend from the head of the queue, the maze created depends on what gets pushed onto the head (if anything). If we re-push to the head the cell just taken off, then the algorithm basically expands out the cell as much as possible before moving to the next one, which has a different effect than if the just-opened cells are expanded before reprocessing.

Interesting mazes

My code allows me to choose the extension strategy so I can evaluate the effects of them on the final maze. Given that each generated maze is different (due to the use of randomness) it’s not always easy to tell what’s good or not, but in general there are some patterns: (2) and (3) produce mazes that have fairly direct and straight paths from start to finish; (7) and (8) produce slightly more visually complicated mazes than (2) and (3) but whose solutions are equally simple; (1) produces mazes with long paths from start to finish that wind up and down, which look like they’d be hard to solve but really aren’t as there aren’t many deep branches along the way; (4) looks like it produces complicated mazes (more on this below); (5) is similar to (1); and (6) is similar to (1).

Here are a few simple character-based renderings of some of the various strategies (10×10 maze):

_________________________________________
|   |   |   |   |   |   |   |   |   |   |
| →   →   →   →   →   →   ↓     | →   F |
|_ _|___|___|_ _|_ _|_ _|_ _|___|_ _|___|
__ ___________ ___ ___ ___ _______ ______
|   |   |   |   |   |   |   |   |   |   |
| ↑ |   |   |   |   |   | ↓     | ↑ |   |
|_ _|_ _|_ _|___|___|___|_ _|___|_ _|_ _|
__ ___ ___ _______________ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
| ↑   ←   ← |   |     ↓   ←     | ↑   ← |
|_ _|___|_ _|_ _|___|_ _|_ _|___|___|_ _|
__ _______ ___ _______ ___ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑   ←     | ↓ |   |       | ↑ |
|_ _|___|___|_ _|___|_ _|___|___|_ _|_ _|
__ ___________ _______ ___________ ___ __
|   |   |   |   |   |   |   |   |   |   |
|       |   | ↑     | ↓     |     →   ↑ |
|_ _|___|_ _|_ _|___|_ _|___|___|_ _|___|
__ _______ ___ _______ ___________ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     →   ↑     | →   ↓     | ↑     |
|_ _|___|_ _|___|___|___|_ _|___|_ _|___|
__ _______ _______________ _______ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑ |   |   |   | →   →   ↑     |
|_ _|___|_ _|_ _|_ _|_ _|___|_ _|_ _|___|
__ _______ ___ ___ ___ _______ ___ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑   ←   ←   ← |   |   |       |
|_ _|___|_ _|_ _|___|_ _|_ _|___|_ _|_ _|
__ _______ ___ _______ ___ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
|       |   |   |     ↑   ←     |   |   |
|_ _|___|___|___|___|___|_ _|___|___|_ _|
__ _______________________ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|                   |     S     |       |
|___|___|___|___|___|___|___|___|___|___|

and another

_________________________________________
|   |   |   |   |   |   |   |   |   |   |
| F         | ↓   ← |       |           |
|_ _|___|___|_ _|_ _|___|_ _|_ _|___|_ _|
__ ___________ ___ _______ ___ _______ __
|   |   |   |   |   |   |   |   |   |   |
| ↑   ←   ←   ← | ↑   ← |   |   |       |
|___|___|___|___|___|_ _|_ _|_ _|___|___|
______________________ ___ ___ __________
|   |   |   |   |   |   |   |   |   |   |
|                   | ↑ |   |       |   |
|_ _|___|___|___|_ _|_ _|_ _|___|_ _|_ _|
__ _______________ ___ ___ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
|   | →   →   ↓ |   | ↑   ← |       |   |
|_ _|_ _|___|_ _|___|___|_ _|_ _|___|_ _|
__ ___ _______ ___________ ___ _______ __
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |   | ↓ | →   ↓ | ↑ |   |       |
|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|___|
__ ___ ___ ___ ___ ___ ___ ___ ___ ______
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |   | →   ↑ | →   ↑ |   |       |
|_ _|_ _|_ _|___|___|_ _|___|_ _|___|_ _|
__ ___ ___ ___________ _______ _______ __
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |           |       |   |   |   |
|_ _|_ _|___|___|_ _|___|_ _|_ _|_ _|_ _|
__ ___ ___________ _______ ___ ___ ___ __
|   |   |   |   |   |   |   |   |   |   |
|     ↑   ←   ← |       |   |           |
|___|___|___|_ _|___|_ _|_ _|___|___|_ _|
______________ _______ ___ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|       | →   ↑ |   |   |   |       |   |
|_ _|___|_ _|___|_ _|_ _|___|_ _|_ _|_ _|
__ _______ _______ ___ _______ ___ ___ __
|   |   |   |   |   |   |   |   |   |   |
|         ↑   ←   ←   ←   S     |       |
|___|___|___|___|___|___|___|___|___|___|

While both of the above mazes have a solution that looks interesting, only the second one is what I’d call a maze that’s not trivial to solve, as the first one doesn’t have many “deep” branches. The second one used strategy (4) while the first one used strategy (1).

This is where more (objective) analysis of the strategies is useful but I haven’t done much on that. I can say that there appears to be a balance between the branching factor (basically a normalized number of branches for each cell along the solution path), branch depth (the maximum path length of each incorrect branch), and branch volume (how many cells each incorrect branch occupies in total). I can only say that after eyeballing a number of mazes created by each strategy that strategy (4) creates satisfying mazes–ones that provide ample opportunities to take a wrong turn.