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 maze – it 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 of – it is nothing more than an unordered collection of unique elements.

Description of the algorithm

Create the first line. No cell will be part of any set.
Assign cells that are not in a set to their own unique set.
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.
Create borders on the bottom, moving from left to right:
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.

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.

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.

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

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

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

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

We generate a new line:

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

Step 3 Creating the Right Borders

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)

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

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.

Maze Generation: Eller’s Algorithm

Introduction

Basic concepts

Implementation of the algorithm in steps

Description of the labyrinth:

Step 1:

Step 2

Step 3

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

Step 4

Step 5.1

We continue the algorithm to the last line:

Step 5.2

Conclusion

Another review of another course. Or how I studied as a system analyst at Netology

Top 7 Highly Paid AI Jobs

Connecting Tinkoff payment to Telegram bot in pure php

“Principles of Changing the World Order. Why Some Nations Win and Others Fail”

About choosing an IT university and specialty

The plane decided to land

Leave a Reply Cancel reply

Introduction

Basic concepts

Implementation of the algorithm in steps

Description of the labyrinth:

Step 1:

Step 2

Step 3

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

Step 4

Step 5.1

We continue the algorithm to the last line:

Step 5.2

Conclusion

Similar Posts

Leave a Reply Cancel reply