Eller's algorithm for generating mazes

This is a topic translation of an Eller's Algorithm article . It talks about how to programmatically generate labyrinths. Further narration comes from the author.

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

Eller's algorithm allows you to create labyrinths that have only one path between two points. The algorithm itself is very fast and uses memory more efficiently than other popular algorithms (such as Prim and Kruskal), requiring memory in proportion to the number of lines. This allows you to create large mazes with limited memory sizes.



There is very little information on the Internet about the Eller algorithm. The best source I could find ( Walter Pullen website ) has just one paragraph with a description that is useful, but not enough to implement the algorithm. Also, the algorithm described in the book Mathematics and Physics for Programmersmost likely not working. I considered the missing parts and am sure that the algorithm that I described is actually Eller's algorithm. You can also find more information about it in the Maze Generation: Eller's Algorithm article .

Algorithm description

Note: we assume that the leftmost cell has a border on the left and the rightmost one on the right.

1. Create the first line. No cell will be part of any set.
2. Assign cells that are not in the set to your unique set.
3. Create the right borders, moving from left to right:
   1. Randomly decide to add a border or not
      1. If the current cell and the cell on the right belong to the same set, then create a border between them (to prevent loops)
      2. If you decide not to add a border, then combine the two sets in which the current cell and the cell to the right are located.
4. Create borders from the bottom, moving from left to right:
   • Randomly decide to add a border or not. Make sure that each set has at least one cell without a lower border (to prevent isolating areas)
     1. If there is only one cell in its set, then do not create a border from below
     2. If the cell is one in its set without a lower border, then do not create a lower border
5. Decide if you will continue to add lines or if you want to finish the maze
   1. If you want to add another line, then:
      1. Print the current line
      2. Remove all right borders
      3. Remove cells with a lower border from their set
      4. Remove all lower bounds
      5. Continue from step 2.
   2. If you decide to finish the maze, then:
      1. Add a bottom border to each cell
      2. Moving from left to right:
         1. If the current cell and the cell on the right are members of different sets, then:
            1. Remove the right border
            2. Combine the sets of the current cell and the cell to the right
            3. Print the ending line

Example

In this example, we will create a simple maze. We will begin to create it line by line, moving from top to bottom, from left to right. Each cell in the row will belong to the set. We visualize this by putting down the numbers of the sets and writing down these numbers in the cell, according to their affiliation. Each cell may have a border to the right and / or bottom. We assume that there are borders to the left of the very first and to the right of the very last cell in the row.

Step 1: Create the first line

	 ___ ___ ___ ___ ___ ___ ___ ___
	| |

Step 2: Connect all cells not belonging to the sets to our new sets

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 2 3 4 5 6 7 8 |

Step 3: Create the Borders on the Right

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

If we decide not to create a border, then we unite the sets

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

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

	...

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 1 1 | 4 4 | 6 6 6 |

Step 4: Creating Bottom Bounds

Make sure that each set of cells has at least one cell without a lower border. If this condition is not met, then we will create isolated areas.

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ |

Step 5A: Creating a New Line

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ | <- Print this line
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ | <- our previous line became current

Delete the right borders

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ |
	| 1 _1_ _1_ 4 _4_ 6 6 _6_ |

If the cell has a lower bound, remove it from the set:

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ |
	| 1 ___ ___ 4 ___ 6 6 ___ |

Delete the lower bounds

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1 _1_ _1_ | 4 _4_ | 6 6 _6_ |
	| 1 4 6 6 |

Continuing from step 2:

Step 2: Attach cells that do not belong to the sets to their unique sets

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 2 3 4 5 6 6 7 |

Step 3: Add Borders To The Right

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| (1 | 2) 3 4 5 6 6 7 | <- border added

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | (2 3) 4 5 6 6 7 | <- no border added; combine sets 2 and 3

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | 2 (2 4) 5 6 6 7 | <- no border added; combine sets 2 and 4

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

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

The next two cells are members of the same set, so we MUST add a border. If we don’t add, then this will lead to cycles in our maze

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | 2 2 2 | 5 | (6 | 6) 7 | <- must add a border

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | 2 2 2 | 5 | 6 | (6 7) | <- no border added; combine sets 6 and 7

Step 4: lower bounds

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | 2 2 2 | 5 | 6 | 6 6 |

Remember, at least one cell from the set must not have a lower boundary

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| 1 | 2 _2_ _2_ | 5 | _6_ | 6 _6_ |

You can add as many lines as you want

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| | ___ ___ | | ___ | ___ |
	| _1_ 1 | 3 3 | 7 _7_ _7_ | 8 |

Step 5B: Finishing the labyrinth

The last line differs from the usual ones in that 1) each cell has a bottom border 2) each cell must belong to one set.

Attaching cells to one set is very simple; you just need to remove the boundaries between cells that are members of different sets until they belong to the same set. Do not delete the border that separates two cells that already belong to the same set.

We start by creating a regular row and adding a bottom border to each cell.

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| | ___ ___ | | ___ | ___ |
	| ___ | | ___ ___ | |
	| _1_ _1_ | _3_ | _3_ | _7_ _7_ | _8_ _8_ |

We finish the maze, destroying the boundaries between cells belonging to different sets and combining them into one.

	 ___ ___ ___ ___ ___ ___ ___ ___
	| ___ ___ | ___ | ___ |
	| | ___ ___ | | ___ | ___ |
	| ___ | | ___ ___ | |
	| _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_ |

In the end, you should get an ideal labyrinth in which there are no cycles (there is only one path between two cells) and isolated parts (cells or groups of cells that are not connected with other parts of the labyrinth). Now you can assign any two cells, respectively, “input” and “output”.