The Buckblog

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:

1. Initialize the cells of the first row to each exist in their own set.
2. 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).
3. 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.
4. Flesh out the next row by putting any remaining cells into their own sets.
5. Repeat until the last row is reached.
6. 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.

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

For those of you not using IE (which will make a total mess of this), here are two demos you can play with to see the algorithm in action:

My complete implementation (in Ruby) is here:

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