![Лабиринты сгенерированные Алгоритмом Эллера Лабиринты сгенерированные Алгоритмом Эллера](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Статья, написанная мной, по генерации пещер:
Генерация пещерСтатья, написанная мной, по волновому алгоритму:
Волновой алгоритм