Maze Generation: Eller’s Algorithm



Introduction

As it turned out, the topic of generating labyrinths is not much disclosed in the Russian and English-speaking communities. There is one article on Habré Eller’s algorithm for generating mazes. The article is a translation English article with a description of the algorithm step by step. In my implementation, I relied on the algorithm from the article. In the process, I encountered difficulties and misunderstood the algorithm. Therefore, I decided to analyze Eller’s algorithm in detail and clarify some points with special cases.

Basic concepts

perfect mazeit is a maze 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 to other parts of the maze).

A bunch ofit is nothing more than an unordered collection of unique elements.

Description of the algorithm
  1. Create the first line. No cell will be part of any set.

  2. Assign cells that are not in a set to their own unique set.

  3. Create the right borders by moving from left to right:

    1. Randomly decide whether 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 join the two sets that contain the current cell and the cell on the right.

  4. Create borders on the bottom, moving from left to right:

  5. Decide if you want to add more lines or if you want to finish the maze

    1. If you want to add another line then:

      1. Output the current line

      2. Remove all right borders

      3. Remove cells with bottom border from their set

      4. Remove all bottom borders

      5. Continue from step 2

    2. If you decide to end 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 right border

          2. Combine the sets of the current cell and the cell on the right

          3. Output the final line

Implementation of the algorithm in steps

Description of the labyrinth:

The maze can be stored in the file as a number of rows and columns, as well as two matrices containing the position of vertical and horizontal walls, respectively. The first matrix shows the presence of a wall to the right of each cell, and the second one shows it from below.

4 4
0 0 0 1
1 0 1 1
0 1 0 1
0 0 0 1

1 0 1 0
0 0 1 0
1 1 0 1
1 1 1 1
An example of a maze from a file
An example of a maze from a file
Maze generation method
/* Метод генерации лабиринта */
void Maze::generateMaze() {
	  /* Шаг 1 */
    fillEmptyValue();
    for (int j = 0; j < rows_ - 1; j++) {
      	/* Шаг 2 */
        assignUniqueSet();
      	/* Шаг 3 */
        addingVerticalWalls(j);
      	/* Шаг 4 */
        addingHorizontalWalls(j);
        checkedHorizontalWalls(j);
      	/* Шаг 5.1*/
        preparatingNewLine(j);
    }
  	/* Шаг 5.2 */
    addingEndLine();
}

Step 1:

Create the first line. No cell will be part of any set.

Create the first line
Create the first line
Step 1 Implementation
/* Заполним вектор пустым значением */
void Maze::fillEmptyValue() {
    for (int i = 0; i < cols_; i++) {
        sideLine_.push_back(kEmpty);
    }
}
What is kEmpty?

constexpr int kEmpty = 0;

Step 2

Assign cells that are not in a set to their own unique set.

Assigning cells a unique set
Assigning cells a unique set
Step 2 Implementation
/* Присваиваем ячейкам свое уникальное множество */
void Maze::assignUniqueSet() {
    for (int i = 0; i < cols_; i++) {
      	/* Проверяем на пустую ячейку */
        if (sideLine_[i] == kEmpty) {
          	/* Присваиваем ячейки уникальное множество */
            sideLine_[i] = counter_;
            counter_++;
        }
    }
}
What is counter_?

counter_ is the unique set generation counter.

Step 3

Create the right borders by moving from left to right:

– 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 join the two sets that contain the current cell and the cell on the right.

What is a number?

By number, I mean the location of the cell in the maze. This should not be confused with many

We put the right wall at the cell number 2
We put the right wall at the cell number 2
We combine two sets in which the current cell and the cell on the right are located
We combine two sets in which the current cell and the cell on the right are located
We put the right wall at the cell number 3
We put the right wall at the cell number 3
We combine two sets in which the current cell and the cell on the right are located
We combine two sets in which the current cell and the cell on the right are located
Step 3 Implementation
/* Добавление правой вертикальной стенки */
void Maze::addingVerticalWalls(int row) {
    for (int i = 0; i < cols_ - 1; i++) {
      	/* Ставим стенку или нет */
        bool choise = randomBool();
      	/* Проверка условия для предотовращения зацикливания */
        if (choise == true || sideLine_[i] == sideLine_[i + 1]) {
            v_walls_(row, i) = true;
        } else {
          	/* Объединение ячеек в одно множество */
            mergeSet(i, sideLine_[i]);
        }
    }
  	/* Добавление правой стенки в последней ячейки */
    v_walls_(row, cols_ - 1) = true;
}

/* Объединение ячеек в одно множество */
void Maze::mergeSet(int index, int element) {
    int mutableSet = sideLine_[index + 1];
    for (int j = 0; j < cols_; j++) {
      	/* Проверка ячеек на одно множество */
        if (sideLine_[j] == mutableSet) {
          	/* Объединение ячейки в множество */
            sideLine_[j] = element;
        }
    }
}

Step 4

Create borders on the bottom, moving from left to right:

– Randomly decide to add a border or not. Make sure each set has at least one cell with no bottom border (to prevent areas being isolated):

1. If there is only one cell in its set, then do not create a bottom border

2. If the cell is alone in its set without a bottom border, then do not create a bottom border

Let's create a bottom border in cell number 2, since 1 set has at least one cell without a bottom border
Let’s create a bottom border in cell number 2, since 1 set has at least one cell without a bottom border

In cell number 3, we cannot add a bottom wall, since cell in set 3 is one

Step 4 Implementation
/* Добавление нижней горизонтальной стенки */
void Maze::addingHorizontalWalls(int row) {
    for (int i = 0; i < cols_; i++) {
      	/* Ставим стенку или нет */
        bool choise = randomBool();
      	/* Проверка, что множество имеет более одной ячейки (это предовратит замкнутые области  */
        if (calculateUniqueSet(sideLine_[i]) != 1 && choise == true) {
          	/* Ставим горизонтальную стенку */
            h_walls_(row, i) = true;
        }
    }
}

/* Подсчет ячеек, которые содержаться в уникальном множестве */
int Maze::calculateUniqueSet(int element) {
    int countUniqSet = 0;
    for (int i = 0; i < cols_; i++) {
        if (sideLine_[i] == element) {
            countUniqSet++;
        }
    }
    return countUniqSet;
}

/* Проверка условие 4.1 и 4.2 */
void Maze::checkedHorizontalWalls(int row) {
    for (int i = 0; i < cols_; i++) {
        if (calculateHorizontalWalls(sideLine_[i], row) == 0) {
            h_walls_(row, i) = false;
        }
    }
}

/* Подсчет горизонтальных стен у ячеек уникального множества */
int Maze::calculateHorizontalWalls(int element, int row) {
    int countHorizontalWalls = 0;
    for (int i = 0; i < cols_; i++) {
        if (sideLine_[i] == element && h_walls_(row, i) == false) {
            countHorizontalWalls++;
        }
    }
    return countHorizontalWalls;
}

Step 5.1

If you want to add another line then:

one. Output the current line

2. Remove all right borders

3. Remove cells with bottom border from their set

4. Remove all bottom borders

5. Continue from step 2

Copy the current line
Copy the current line
Removing the right side
Removing the right side
Removing a cell with a bottom border
Removing a cell with a bottom border
Removing all bottom borders
Removing all bottom borders
Implementation of step 5.1
void Maze::preparatingNewLine(int row) {
    for (int i = 0; i < cols_; i++) {
        if (h_walls_(row, i) == true) {
          	/* Присваиваем ячейки пустое множество */
            sideLine_[i] = kEmpty;
        }
    }
}

We continue the algorithm to the last line:

Step 2. Assign a Unique Set to Empty Cells

Cell number 2 is assigned sets 5
Cell number 2 is assigned sets 5

Step 3 Creating the Right Borders

Let's add the right wall, since cell number 4 and 5 are from one unique set
Let’s add the right wall, since cell number 4 and 5 are from one unique set

Steps 4 and 5: Create a Bottom Border and Copy a Row

Added a horizontal wall at cell number 5
Added a horizontal wall at cell number 5

We generate a new line:

New line generation
New line generation

Generation of the last line of the maze

Step 2. Assign a Unique Set to Empty Cells

Cells numbered 2 and 5 are assigned a unique set
Cells numbered 2 and 5 are assigned a unique set

Step 3 Creating the Right Borders

Adding a right border in cell number 1
Adding a right border in cell number 1
If we decide not to add a right border in cell number 2, then what unique set will cell number 2 and 3 belong to?

1 or 7 (change all cells belonging to set 1 to 7)

Result of adding right walls
Result of adding right walls

Skip step 4 as this is our last line

Step 5.2

If you want to finish the maze then:

Add a bottom border to each cell:

Moving from left to right:

1. If the current cell and the cell on the right are members of different sets, then:

1.1 Remove right border

1.2 Combine the sets of the current cell and the cell on the right

1.3 Print the final line

We delete the right wall at the cell number 4, since they are of a different set and combine the set
We delete the right wall at the cell number 4, since they are of a different set and combine the set
Implementation of step 5.2
/* Добавление последней строки */
void Maze::addingEndLine() {
    assignUniqueSet();
    addingVerticalWalls(rows_ - 1);
    checkedEndLine();
}

/* Проверка условий на добавление последней строки */
void Maze::checkedEndLine() {
    for (int i = 0; i < cols_ - 1; i++) {
      	/* Проверка условия пункта 5.2.1 */
        if (sideLine_[i] != sideLine_[i + 1]) {
          	/* Убираем вертикальную стенку */
            v_walls_(rows_ - 1, i) = false;
          	/* Объединяем множества */
            mergeSet(i, sideLine_[i]);
        }
      	/* Добавляем горизонтальные стенки */
        h_walls_(rows_ - 1, i) = true;
    }
  	/* Добавляем горизонтальную стенку в последней ячейке */
    h_walls_(rows_ - 1, cols_ - 1) = true;
}

Conclusion

Above, I demonstrated how the implementation of the Eller algorithm looks like, you can try to implement it according to my article.

The project code with the algorithm from the article can be found at Github.

Thank you for attention! I hope I have shared something new and interesting for you.

If you liked the article, then please write about it in the comments. I will be very glad to any criticism.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *