Last time I talked about the recursive backtracker algorithm for maze generation. That?s probably always going to be my favorite algorithm for generating mazes, for a variety of reasons, but that?s not going to stop me from looking at others.
For one thing, there are some pretty crazy algorithms out there for generating mazes.
Eller?s algorithm is one of the craziest. It?s also one of the fastest. And it?s the only one I know that let?s you generate mazes of an infinite size. In linear time.
Yeah, it?s that crazy.
It does this by building the maze one row at a time, using sets to keep track of which columns are ultimately connected. But it never needs to look at more than a single row, and when it finishes, it always produces a perfect maze.
Like I did for the recursive backtracking algorithm, here?s the ?mile-high? overview of Eller?s algorithm:
- Initialize the cells of the first row to each exist in their own set.
- Now, randomly join adjacent cells, but only if they are not in the same set. When joining adjacent cells, merge the cells of both sets into a single set, indicating that all cells in both sets are now connected (there is a path that connects any two cells in the set).
- For each set, randomly create vertical connections downward to the next row. Each remaining set must have at least one vertical connection. The cells in the next row thus connected must share the set of the cell above them.
- Flesh out the next row by putting any remaining cells into their own sets.
- Repeat until the last row is reached.
- For the last row, join all adjacent cells that do not share a set, and omit the vertical connections, and you?re done!
If you?re at all like me, your head is probably spinning at this point. Let?s back up and work through an example manually, to help you see how the algorithm works in practice. Let?s begin with a simple 5-column row.
An example
First, we initialize each cell in that row to be in its own set. I?ll just assign each cell a number, indicating the set it belongs to:
___________________
| | | | | |
| 1 | 2 | 3 | 4 | 5 |
|___|___|___|___|___|
Next, we randomly join adjacent cells that belong to different sets. The cells so joined also are merged into the same set:
___________________
| | |
| 1 1 1 | 4 4 |
|___________|_______|
Now we randomly determine the vertical connections, at least one per set. The cells in the next row that we connected to must be assigned to the set of the cell above them:
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | | | |
| 1 | | 1 | | 4 |
|___| |___| |___|
Next, we flesh out the next row, assigning each remaining cell to its own set:
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | | | |
| 1 | 6 | 1 | 7 | 4 |
|___|___|___|___|___|
At this point, we can actually discard the first row, because the algorithm is done with it. We?ll keep it around for now, though, for the sake of illustration. I?ll just put a little space between the previous rows, and the current row:
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
___ ___
| | | | | |
| 1 | 6 | 1 | 7 | 4 |
|___|___|___|___|___|
Now, we just repeat the previous steps on our new row. We randomly connect adjacent sets that do not share a set. Something like this:
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|_______|_______|___|
Now we add at least one vertical connection for each set:
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
| | | |
| 1 | | 4 |
|___| |___|
And then we flesh out the next row (I?m reusing some extinct set numbers here, for the sake of single-digits):
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
| | | | | |
| 8 | 1 | 9 | 2 | 4 |
|___|___|___|___|___|
This is our current state, with history, now:
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
___ ___ ___
| | | | | |
| 8 | 1 | 9 | 2 | 4 |
|___|___|___|___|___|
It?s starting to look like a maze! Let?s do one more iteration, and then finish it out. So, first, randomly join adjacent cells from different sets:
___ ___ ___
| | | |
| 8 | 1 | 9 9 9 |
|___|___|___ ___ ___|
Then, add at least one veritcal connection for each set:
___ ___ ___
| | | |
| 8 | 1 | 9 9 9 |
| | |___ ___|
| | | | |
| 8 | 1 | | 9 |
|___|___| |___|
And flesh out the next row:
___________________
| | |
| 1 1 1 | 9 9 |
| ___ |___ |
| | | |
| 1 1 | 1 1 | 9 |
|___ |_______| |
| | | |
| 8 | 1 | 9 9 9 |
| | |___ ___|
___ ___
| | | | | |
| 8 | 1 | 3 | 9 | 5 |
|___|___|___|___|___|
And now the last row. This time, we must connect ALL adjacent (but disjoint) cells. In this case, that means all of them:
___ ___
| |
| 8 8 8 8 8 |
|___________________|
Since this is the last row, we skip the bit where we add verticals?and that means we?re done! The result, with set numbers removed, is:
___________________
| | |
| | |
| ___ |___ |
| | | |
| | | |
|___ |_______| |
| | | |
| | | |
| | |___ ___|
| |
| |
|___________________|
A perfect maze!
Analysis
Let?s analyze that a bit. It seemed to come together pretty magically, considering we weren?t looking at anything but the current row (and the next row, briefly). The key to it all are the sets.
The set that a cell belongs to tells the algorithm who its siblings were, are, and will be. It?s the crystal ball that lets the algorithm gaze into the future (and the past!) and avoid adding cycles and isolates to the maze.
Cells that share a set, also share a path between them. (If you don?t believe me, look at the example I just gave, above. Every cell that shares a set identifier is connected; cells in different sets are not connected.)
If the algorithm allowed us to create a passage between two cells that shared a set, it would be introducing a second path between those two cells. That?s essentially the definition of a loop or cycle in the graph, and since we don?t want cycles in our maze, we disallow that.
Conversely, cells that do not share a set, are not connected (they are disjoint). By the time we reach the end of the maze, every cell must be connected to every other cell, and the only way we can do that is if every set is eventually merged into a single set.
We can?t do that if a set does not propogate itself to the next row. This is why the algorithm requires that at least one vertical passage be created for each set in the row. Otherwise, any set that didn?t create a vertical passage would become extinct after the current row. The result would be an isolate, an orphaned collection of cells that could never be reached from outside that set.
Then, at the end, the algorithm joins all disjoint sets, allowing every cell in the the entire maze to be connected by a single, unique path to any other cell in the maze. And we?re done!
Implementation
How would you implement this? The key, for me, turned out to be implementing the sets. You need to be able to quickly determine the set of any given cell in a row, as well as determine the list of cells in any given set. I did this by maintaining a hash of arrays that mapped sets to cells, and another hash that mapped cells to sets. As I did in the example above, I simply used a unique integer to identify each set.
Josh Marinacci has announced that a new version of Leonardo Sketch is now available: 
an open source vector drawing program named after the 15th century painter, but aimed for the 21st century user. It focuses on common tasks like mockups, prototyping, quick vector sketches, and presentations with a clean and consistent user interface. Leo is designed to be augmented by internet webservices and plugins created in several scripting languages.
