Алгоритм Эллера - это алгоритм генерации идеального лабиринта. Лабиринт считается идеальным, если у него нет замкнутых и зацикленных участков, и от любой точки до любой другой точки существует ровно один путь.
Всем привет! Меня зовут Нурислам (aka tonitaga), я участник School21 и сегодня я бы вам хотел рассказать о Генерации Лабиринтов.
Правила алгоритма
Во-первых, хочется сказать, что алгоритм Эллера строится на основе псевдослучайных чисел. Именно поэтому каждый лабиринт является уникальным.
Случайное число всегда будет отвечать на вопрос: "Будем ставить стенку?"
Далее будут представлены правила алгоритма, перефразированные так, как я их понимаю:
Посмотреть
Создадим пустую строку, размер строки равен
лабиринта
Каждую ячейку пустой строки заполняем своим множеством
Под множеством, в данном случае, подразумеваются обычные числа.-
Постепенно двигаясь слева направо по строке, созданной в 1 пункте, будем решать ставить стенку справа или нет:
Стенку решили ставить, просто ставим и идем дальше.
Стенку решили не ставить, но если текущая ячейка и ячейка справа принадлежат одному множеству, то между ними всегда нужно ставить стенку, чтобы предотвратить зацикливание участков.
Стенку решили не ставить и условие в пункте 3.2 не выполнилось.
В данном случае нужно объединить множество к которому относится ячейка справа с множеством текущей ячейки. (В самом низу статьи есть оглавление по поводу как правильно объединять множества)
-
Постепенно двигаясь слева направо по строке, модернизированной в пункте 3, будем решать ставить стенку снизу или нет:
Стенку решили не ставить, просто не ставим и идем дальше
Стенку решили ставить, стенку будем ставить, если множество, которому принадлежит текущая ячейка имеет более одной ячейки без нижней границы.
-
После 3 и 4 пункта, строка считается завершенной, далее принимаем решение продолжать генерировать строки или следующая строка последняя:
-
Если решили сгенерировать ещë одну строку, то нужно скопировать текущую строку, удалить из нее все правые стенки, и там где были нижние стенки ячейкам присвоить пустые множества, удалить все нижние границы.
Всем ячейкам имеющим пустые множества, присвоить новые (ранее не встречавшиеся) множества
Повторяйте пункты 3 и 4 для каждой новой строки
-
Если решили что, текущая строка последняя, то каждой ячейке присвойте нижнюю стенку и:
Двигаясь слева направо, если множество текущей клетки и клетки справа не совпадает уберите между ними стенку (для того чтобы убрать замкнутые участки).
Объедините множества текущей ячейки и ячейки справа.
-
Пошаговая генерация лабиринта 4 x 4
Посмотреть
Для генерации лабиринта 4 х 4 сгенерируем случайные числа
Далее идет этап проставления правых стенок, посмотрим на первые три случайные числа, увидим что первое случайное число это ноль, значит по пункту 3.3, нужно все ячейки принадлежащие множеству 2 объединить с множеством 1.
Второе случайное число это 1, значит между ячейками с множествами 1 и 3 по пункту 3.1 ставим стенку
Третье случайное число 0, поэтому также по пункту 3.3 объединяем множества
Этап с вертикальными стенками завершен, дальше идет этап проставления горизонтальных стенок
Смотрим на следующие 4 случайных числа: 0 1 1 0
Первое случайное число в этом списке 0, поэтому по пункту 4.1 горизонтальную стенку ставить не будем.
Второе случайное число в этом списке 1, видим что множеству "1" принадлежит две ячейки, и свободных ячеек без нижней границы также две, условие по пункту 4.2 выполняется, поэтому нижнюю стенку можем поставить.
Третье случайное число в этом списке 1, видим что множеству "3" принадлежит две ячейки, и свободных ячеек без нижней границы также две, условие по пункту 4.2 выполняется, поэтому нижнюю стенку можем поставить.
Четвертое число в этом списке 0, поэтому по пункту 4.1 стенку не ставим и идем дальше.
Этап с проставлением горизонтальных стенок завершен, продолжаем по пункту 5.1 генерировать следующую строку:
Далее удаляем все правые границы и там, где были нижние границы, ячейкам присваиваем пустые множества (пусть будет, например, ноль), далее удаляем все нижние границы
Далее каждой ячейке с пустым множеством присваиваем новое уникальное множество, ранее не встречавшееся. Множества будут проставляться просто используя обычную переменную-счетчик, и мы постоянно будем ее инкрементировать, так как четверка у нас уже была то следующее число это 5.
Далее для этой строки повторяем пункты 3 и 4, используя псевдослучайные числа , представленные выше
Продолжаем генерировать новую строку по пункту 5.1
Проставляем по пунктам 3 и 4 стенки:
С этого момента поподробнее, тут будет задет пункт, который выше не попадался.
Случайные числа для проставления горизонтальных стенок третьей строки:
1 1 0 1
Для первой ячейки ставим нижнюю стенку, так как случайное число 1 и в множестве "1" больше одной свободной ячейки по пункту 4.2.
Заметим, что следующее число также 1, но в множестве "1" теперь всего одна свободная ячейка, стенку не ставим. Остальные случае встречались ранее.
Так как это не последняя строка, то продолжаем.
Проставляем также как и раньше, по пункту 3 и 4 вертикальные и горизонтальные стенки.
Случайные числа для вертикальных стен: 0 1 1
Случайные числа для горизонтальных стен: 0 0 0 0
Так как это строка последняя, в данном случае, то по пункту 5.2, проставим нижние границы для каждой ячейки и по 5.2.1 и 5.2.2 удалим стенки и объединим множества соответственно.
Важно
Под понятием объединить множества, имеется в виду не просто приравнять значения текущей ячейки и ячейки справа, а изменить множество, которому принадлежит ячейка справа полностью!
Посмотреть
Допустим нужно объединить множества самой левой ячейки и ячейки правее от нее.
Рисунок выше иллюстрирует неправильное объединение множеств
А вот так объединять уже правильно!
Полезные ссылки
Хочу поделиться своим github'ом, буду признателен если вы оформите подписку:
GitHubСтатья, написанная мной, по генерации пещер:
Генерация пещерСтатья, написанная мной, по волновому алгоритму:
Волновой алгоритм
Статья была написала из-за того, что другие источники (по крайней мере, которые я видел) упускают важные моменты теории, а именно момента по правильному объединению множеств, и не имеют корректного пошагового примера с использованием определённых псевдослучайных чисел.
Комментарии (17)
sinefag
09.07.2023 22:10+1https://habr.com/ru/articles/667576/
Простите мне мое занудство, но Хабр превращается в место для "еще одной курсовой/ задачки на курсе". Почему-то каждый студент считает свои труды уникальными. При этом я положительно отношусь к труду автора. Но где новизна? Где сравнение, анализ вариантов, сложности? Просто "смотрите, я написал программу, и она даже работает". Прекратите писать стать-записки о программке для студента на 2 дня.
tonitaga Автор
09.07.2023 22:10+4Мне пожаловались о том, что как раз таки статья которую вы прикрепили, не раскрывает полностью суть данного алгоритма, и лабиринт получается не идеальным.
tonitaga Автор
09.07.2023 22:10+1Плюс в статье, которые вы скинули, нет толкового разбора пошагово на определённых псевдослучайных числах, и поэтому понимание реализации алгоритма на бумаге ухудшается.
Также в той статье не написано как правильно объединять множества, потому что многие считают, что сама по себе ячейка в строке является множеством, но нет, она лишь принадлежит определённому множеству
aamonster
09.07.2023 22:10Напрашивается оптимизация: когда сливаете два множества – надо перекрашивать меньшее в цвет большего (не смотрел код, может, вы так и сделали?)
При случайном выборе ставить/не ставить стенку – какая нужна вероятность установки стены? 0.5? А как повлияет на устройство лабиринта изменение этого параметра?
Структура лабиринта везде однородна или верхний и левый края имеют статистические отличия? Если имеют – можно ли от этого избавиться (например, сделав вероятность стенки зависящей от координат)?
tonitaga Автор
09.07.2023 22:101) Оптимизацию по поводу сливания в более выгодную сторону я не делал у себя в коде, так как это не влияет, в любом случае надо перебирать всю строку, и присваивание копированием примитивных типов работает за константное время
2) Вероятности ставить стену и не ставить стену равны, если например сделать вероятность ставить стенки равной 1, то структура лабиринта будет примерно такой:
Каждая строка, кроме последней, будет иметь всё вертикальные стенки и ни одной горизонтальной, а последняя строка будет иметь всё горизонтальные стенки и ни одной вертикальной
Если же наоборот, вероятность ставить стену 0, то ситуация поворачивается в обратную сторону, первая строка не будет иметь ни вертикальных стенок ни горизонтальных, остальные строки будут иметь все вертикальные стенки
3) Не понял сути вопроса про однородность лабиринта.
aamonster
09.07.2023 22:103 – вы отчасти ответили (при вероятности, близкой к 0 или 1 – первая или последняя стена соответственно будет отличаться от остальных, если не строго 0/1 – соседние тоже, но уже меньше), а вот что будет при 0.5? Будет полоса, в которой больше вертикальных/горизонтальных линий или всё выровняется? А если будет – то можно ли от неё избавиться, сделав вероятность функцией от номера строки?
Ну и по столбцу тоже может быть какая-то неоднородность.
В общем, поведение алгоритма достаточно неочевидно (за исключением просто доказываемого факта корректного построения лабиринта), есть резон его исследовать (или найти готовое исследование, наверняка автор алгоритма этим занимался).
masyaman
09.07.2023 22:10Это точно хороший алгоритм? Похоже, что среди множества возможных лабиринтов генерация одних лабиринтов более вероятна, чем других.
Например я для поля 2х2 есть всего 4 варианта лабиринта, но вероятность стенки между верхними квадратами больше, чем остальные варианты.
Например, можно обнаружить неравномерность даже на анимации вначале статьи. Количество стенок в верхнем ряду больше, чем в нижнем или в боковых столбцах. Исходя из симметрии, я бы ожидал одинакового распределения. Есть вероятность, что можно проследить и другие паттерны, например неравномерность между вертикальными или горизонтальными стенками.
tonitaga Автор
09.07.2023 22:10В этом и суть псевдослучайных чисел, они не случайные, эти числа получаются путем математических алгоритмов, поэтому и такой результат
masyaman
09.07.2023 22:10Математические алгоритмы гегерации псевдослучайных чисел могут давать хорошее распределение. Дело в том, как алгоритм их использует, он изначально не рассчитан генерировать варианты с равной вероятностью.
Просчитайте вероятности для 2х2. Если я правильно понял, то алгоритм ставит стенку между двумя верхними квадратами с вероятностью 50% при первом вызове рандома. И на этом всё, псевдослучайных числа дальше не имеют значения.
GaricT
09.07.2023 22:10В одном из разборов этого алгоритма отмечалось, что генерация самой нижней строки "характеризуется" длинными коридорами. Даже предлагались варианты, как минимизировать их. Лично меня, эта особенность дико раздражает.
Пример длинных коридоров в нижней строке.
ZEvS_Poisk
Примерно 20 лет назад я тоже придумывал алгоритм генерации лабиринта для самопальной игры.
Механизм был следующий: сначала в пустом пространстве рисуем псевдослучайный путь. Главное его длина. После чего заполняем псевдослучайными стенками все, кроме этого пути.
Путь и есть верный способ прохода лабиринта, но часто обнаруживались и альтернативные маршруты. Конечно их можно обнаруживать каким либо алгоритмом и блокировать установкой стены.
Zara6502
Ваш вариант легко позволяет избавиться от недостатка с "вторыми путями", достаточно при генерации стен не генерировать разрывы вовсе, или не генерировать разрывы на основном пути.