Eller's algorithm for generating mazes

This is a topic-translation of the article Eller's Algorithm . It tells about the method of software generation of labyrinths. Further narration comes from the author.

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

Heller's algorithm allows you to create mazes 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 Eller algorithm on the Internet. The best source I could find ( Walter Pullen website) has only 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 Programmers , most likely, does not work. I thought about the missing parts and I am sure that the algorithm I described is in fact Eller's algorithm. In addition, you can find more information about him in the article Maze Generation: Eller's Algorithm .

Algorithm Description

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

1. Create the first line. No cell will be part of a single set.
2. Assign your unique set to non-set cells.
3. Create 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 looping)
      2. If you decide not to add a border, then combine the two sets in which the current cell is located and the cell to the right.
4. Create borders from below, moving from left to right:
   • Randomly decide to add a border or not. Make sure each set has at least one cell without a lower boundary (to prevent areas from isolating)
     1. If there is only one cell in your set, then do not create a border below.
     2. If a cell is alone in its set without a lower bound, then do not create a lower bound
5. Decide whether you will further add lines or want to complete 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 lower bound from their set
      4. Remove all lower bounds
      5. Continue from step 2
   2. If you decide to complete the labyrinth, then:
      1. Add a lower 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 current cell set and the cell to the right
            3. Print the final 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 the numbers of the sets and writing these numbers into the cell, according to their affiliation. Each cell can have a border to the right and / or bottom. We assume that the borders are 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: Attach all cells not belonging to the sets to their 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 boundary, then we combine 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 Limits

Let us make sure that each set of cells has at least one cell without a lower boundary. If this condition is not met, we will create isolated areas.

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

Step 5A: Create 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 is current 

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

Remove the lower bounds

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

Continuing from step 2:

Step 2: Join 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 |  <- added border 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  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 |  <- added border 

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

The next two cells are members of the same set, so we MUST add a border. If we do not add, it will lead to cycles in our maze.

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 | (6 | 6) 7 |  <- must add 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 of the set should not have a lower bound

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

You can add as many lines as you like.

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

Step 5B: Completing the maze

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

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

Start by creating a regular row and adding a lower border to each cell.

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

Finish the maze by 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_ | 

At the end there should be an ideal maze in which there are no cycles (there is only one way between two cells) and isolated parts (cells or groups of cells that are not connected with other parts of the maze). Now you can assign any two cells, respectively, "input" and "output".