Jamis Buck: Maze Generation: Eller’s Algorithm
Dec 30, 2010
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: 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. 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: Next, we randomly join adjacent cells that belong to different sets. The cells so joined also are merged into the same set: 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: Next, we flesh out the next row, assigning each remaining cell to its own set: 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: 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: Now we add at least one vertical connection for each set: And then we flesh out the next row (I?m reusing some extinct set numbers here, for the sake of single-digits): This is our current state, with history, now: 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: Then, add at least one veritcal connection for each set: And flesh out the next row: And now the last row. This time, we must connect ALL adjacent (but disjoint) cells. In this case, that means all of them: 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! 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! 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.
An example
___________________
| | | | | |
| 1 | 2 | 3 | 4 | 5 |
|___|___|___|___|___|
___________________
| | |
| 1 1 1 | 4 4 |
|___________|_______|
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | | | |
| 1 | | 1 | | 4 |
|___| |___| |___|
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | | | |
| 1 | 6 | 1 | 7 | 4 |
|___|___|___|___|___|
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
___ ___
| | | | | |
| 1 | 6 | 1 | 7 | 4 |
|___|___|___|___|___|
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|_______|_______|___|
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
| | | |
| 1 | | 4 |
|___| |___|
___ ___
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
| | | | | |
| 8 | 1 | 9 | 2 | 4 |
|___|___|___|___|___|
___________________
| | |
| 1 1 1 | 4 4 |
| ___ |___ |
| | | |
| 1 1 | 1 1 | 4 |
|___ |_______| |
___ ___ ___
| | | | | |
| 8 | 1 | 9 | 2 | 4 |
|___|___|___|___|___|
___ ___ ___
| | | |
| 8 | 1 | 9 9 9 |
|___|___|___ ___ ___|
___ ___ ___
| | | |
| 8 | 1 | 9 9 9 |
| | |___ ___|
| | | | |
| 8 | 1 | | 9 |
|___|___| |___|
___________________
| | |
| 1 1 1 | 9 9 |
| ___ |___ |
| | | |
| 1 1 | 1 1 | 9 |
|___ |_______| |
| | | |
| 8 | 1 | 9 9 9 |
| | |___ ___|
___ ___
| | | | | |
| 8 | 1 | 3 | 9 | 5 |
|___|___|___|___|___|
___ ___
| |
| 8 8 8 8 8 |
|___________________|
___________________
| | |
| | |
| ___ |___ |
| | | |
| | | |
|___ |_______| |
| | | |
| | | |
| | |___ ___|
| |
| |
|___________________|
Analysis
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
@sets = Hash.new { |h,k| h[k] = [] } @cells = {} def same?(cell1, cell2) @cells[cell1] == @cells[cell2] end def add(cell, set) @cells[cell] = set @sets[set] << cell self end def each_set @sets.each do |id, set| yield id, set end end |
The process of merging two sets is O(n) as I?ve implemented it, but given that n is fairly small, that didn?t worry me too much:
1 2 3 4 5 6 7 |
def merge(sink_cell, target_cell) sink, target = @cells[sink_cell], @cells[target_cell] @sets[sink].concat(@sets[target]) @sets[target].each { |cell| @cells[cell] = sink } @sets.delete(target) end |
There?s plenty of room for optimization there, though.
Lastly, assigning set ids is done via a #populate method:
1 2 3 4 5 6 7 8 9 10 11 |
def populate width.times do |cell| unless @cells[cell] set = @next_set += 1 @sets[set] << cell @cells[cell] = set end end self end |
Once I had these routines (encapsulated into a State class), the algorithm itself came fairly neatly. It works in two steps, plus a third to convert the representation into something easier to display.
The first step looks over the row and randomly connects adjacent cells (if they exist in disjoint sets):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
connected_sets = [] connected_set = [0] (state.width-1).times do |c| if state.same?(c, c+1) || (!finish && rand(2) > 0) # cells are not joined by a passage, so we start a new connected set connected_sets << connected_set connected_set = [c+1] else state.merge(c, c+1) connected_set << c+1 end end connected_sets << connected_set |
As you can see, the process simply looks at each cell and its neighbor, comparing their states and then either adding the cells to a ?connected set? (a series of adjacent cells that are all horizontally connected) and merging the sets together, or creating a new connected set when the two cells should not be merged.
The finish variable is used to change the behavior for the final row; it is false for the rest of the rows.
The second step looks at the available sets and randomly adds vertical connections:
1 2 3 4 5 6 7 8 9 10 |
verticals = [] next_state = state.next unless finish state.each_set do |id, set| cells_to_connect = set.sort_by { rand }[0, 1 + rand(set.length-1)] verticals.concat(cells_to_connect) cells_to_connect.each { |cell| next_state.add(cell, id) } end end |
State#next just returns a new State object (that we?re using for the next row). Then, for each set of cells, we randomly pick some number of them and add them to the list of verticals we?re going to create. (The verticals are also added to the next row, in the same set.)
The algorithm itself then loops over these steps repeatedly, setting state to next_state at the end of each pass, until it is done. (In my case, I trapped the INT signal, so ctrl-C can be used to terminate the algorithm and gracefully finish the maze.)
My complete implementation is here:
<noscript>ellers.rb on gist.github.com</noscript>
I think Eller?s algorithm is harder to customize than the recursive backtracking algorithm, but it can be done. Consider it an exercise, if you want: how would you introduce horizontal or vertical bias into the maze? (I.e., how would you make the maze prefer longer corridors, either horizontally or vertically?) How would you implement weave mazes, where the passages move over or under other passages? Especially tricky: how would you introduce symmetry into the output, given that the algorithm itself doesn?t look at anything more than the single row?
If nothing else, though, please give Eller?s algorithm a shot. Please share your implementations (in any language!) in the comments (links to gist.github.com are preferred).
