Eller's Algorithm

Eller's algorithm creates 'perfect' mazes, having only a single path between any two cells, one row at a time. The algorithm itself is incredibly fast, and far more memory efficient than other popular algorithms (such as Prim's and Kruskal's) requiring storage proportional to only a single row. This makes it possible to create mazes of indefinite length on systems with limited memory.

There is very little written about Eller's Algorithm on the internet. The best source I could find (Walter Pullen's excellent Think Labyrinth website) has a single paragraph description which, while very helpful, I found inadequate to implement the algorithm. Additionally, the algorithm described in Mathematics and Physics for Programmers doesn't seem to work. Needless to say, uncovering information about this very interesting algorithm was frustrating. I was able to work out the missing details, and I'm confident that the algorithm I came up with is indeed Eller's algorithm. This page is intended to (hopefully) alleviate the suffering of future searchers interested in this facinating maze generator.

Update:At least one new useful page has appeared on the net since I first wrote this. Check out Jamis Buck'sMaze Generation: Eller's Algorithm blog post. I'll add other useful links as I find them.

The Algorithm

Note: Assume that there all left-most cells have a left-wall and all right-most cells have a right wall.

Create the first row. No cells will be members of any set

Join any cells not members of a set to their own unique set

Create right-walls, moving from left to right:

Randomly decide to add a wall or not

If the current cell and the cell to the right are members of the same set, always create a wall between them. (This prevents loops)

If you decide not to add a wall, union the sets to which the current cell and the cell to the right are members.

Create bottom-walls, moving from left to right:

Randomly decide to add a wall or not. Make sure that each set has at least one cell without a bottom-wall (This prevents isolations)

If a cell is the only member of its set, do not create a bottom-wall

If a cell is the only member of its set without a bottom-wall, do not create a bottom-wall

Decide to keep adding rows, or stop and complete the maze

If you decide to add another row:

Output the current row

Remove all right walls

Remove cells with a bottom-wall from their set

Remove all bottom walls

Continue from Step 2

If you decide to complete the maze

Add a bottom wall to every cell

Moving from left to right:

If the current cell and the cell to the right are members of a different set:

Remove the right wall

Union the sets to which the current cell and cell to the right are members.

Output the final row

A Sample Run

The example here will create a rectangular maze of indefinite length. We'll create the maze one row at a time starting at the top row and moving left to right between cells. Each cell in a row will be assigned to a set. We'll represent that here by enumerating the sets and writing the number of the set that a cell belongs to inside each cell. Each cell can have a wall on the right and on the bottom. We'll assume that a wall exists to the left of the leftmost cell and the the right of the rightmost cell in each row and that a wall exists on the top of all cells in the first row.

Step 1: Create the first row
This will just be an empty row.
	 ___ ___ ___ ___ ___ ___ ___ ___
	|                               |
	
Step 2:Join any cells not members of a set to their own unique set
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   2   3   4   5   6   7   8 |
	
Step 3:Create right walls
	 ___ ___ ___ ___ ___ ___ ___ ___
	|(1   2)  3   4   5   6   7   8 |
	
If we choose not to add a wall, union the sets
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  (1   3)  4   5   6   7   8 |

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   1  (1 | 4)  5   6   7   8 |

	... snip ...

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   1   1 | 4   4 | 6   6   6 |
	
Step 4:Create bottom walls.
Ensure that each set has at least one cell with a down passage (i.e. without a bottom wall). Failure to do so will create an isolation.
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	
Step 5.A: Create a new row.
For each cell with a down passage on the previous row, assign the cell below to the same set.
	Output the current row:
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_| <-- Output to something (line printer, etc.)
	| 1  _1_ _1_| 4  _4_| 6   6  _6_| <-- our old row is our current row

	Remove right walls:
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1  _1_ _1_  4  _4_  6   6  _6_|

	If a cell has a bottom wall, remove it from its set:
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1  ___ ___  4  ___  6   6  ___|

	Remove bottom walls:
	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1           4       6   6     |

	Continue from Step 2:

	Step 2: Join cells not members of a set to their own unique set
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___| 
	| 1   2   3   4   5   6   6   7 |
	
	Continuing to Step 3: Add Right Walls
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|(1 | 2)  3   4   5   6   6   7 | <-- added a wall
	
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 |(2   3)  4   5   6   6   7 | <-- didn't add a wall, union sets 2 and 3

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  (2   4)  5   6   6   7 | <-- didn't add a wall, union sets 2 and 4

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2  (2 | 5)  6   6   7 | <-- added a wall

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 |(5 | 6)  6   7 | <-- added a wall
	
The next two cells are members of the same set, so we MUST add a wall. Failure to do so will create loops in our maze.
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 |(6 | 6)  7 | <-- MUST add a wall

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 |(6   7)| <-- didn't add a wall, union sets 6 and 7


	Continuing to Step 4: add bottom walls
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 | 6   6 |
	
Remember: at least one cell from each set must have a down-passage (i.e. must not have a bottom wall).
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  _2_ _2_| 5 |_6_| 6  _6_|

	
You can add as many rows as you'd like this way
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|_1_  1 | 3   3 | 7  _7_ _7_| 8 |
	
Step 5.B: Complete the maze
The final row differs from a regular row in just two ways: 1) every cell has a bottom wall and 2) every cell must be a member of the same set.

Making each cell part of the same set is simple. Just remove walls between cells that are members of different sets until all the cells are part of the same set. Do not remove a wall if it separates two cells which are members of the same set.

Start by creating a normal row and add a bottom wall to each cell
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_|_3_|_3_|_7_ _7_|_8_ _8_|
	
Complete the maze by knocking down walls between cells that are members of different sets and unioning them until all cells are part of the same set.
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ (1_|_3)|_3_|_7_ _7_|_8_ _8_|
	 
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|_ _    |       |    ___ ___|   |
	|_1_ _1_ _1_|(1_|_7) _7_|_8_ _8_|

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_ _1_|_1_ _1_ (1_|_8) _8_|

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_ _1_|_1_ _1_ _1_ _1_ _1_|
	
You should now have a "perfect maze". There are no loops (ensuring only a single path exists between any two cells) and no isolations (no cell or group of cells are "blocked off" from the rest of the maze). You can assign any two cells to be the entrance and exit.
	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|___ ___ ___|___ ___ ___ ___ ___|
	

Example mazes

The following 15 x 15 maze was generated using this algorithm:

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

You can change the "texture" of your mazes by adding bias to your random number generator so that it becomes more or less likely that you create a right wall than a bottom wall. For example, you can make a maze with more long horizontal passages by creating right-walls less frequently and bottom-walls more frequently.

This is really easy to do. When deciding to add a wall, do something like the following: 1) generate a random number between 1 and 100. 2) if creating a right-wall, check that the resulting number is less than our bias value, if creating a bottom-wall, check than the number is greater than our bias value. In this case, a bias of 50 will create an even texture, like the sample maze above.

The following two sample mazes show how adding bias affects the resulting texture of a maze.

A very vertical maze:

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|  |  |     |  |   __|  |__   |  |  |  |  |  |
|  |  |__|  |   __|__   |  |  |__   |  |     |
|  |  |     |  |  |  |  |  |  |   __|__   |  |
|  |  |  |  |  |  |  |  |     |  |  |  |  |__|
|  |  |  |  |  |      __|  |  |  |  |     |  |
|  |  |  |__|__   |  |  |  |     |  |  |__   |
|  |  |  |  |  |  |  |     |  |  |     |     |
|  |  |     |     |  |  |  |__|__|  |  |  |__|
|  |  |  |     |  |  |__|  |  |  |__|  |     |
|__   |__|__|  |__|__|  |  |     |  |  |__|  |
|   __   |  |  |  |__      |  |  |  |   __|__|
|__|  |  |  |  |  |  |  |__ __|  |  |  |__   |
|  |  |  |  |  |  |  |        |  |  |  |  |  |
|  |  |  |   __|  |  |__|  |  |  |  |  |     |
|  |  |     |  |  |  |  |__|  |__   |  |  |  |
|__ __ __|__ __ __ __ __ __ __|__ __ __ __|__|

A more horizontal maze:

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|  |   __ __ __ __|   __ __ __ __ __ __ __ __|
|  |   __ __    __ __|   __ __ __ __|   __   |
|  |   __ __|__    __    __ __ __       __|  |
|__ __ __ __ __|__ __|__    __   |__|__   |__|
|   __ __ __|  |  |  |__ __   |__|__ __    __|
|__ __ __ __ __ __       __ __|__ __ __   |  |
|__ __ __ __ __ __   |__|__ __ __ __ __ __ __|
|__ __       __ __ __ __ __    __ __|      __|
|__   |  |__ __ __|__ __ __ __|__ __   |__ __|
|  |  |   __ __ __|  |__ __    __|   __|__   |
|   __ __|__ __ __    __ __ __ __ __   |   __|
|__ __   |__ __ __ __ __   |   __ __ __|   __|
|__    __ __ __    __|   __|__ __ __|__ __   |
|  |__    __ __|__|   __ __ __ __|   __ __ __|
|__ __ __       __ __|   __|   __ __|   __ __|
|__ __ __ __|__ __ __ __ __ __ __ __ __ __ __|

Home - Last modified: June 2012