The maze book for programmers!

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

# The Buckblog

## Maze Generation: Eller's Algorithm

29 December 2010 — A clever technique is demonstrated for generating a random maze, one row at a time — 9-minute read

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?

All the mazes you’ve generated in these articles have no start/end openings. Is it true that no matter where you poke two holes in the outer wall, they will be connected? It seems like each of the algorithms produces a single non-disjoint “tiling” of the maze, but do these algorithms guarantee that?

Can this be tweaked to generate uni-cursal mazes, in other words, Labyrinths instead of mazes?

I have been designing labyrinths manually and this would certainly be a great help.

Thanks.

Very good read. I’ve come across this algorithm before and didn’t fully understand it, but your walkthrough makes much more sense to me now.

A while back when bored I was able to implement a modified/misinterpreted Eller’s algorithm using only formulas and conditional formatting in Excel or OpenOffice.

Every row’s leftmost cell contained a 1. For every other row in the grid, a random function determines whether the next cell was 1+Previous (same set) or reset to 1 (new set). (You can add vertical bias by favoring the reset option, or horizontal bias by favoring the 1+Previous option.)

Every row also had a random digit generated between 2 and the maximum number used in that row to determine where a vertical connection was made upward (call it X).

Conditional formatting worked like this: - Add a left-side wall if the cell contains a 1. - Add a top-side wall if: ... the cell contains a digit higher than X ... the cell contains a digit lower than X AND the cell immediately to it’s right does NOT contain 1. (This rule is used for when a set’s width is smaller than X to ensure that a vertical path is available.)

I’m not sure my explanation entirely makes sense, so you can grab this OpenOffice spreadsheet if you’re interested in seeing what I mean:

http://www.thegriddle.net/maze/other/eller.ods

Thanks for the great read/explanation on how the algorithm works. :)

Is there a date for Eller’s Algorithm? I ask this because, I remember coming up with this exact solution in high school in 1984-5 or 1986 at the latest, and implementing it in Applesoft Basic on an Apple ][. Sadly, back then, awesome programming skills did not attract the attention of girls. I know it is different today with all girls checking over the elegance of your haskell code.

Amazingly, your unicursal maze exactly corresponds to the floor plan of my local Ikea store.

I encountered a program written in BASIC in around about 1983 or so, that must have been implementing this algorithm or one like it. I could never understand how it did it, and sadly I lost the listing when I upgraded from my Commodore CBM-8032 to a more modern MS-DOS compatible 8086 computer. It’s only taken 27 years, but thanks for finally explaining the mystery for me!

excellent article, very good illustrations!

That’s incredible.

I attended a programming competition in high school, years ago, where we were challenged to write a program that drew random, solvable mazes. We had to complete the task in 1 hour. The implementation we came up with was naive at best, and didn’t meet the requirements. Had we been aware of such an algorithm, we would have definitely had a solution. However, our high school never taught algorithms, only simple programming languages: unfortunately, Turing. The focus was on how to write in some language, but not actually get into algorithms.

Also see John Tromp’s IOCCC winner, described at http://homepages.cwi.nl/~tromp/maze.html, and Carl Shapiro’s IOCCC winner before that.

 ```1 2 3 4 5 6 7 ``` ```char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C); -- E; J[ E] =T [E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|" ) , A = 39 ,C -- ) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C & A == T[ A] |6<<27

I asked the maintainer of “Think Labyrinth” about the origin of Eller’s algorithm and here was his response:

“Eller’s algorithm is named after computer programmer Marlin Eller, CEO of sunhawk.com. He invented this algorithm in 1982, which is the earliest use of it I know of. He never published it, but he did tell me about it, so I chose to name the algorithm after him.”

What would you call a maze that is “perfect” w.r.t. the solution path, i.e. there is only a single path from start to finish, but the non-solution areas can have loops? In other words, something between perfect and braid. To see what I mean, download Amaze from qtamaze.sf.net, run it, and slide the “Cuts” value to a non-zero value. B.t.w. the biggest single improvement in maze quality for that program’s algorithm comes from cutting short any loops in the naive solution path, where the path passes by itself one cell over; this tends to cut the path length by 70-90%.

@Jamis, I think it depends on where the loop occurs. Analogously (topologically equivalent) you can think of the solution path as a long corridor with doors going off into different rooms, which may contain further walls. In a perfect maze, the rooms are not interconnected, except through that corridor. My question concerns the case where the rooms themselves may have free-standing walls inside them, so you can circle around inside a room, but any such loop will never take you between two points on the corridor; you can only enter/exit a room through the same door. The definition of “perfect” seems to preclude free-standing walls even if they never lead to connections between the rooms, i.e. never cause alternate solution paths to exist.

@Jamis, one source of confusion may be how you enter the maze: you say “placed inside the maze”, whereas I assume the maze has a single defined entrance. My earlier comment only applies to mazes with a single defined entrance and exit point. I think retracing steps would not count as a loop, otherwise a loop-free maze cannot exits: imagine a T-shaped, 4-cell maze, enter on top left, exit top right; you can walk either straight from the entrance to the exit, or take a one-step detour into the dangling single cell below. The second path, where you go off the path and then retrace through the same cell, should not, I think, be counted as an alternative path. What do you think? (PS: This is a fascinating topic, thanks for taking the time to reply!)

@Jamis, thanks for the definitions of terms, it clear up confusion a lot; what I though of as a “path” corresponds to what you define as “shortest path”. So using your definition, if you have a 2-cell maze with cells 1 and 2, and start/end S and E, then S->1->2->E is the shortest path and a path, but S->1->2->1->2->E is just a path, right? Any path containing two visits to the same cell is non-shortest, and the subpath between those two visits is a “loop”. A dead-end is a special case of a loop, where the first half mirrors the second. And a “perfect maze” is a maze where there is exactly 1 shortest-path between any two cells. And a braid is a maze where there is at least 1 shortest-path between any two cells.

In that case, the class of mazes I was talking about could be defined as having exactly 1 shortest-path between the entrance and exit cell, and at least 1 shortest-path between any two cells in the maze. In other words, the non-self-intersecting traversal path from start to end is unique, but the same for any other pair of cells may not be.

@Jamis, btw. sorry if I seem to be harping on about the specific cases. Just wanted to clarify that in order for a maze (as a puzzle) to have a single valid “answer”/”solution” (non-self-intersecting path from start to end), it is not required to be a “perfect maze”.

@Jamis, I agree with your assertions above. However, the distinction I was making between a braided maze and the (nameless so far) other maze class is a single issue about those non-self-intersecting paths: in a braided maze, there may be multiple non-self-intersecting paths between any two cells (and there will be at least one, as you state); in the “other” kind of maze, for the specific case only of the start and end cells, there cannot be multiple non-self-intersecting paths. This means that if “solving” a maze is defined as finding any non-self-intersecting path from start to end, then for a braided maze you might come up with multiple valid solutions, but for the other maze kind (just like for a perfect maze) the solution is guaranteed to be unique.

Here’s a picture of an example: there is only 1 non-self-intersecting path between the entry and exit (the dotted line), but the right half does contain a loop. Link: https://picasaweb.google.com/lh/photo/qGOcjje4fjjoomfN22gWgXqdrwFdBJ6iIsF9YwO7n70?feat=directlink

@Jamis, you’re right, the difference I described is only in the constraints, not the general topology. As a technicality, the selection of the start and end points in this program takes place before building the maze, so the constraint is actually a feature of the maze building algorithm. Maybe the classification in my mind was more about maze generation algorithms than the overall topology of the result (comes from spending more time programming mazes than than actually looking at them). In that case, allow me to reformulate: An algorithm that builds a cell-based maze from a given start and end point can fulfill the constraint of producing a fully connected maze with only a single non-self-intersecting path between those two points, without having to produce a perfect maze. Would you agree with this more limited statement?

(Detail: This algorithm does actually start off producing a perfect maze. It then shortens the solution by short-circuiting near-loops. Then it divides the maze into zones corresponding to interconnected cells from a single side-passage of the solution, and chops up walls inside zones.)

@Jamis, thanks! There’s no good write-up of the algorithm right now, but I’m adding one to the qtamaze development documentation. I’ll post a link when it’s all done, looking forward to your comments.

@jamis, I put a better description of the algorithm into the dev doc, it is parts 4.1 and 4.2, on pages 4 through 7, of this PDF: http://qtamaze.sourceforge.net/dev.pdf—enjoy!