![Лабиринты сгенерированные Алгоритмом Эллера Лабиринты сгенерированные Алгоритмом Эллера](https://habrastorage.org/getpro/habr/upload_files/826/d3f/d47/826d3fd472b901f3c70fde7aefd1ff69.gif)
Алгоритм Эллера - это алгоритм генерации идеального лабиринта. Лабиринт считается идеальным, если у него нет замкнутых и зацикленных участков, и от любой точки до любой другой точки существует ровно один путь.
Всем привет! Меня зовут Нурислам (aka tonitaga), я участник School21 и сегодня я бы вам хотел рассказать о Генерации Лабиринтов.
Правила алгоритма
Во-первых, хочется сказать, что алгоритм Эллера строится на основе псевдослучайных чисел. Именно поэтому каждый лабиринт является уникальным.
Случайное число всегда будет отвечать на вопрос: "Будем ставить стенку?"
Далее будут представлены правила алгоритма, перефразированные так, как я их понимаю:
Посмотреть
Создадим пустую строку, размер строки равен
лабиринта
Каждую ячейку пустой строки заполняем своим множеством
Под множеством, в данном случае, подразумеваются обычные числа.-
Постепенно двигаясь слева направо по строке, созданной в 1 пункте, будем решать ставить стенку справа или нет:
Стенку решили ставить, просто ставим и идем дальше.
Стенку решили не ставить, но если текущая ячейка и ячейка справа принадлежат одному множеству, то между ними всегда нужно ставить стенку, чтобы предотвратить зацикливание участков.
Стенку решили не ставить и условие в пункте 3.2 не выполнилось.
В данном случае нужно объединить множество к которому относится ячейка справа с множеством текущей ячейки. (В самом низу статьи есть оглавление по поводу как правильно объединять множества)
-
Постепенно двигаясь слева направо по строке, модернизированной в пункте 3, будем решать ставить стенку снизу или нет:
Стенку решили не ставить, просто не ставим и идем дальше
Стенку решили ставить, стенку будем ставить, если множество, которому принадлежит текущая ячейка имеет более одной ячейки без нижней границы.
-
После 3 и 4 пункта, строка считается завершенной, далее принимаем решение продолжать генерировать строки или следующая строка последняя:
-
Если решили сгенерировать ещë одну строку, то нужно скопировать текущую строку, удалить из нее все правые стенки, и там где были нижние стенки ячейкам присвоить пустые множества, удалить все нижние границы.
Всем ячейкам имеющим пустые множества, присвоить новые (ранее не встречавшиеся) множества
Повторяйте пункты 3 и 4 для каждой новой строки
-
Если решили что, текущая строка последняя, то каждой ячейке присвойте нижнюю стенку и:
Двигаясь слева направо, если множество текущей клетки и клетки справа не совпадает уберите между ними стенку (для того чтобы убрать замкнутые участки).
Объедините множества текущей ячейки и ячейки справа.
-
Пошаговая генерация лабиринта 4 x 4
Посмотреть
Для генерации лабиринта 4 х 4 сгенерируем случайные числа
![Случайные числа для нашего случая Случайные числа для нашего случая](https://habrastorage.org/getpro/habr/upload_files/18f/d5d/5e5/18fd5d5e5f9b6b5a30cbad27cc0cb6de.png)
![Пустая строка (Пункт 1) Пустая строка (Пункт 1)](https://habrastorage.org/getpro/habr/upload_files/40b/a7e/a20/40ba7ea20143fee3163a48d996872052.png)
![Выдали каждой ячейке уникальное множество Выдали каждой ячейке уникальное множество](https://habrastorage.org/getpro/habr/upload_files/65f/eb6/56c/65feb656cbd32258b01e561845d2a082.png)
Далее идет этап проставления правых стенок, посмотрим на первые три случайные числа, увидим что первое случайное число это ноль, значит по пункту 3.3, нужно все ячейки принадлежащие множеству 2 объединить с множеством 1.
![Использование первого случайного числа Использование первого случайного числа](https://habrastorage.org/getpro/habr/upload_files/a71/872/67c/a7187267c7acfc6654b26097f0dc53a4.png)
Второе случайное число это 1, значит между ячейками с множествами 1 и 3 по пункту 3.1 ставим стенку
![Использование второго случайного числа Использование второго случайного числа](https://habrastorage.org/getpro/habr/upload_files/a78/52e/0f0/a7852e0f0ff5d46f9173b5a6d627b701.png)
Третье случайное число 0, поэтому также по пункту 3.3 объединяем множества
![Использование третьего случайного числа Использование третьего случайного числа](https://habrastorage.org/getpro/habr/upload_files/584/2f9/826/5842f98265cf40c3db6adc69346d5358.png)
Этап с вертикальными стенками завершен, дальше идет этап проставления горизонтальных стенок
Смотрим на следующие 4 случайных числа: 0 1 1 0
Первое случайное число в этом списке 0, поэтому по пункту 4.1 горизонтальную стенку ставить не будем.
Второе случайное число в этом списке 1, видим что множеству "1" принадлежит две ячейки, и свободных ячеек без нижней границы также две, условие по пункту 4.2 выполняется, поэтому нижнюю стенку можем поставить.
![Использование пятого случайного числа Использование пятого случайного числа](https://habrastorage.org/getpro/habr/upload_files/0f7/82b/200/0f782b2009b4fc242f19f1be0fc03774.png)
Третье случайное число в этом списке 1, видим что множеству "3" принадлежит две ячейки, и свободных ячеек без нижней границы также две, условие по пункту 4.2 выполняется, поэтому нижнюю стенку можем поставить.
![Использование шестого случайного числа Использование шестого случайного числа](https://habrastorage.org/getpro/habr/upload_files/d58/e16/7f5/d58e167f54e2760d695a44b380cddd87.png)
Четвертое число в этом списке 0, поэтому по пункту 4.1 стенку не ставим и идем дальше.
Этап с проставлением горизонтальных стенок завершен, продолжаем по пункту 5.1 генерировать следующую строку:
![Скопировали предыдущую строку Скопировали предыдущую строку](https://habrastorage.org/getpro/habr/upload_files/c73/56a/c74/c7356ac7411d55d0c456bffe3a878a01.png)
Далее удаляем все правые границы и там, где были нижние границы, ячейкам присваиваем пустые множества (пусть будет, например, ноль), далее удаляем все нижние границы
![Подготовка новой строки Подготовка новой строки](https://habrastorage.org/getpro/habr/upload_files/0db/e52/44d/0dbe5244df5bec39eef3a9092ddb6556.png)
Далее каждой ячейке с пустым множеством присваиваем новое уникальное множество, ранее не встречавшееся. Множества будут проставляться просто используя обычную переменную-счетчик, и мы постоянно будем ее инкрементировать, так как четверка у нас уже была то следующее число это 5.
![Присвоение пустым множествам нового уникального множества Присвоение пустым множествам нового уникального множества](https://habrastorage.org/getpro/habr/upload_files/d0e/6db/a63/d0e6dba6360fcb5d7aaec32afc48c4cd.png)
Далее для этой строки повторяем пункты 3 и 4, используя псевдослучайные числа , представленные выше
![Проставили вертикальные стенки для второй строки Проставили вертикальные стенки для второй строки](https://habrastorage.org/getpro/habr/upload_files/686/ab1/e28/686ab1e288bb21704ca4e56c7f213d17.png)
![Проставили горизонтальные стенки для второй строки Проставили горизонтальные стенки для второй строки](https://habrastorage.org/getpro/habr/upload_files/11c/7ee/969/11c7ee969411814c3928e761d8c0ec7d.png)
Продолжаем генерировать новую строку по пункту 5.1
![Готовая для работы третья строка Готовая для работы третья строка](https://habrastorage.org/getpro/habr/upload_files/3e3/048/9ca/3e30489ca3e765194eb6b6b2576c155e.png)
Проставляем по пунктам 3 и 4 стенки:
![Проставленные вертикальные стенки для третьей строки Проставленные вертикальные стенки для третьей строки](https://habrastorage.org/getpro/habr/upload_files/3f0/445/c39/3f0445c39921e0fe41f1ca5597fc9830.png)
С этого момента поподробнее, тут будет задет пункт, который выше не попадался.
Случайные числа для проставления горизонтальных стенок третьей строки:
1 1 0 1
Для первой ячейки ставим нижнюю стенку, так как случайное число 1 и в множестве "1" больше одной свободной ячейки по пункту 4.2.
Заметим, что следующее число также 1, но в множестве "1" теперь всего одна свободная ячейка, стенку не ставим. Остальные случае встречались ранее.
![Проставленные горизонтальные стенки для третьей строки Проставленные горизонтальные стенки для третьей строки](https://habrastorage.org/getpro/habr/upload_files/7b2/290/2b0/7b22902b0bf6050d740312c641f044c4.png)
Так как это не последняя строка, то продолжаем.
![Готовая для работы четвертая строка Готовая для работы четвертая строка](https://habrastorage.org/getpro/habr/upload_files/55c/a15/a81/55ca15a81211cebacbad5024b4260471.png)
Проставляем также как и раньше, по пункту 3 и 4 вертикальные и горизонтальные стенки.
Случайные числа для вертикальных стен: 0 1 1
Случайные числа для горизонтальных стен: 0 0 0 0
![Проставленные вертикальные и горизонтальные стенки для четвертой строки Проставленные вертикальные и горизонтальные стенки для четвертой строки](https://habrastorage.org/getpro/habr/upload_files/fa5/cd6/6e6/fa5cd66e62a35a00a00f2c720c5472ec.png)
Так как это строка последняя, в данном случае, то по пункту 5.2, проставим нижние границы для каждой ячейки и по 5.2.1 и 5.2.2 удалим стенки и объединим множества соответственно.
![Готовый лабиринт 4 х 4 Готовый лабиринт 4 х 4](https://habrastorage.org/getpro/habr/upload_files/25d/ab0/ce1/25dab0ce1809dd41f838e99b91509381.png)
Важно
Под понятием объединить множества, имеется в виду не просто приравнять значения текущей ячейки и ячейки справа, а изменить множество, которому принадлежит ячейка справа полностью!
Посмотреть
![Пример Пример](https://habrastorage.org/getpro/habr/upload_files/600/7a0/496/6007a04962cfce50bfdbc498b38dab13.png)
Допустим нужно объединить множества самой левой ячейки и ячейки правее от нее.
![Пример неправильного объединения множеств Пример неправильного объединения множеств](https://habrastorage.org/getpro/habr/upload_files/4b1/b74/ef5/4b1b74ef54eef2517e97b36bede9fb40.png)
Рисунок выше иллюстрирует неправильное объединение множеств
![Пример правильного объединения множеств Пример правильного объединения множеств](https://habrastorage.org/getpro/habr/upload_files/6ae/601/2b2/6ae6012b21955237cf242b8a1d7b0af9.png)
А вот так объединять уже правильно!
Полезные ссылки
Хочу поделиться своим 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
Ваш вариант легко позволяет избавиться от недостатка с "вторыми путями", достаточно при генерации стен не генерировать разрывы вовсе, или не генерировать разрывы на основном пути.