Вступление
Как оказалось, что тема генерации лабиринтов не сильно раскрывается в русско- и англоязычном сообществе. На хабре существует одна статья Алгоритм Эллера для генерации лабиринтов. Статья, является переводом англоязычной статьи с описанием алгоритма по шагам. В своей реализации, я опирался на алгоритм из статьи. В процессе я столкнулся с трудностями и недопонимаем алгоритма. Поэтому я решил подробно разобрать алгоритм Эллера и разъяснить некоторые моменты с особенными случаями.
Базовые понятия
Идеальный лабиринт - это лабиринт в котором нет циклов (между двумя ячейками есть только один путь) и изолированных частей (ячейки или групп ячеек, которые не связаны с другими частями лабиринта).
Множество - это не более чем неупорядоченная коллекция уникальных элементов.
Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества. Присвойте ячейкам, не входящим в множество, свое уникальное множество. Создайте правые границы, двигаясь слева направо: Случайно решите добавлять границу или нет Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний) Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
Создайте границы снизу, двигаясь слева направо: Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей) Если ячейка в своем множестве одна, то не создавайте границу снизу Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу Решите, будете ли вы дальше добавлять строки или хотите закончить лабиринт Если вы хотите добавить еще одну строку, то:
Выведите текущую строку Удалите все правые границы Удалите ячейки с нижней границей из их множества Удалите все нижние границы Продолжайте с шага 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
Метод генерации лабиринта
/* Метод генерации лабиринта */
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:
Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
Реализация шага 1
/* Заполним вектор пустым значением */
void Maze::fillEmptyValue() {
for (int i = 0; i < cols_; i++) {
sideLine_.push_back(kEmpty);
}
}
Что такое kEmpty?
constexpr int kEmpty = 0;
Шаг 2
Присвойте ячейкам, не входящим в множество, свое уникальное множество.
Реализация шага 2
/* Присваиваем ячейкам свое уникальное множество */
void Maze::assignUniqueSet() {
for (int i = 0; i < cols_; i++) {
/* Проверяем на пустую ячейку */
if (sideLine_[i] == kEmpty) {
/* Присваиваем ячейки уникальное множество */
sideLine_[i] = counter_;
counter_++;
}
}
}
Что такое counter_?
counter_ - это счетчик генерации уникальных множеств.
Шаг 3
Создайте правые границы, двигаясь слева направо:
- Случайно решите добавлять границу или нет:
1. Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
2. Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
Что такое номер?
Под номером я понимаю расположение ячейки в лабиринте. Не стоит путать это с множеством
-
Создайте правые границы, двигаясь слева направо:
-
Случайно решите добавлять границу или нет
-
Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
-
Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
-
-
Реализация шага 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. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
В ячейке под номером 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
Реализация шага 5.1
void Maze::preparatingNewLine(int row) {
for (int i = 0; i < cols_; i++) {
if (h_walls_(row, i) == true) {
/* Присваиваем ячейки пустое множество */
sideLine_[i] = kEmpty;
}
}
}
Продолжаем алгоритм до последней строки:
Шаг 2. Присваиваем пустым ячейкам уникальное множество
Шаг 3. Создание правых границ
Шаги 4 и 5. Создание нижней границы и копирование строки
Генерируем новую строку:
Генерация последней строки лабиринта
Шаг 2. Присваиваем пустым ячейкам уникальное множество
Шаг 3. Создание правых границ
Если мы решаем не добавлять правую границу в ячейке под номером 2, то к какому уникальному множеству будут принадлежать ячейка под номером 2 и 3?
1 или 7 (все ячейки принадлежащие к множеству 1 изменить на 7)
Пропускаем шаг 4, так-как это наша последняя строка
Шаг 5.2
Если вы хотите закончить лабиринт, то:
Добавьте нижнюю границу к каждой ячейке:
Двигаясь слева направо:
1. Если текущая ячейка и ячейка справа члены разных множеств, то:
1.1 Удалите правую границу
1.2 Объедините множества текущей ячейки и ячейки справа
1.3 Выведите завершающую строку
Реализация шага 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.
Благодарю за внимание! Надеюсь, я поделился чем-то новым и интересным для вас.
Если вам понравилась статья – то, пожалуйста, напишите об этом в комментарии. Буду очень рад любой критике.
Автор:
vladjong