![](https://habrastorage.org/getpro/habr/upload_files/6f4/d63/b8b/6f4d63b8b050b8b7008e73acb61095ce.gif)
Вступление
Оказалось, что тема генерации лабиринтов не сильно раскрывается в русско- и англоязычном сообществе. На хабре существует одна статья Алгоритм Эллера для генерации лабиринтов. Статья, является переводом англоязычной статьи с описанием алгоритма по шагам. В своей реализации, я опирался на алгоритм из статьи. В процессе я столкнулся с трудностями и недопонимаем алгоритма. Поэтому я решил подробно разобрать алгоритм Эллера и разъяснить некоторые моменты с особенными случаями.
Базовые понятия
Идеальный лабиринт - это лабиринт в котором нет циклов (между двумя ячейками есть только один путь) и изолированных частей (ячейки или групп ячеек, которые не связаны с другими частями лабиринта).
Множество - это не более чем неупорядоченная коллекция уникальных элементов.
Описание алгоритма
Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
Присвойте ячейкам, не входящим в множество, свое уникальное множество.
-
Создайте правые границы, двигаясь слева направо:
-
Случайно решите добавлять границу или нет
Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
-
-
Создайте границы снизу, двигаясь слева направо:
-
Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей)
Если ячейка в своем множестве одна, то не создавайте границу снизу
Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
-
-
Решите, будете ли вы дальше добавлять строки или хотите закончить лабиринт
-
Если вы хотите добавить еще одну строку, то:
Выведите текущую строку
Удалите все правые границы
Удалите ячейки с нижней границей из их множества
Удалите все нижние границы
Продолжайте с шага 2
-
Если вы решите закончить лабиринт, то:
Добавьте нижнюю границу к каждой ячейке
-
Двигаясь слева направо:
-
Если текущая ячейка и ячейка справа члены разных множеств, то:
Удалите правую границу
Объедините множества текущей ячейки и ячейки справа
Выведите завершающую строку
-
-
Реализация алгоритма по шагам
Описание лабиринта:
Лабиринт может храниться в файле в виде количества строк и столбцов, а также двух матриц, содержащих положение вертикальных и горизонтальных стен соответственно. В первой матрице отображается наличие стены справа от каждой ячейки, а во второй - снизу.
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
![Пример лабиринта из файла Пример лабиринта из файла](https://habrastorage.org/getpro/habr/upload_files/d6e/d01/55a/d6ed0155a6e3c862f8c669cb35d1fc7e.jpg)
Метод генерации лабиринта
/* Метод генерации лабиринта */
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();
}
Шаг 1:
Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
![Создаем первую строку Создаем первую строку](https://habrastorage.org/getpro/habr/upload_files/454/111/d90/454111d906ad1e2c2f2ab37df8fd6d1f.png)
Реализация шага 1
/* Заполним вектор пустым значением */
void Maze::fillEmptyValue() {
for (int i = 0; i < cols_; i++) {
sideLine_.push_back(kEmpty);
}
}
Что такое kEmpty?
constexpr int kEmpty = 0;
Шаг 2
Присвойте ячейкам, не входящим в множество, свое уникальное множество.
![Присваиваем ячейкам уникальное множество Присваиваем ячейкам уникальное множество](https://habrastorage.org/getpro/habr/upload_files/69d/0e5/568/69d0e556836688ad168ee154025fac81.png)
Реализация шага 2
/* Присваиваем ячейкам свое уникальное множество */
void Maze::assignUniqueSet() {
for (int i = 0; i < cols_; i++) {
/* Проверяем на пустую ячейку */
if (sideLine_[i] == kEmpty) {
/* Присваиваем ячейки уникальное множество */
sideLine_[i] = counter_;
counter_++;
}
}
}
Что такое counter_?
counter_ - это счетчик генерации уникальных множеств.
Шаг 3
Создайте правые границы, двигаясь слева направо:
- Случайно решите добавлять границу или нет:
1. Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
2. Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
Что такое номер?
Под номером я понимаю расположение ячейки в лабиринте. Не стоит путать это с множеством
![Ставим правую стенку у ячейки под номером 2 Ставим правую стенку у ячейки под номером 2](https://habrastorage.org/getpro/habr/upload_files/e6a/6bf/755/e6a6bf755d64de8185ee4585d8d86f31.png)
-
Создайте правые границы, двигаясь слева направо:
-
Случайно решите добавлять границу или нет
Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
-
![Объединяем два множества в котором находится текущая ячейка и ячейка справа Объединяем два множества в котором находится текущая ячейка и ячейка справа](https://habrastorage.org/getpro/habr/upload_files/6c8/fa8/307/6c8fa830758f7be66e22d57849d7870c.png)
![Ставим правую стенку у ячейки под номером 3 Ставим правую стенку у ячейки под номером 3](https://habrastorage.org/getpro/habr/upload_files/069/881/820/069881820fe772789b9f05112c9f9f9a.png)
![Объединяем два множества в котором находится текущая ячейка и ячейка справа Объединяем два множества в котором находится текущая ячейка и ячейка справа](https://habrastorage.org/getpro/habr/upload_files/441/d59/517/441d5951719067eb91992deeab946685.png)
Реализация шага 3
/* Добавление правой вертикальной стенки */
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;
}
}
}
Шаг 4
Создайте границы снизу, двигаясь слева направо:
- Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей):
1. Если ячейка в своем множестве одна, то не создавайте границу снизу
2. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
![Создадим нижнюю границу в ячейке под номером 2, так-как 1 множество имеет хотя бы одну ячейку без нижней границы Создадим нижнюю границу в ячейке под номером 2, так-как 1 множество имеет хотя бы одну ячейку без нижней границы](https://habrastorage.org/getpro/habr/upload_files/acc/d7a/6a4/accd7a6a4c802139bedddd20de82c7e2.png)
В ячейке под номером 3 не можем добавить нижнюю стенку, так-как ячейка в множестве 3 одна
Реализация шага 4
/* Добавление нижней горизонтальной стенки */
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;
}
Шаг 5.1
Если вы хотите добавить еще одну строку, то:
1. Выведите текущую строку
2. Удалите все правые границы
3. Удалите ячейки с нижней границей из их множества
4. Удалите все нижние границы
5. Продолжайте с шага 2
![Копируем текущую строку Копируем текущую строку](https://habrastorage.org/getpro/habr/upload_files/82d/e60/2a6/82de602a6ea6b8a958e53549f388b612.png)
![Удаляем правые стенки Удаляем правые стенки](https://habrastorage.org/getpro/habr/upload_files/91e/b2f/898/91eb2f8980e828cfb66c91b759b704a0.png)
![Удаляем ячейку с нижней границей Удаляем ячейку с нижней границей](https://habrastorage.org/getpro/habr/upload_files/2d4/aee/818/2d4aee8183d907401e86f018ed121b81.png)
![Удаляем все нижние границы Удаляем все нижние границы](https://habrastorage.org/getpro/habr/upload_files/a73/445/052/a734450528b92ca914189c165c2b319f.png)
Реализация шага 5.1
void Maze::preparatingNewLine(int row) {
for (int i = 0; i < cols_; i++) {
if (h_walls_(row, i) == true) {
/* Присваиваем ячейки пустое множество */
sideLine_[i] = kEmpty;
}
}
}
Продолжаем алгоритм до последней строки:
Шаг 2. Присваиваем пустым ячейкам уникальное множество
![Ячейке под номером 2 присваиваем множества 5 Ячейке под номером 2 присваиваем множества 5](https://habrastorage.org/getpro/habr/upload_files/f54/b74/773/f54b747734d879ac884b41bc5c233b11.png)
Шаг 3. Создание правых границ
![Добавим правую стенку, так-как ячейка под номером 4 и 5 из одного уникального множества Добавим правую стенку, так-как ячейка под номером 4 и 5 из одного уникального множества](https://habrastorage.org/getpro/habr/upload_files/381/a82/b50/381a82b50c5cfd62bf4ba4b4bf79d5b4.png)
Шаги 4 и 5. Создание нижней границы и копирование строки
![Добавили горизонтальную стенку у ячейки под номером 5 Добавили горизонтальную стенку у ячейки под номером 5](https://habrastorage.org/getpro/habr/upload_files/f5d/1dc/478/f5d1dc4789757a2d0fec25b14a286ca5.png)
Генерируем новую строку:
![Генерация новой строки Генерация новой строки](https://habrastorage.org/getpro/habr/upload_files/5a6/a21/540/5a6a2154083c0cf61b523411cef93bf4.png)
Генерация последней строки лабиринта
Шаг 2. Присваиваем пустым ячейкам уникальное множество
![Ячейкам под номерами 2 и 5 присваиваем уникальное множество Ячейкам под номерами 2 и 5 присваиваем уникальное множество](https://habrastorage.org/getpro/habr/upload_files/b28/2a5/97c/b282a597c970e17f28c41b1b00f50256.png)
Шаг 3. Создание правых границ
![Добавляем правую границу в ячейке под номером 1 Добавляем правую границу в ячейке под номером 1](https://habrastorage.org/getpro/habr/upload_files/cca/b73/7a6/ccab737a6efdb0494a2da6def68e6a73.png)
Если мы решаем не добавлять правую границу в ячейке под номером 2, то к какому уникальному множеству будут принадлежать ячейка под номером 2 и 3?
1 или 7 (все ячейки принадлежащие к множеству 1 изменить на 7)
![Результат добавления правых стенок Результат добавления правых стенок](https://habrastorage.org/getpro/habr/upload_files/0a3/c18/da5/0a3c18da52116b041627905d9fd97296.png)
Пропускаем шаг 4, так-как это наша последняя строка
Шаг 5.2
Если вы хотите закончить лабиринт, то:
Добавьте нижнюю границу к каждой ячейке:
Двигаясь слева направо:
1. Если текущая ячейка и ячейка справа члены разных множеств, то:
1.1 Удалите правую границу
1.2 Объедините множества текущей ячейки и ячейки справа
1.3 Выведите завершающую строку
![Удаляем правую стенку у ячейки под номером 4, так-как они разного множества и объединяем множество Удаляем правую стенку у ячейки под номером 4, так-как они разного множества и объединяем множество](https://habrastorage.org/getpro/habr/upload_files/a05/497/b00/a05497b0098319f361fad2e514a99cb9.png)
Реализация шага 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;
}
Вывод
Выше я продемонстрировал как выглядят реализация алгоритма Эллера, вы можете попробовать реализовать его по моей статье.
Код проекта с алгоритмом из статьи можно найти на Github.
Благодарю за внимание! Надеюсь, я поделился чем-то новым и интересным для вас.
Если вам понравилась статья – то, пожалуйста, напишите об этом в комментарии. Буду очень рад любой критике.
Комментарии (8)
dkrivoshapova
24.05.2022 18:40+4Спасибо, очень подробно и понятно написано. Успехов вам в ваших начинаниях
Rikhmayer
25.05.2022 10:24+6Идеальный лабиринт - это лабиринт в котором нет циклов (между двумя ячейками есть только один путь) и изолированных частей (ячейки или групп ячеек, которые не связаны с другими частями лабиринта)
Страшный сон Пакмана.
Browning
25.05.2022 15:54Тема генерации лабиринтов как раз раскрыта на Хабре неплохо: по тегу "генерация лабиринтов", который даже проставлен у этого поста, есть немало интересных постов. (На один из них уже есть ссылка в верхнем комменте.)
Yermack
И еще на других языках: