Understanding Eller’s Algorithm

Background

So many algorithms! From the Binary Tree and Sidewinder to Kruskal’s and Prim’s and Growing Tree, we’ve learned a lot about the different methods of generating random mazes. If we’re counting Dijkstra’s, there are 11 in total.

There are only two more left to cover!

The first, called Eller’s algorithm, is a fast, efficient, and clever technique that seems born of the unlikely union of the Sidewinder algorithm and Kruskal’s.

Eller’s algorithm explained and illustrated

Marlin Eller invented Eller’s algorithm in 1982. It shares some remarkable similarities with the Sidewinder algorithm and yet manages to avoid the striking bias of that algorithm by incorporating some of the features of Kruskal’s algorithm as well.

Like Sidewinder, it works by considering only a single row at a time while building up sets (Kruskal-style) to keep track of which cells are reachable from which other cells. Let’s work through an example.

Note: We can visualize the algorithm using the slides at the end of this lesson.

1. We’ll start at the top row (for convenience’s sake), and we’ll highlight the current row in yellow to keep track of where we’re at.

2. The first thing we do is assign each cell in that row a number, effectively putting each one in a set all by itself, as we did for Kruskal’s (but on a smaller scale).

3. Then, we randomly link adjacent cells, but only if they aren’t in the same set. Like with Kruskal’s algorithm, when we link adjacent cells, we also merge the two sets. Let’s say we decide to link cells 1 and 2 (merging both into set 1), and cells 3 and 4 (merging both into set 3).

4. The next step is to choose at least one cell at random from each remaining set and carve passages south. We can choose more than one cell from any given set if we want to, but we must choose at least one. We'll choose a few cells and carve south.

5. Carving south also adds those cells to the set of the cell that linked them, allowing us to keep track of which cells are ultimately connected between rows. (This is a key difference between this algorithm and Sidewinder). Carving those passages south finishes that row, and we advance to the next one.

6. Three cells in this row already belong to a set because they were linked to cells in the previous row. The two other cells, though, need to be assigned new sets. The new sets can be assigned however we like, just so long as they are unique. We'll opt to continue counting from where the previous row left off.