Генерация Лабиринта | Алгоритм Эллера

Лабиринты сгенерированные Алгоритмом Эллера

Алгоритм Эллера - это алгоритм генерации идеального лабиринта. Лабиринт считается идеальным, если у него нет замкнутых и зацикленных участков, и от любой точки до любой другой точки существует ровно один путь.

Всем привет! Меня зовут Нурислам (aka tonitaga), я участник School21 и сегодня я бы вам хотел рассказать о Генерации Лабиринтов.

Статья была написала из-за того, что другие источники (по крайней мере, которые я видел) упускают важные моменты теории, а именно момента по правильному объединению множеств, и не имеют корректного пошагового примера с использованием определённых псевдослучайных чисел.

Правила алгоритма

• Во-первых, хочется сказать, что алгоритм Эллера строится на основе псевдослучайных чисел. Именно поэтому каждый лабиринт является уникальным.

• Случайное число всегда будет отвечать на вопрос: "Будем ставить стенку?"

Далее будут представлены правила алгоритма, перефразированные так, как я их понимаю:

Посмотреть

1. Создадим пустую строку, размер строки равен лабиринта

2. Каждую ячейку пустой строки заполняем своим множеством
   
   Под множеством, в данном случае, подразумеваются обычные числа.

3. Постепенно двигаясь слева направо по строке, созданной в 1 пункте, будем решать ставить стенку справа или нет:

   1. Стенку решили ставить, просто ставим и идем дальше.

   2. Стенку решили не ставить, но если текущая ячейка и ячейка справа принадлежат одному множеству, то между ними всегда нужно ставить стенку, чтобы предотвратить зацикливание участков.

   3. Стенку решили не ставить и условие в пункте 3.2 не выполнилось.
      В данном случае нужно объединить множество к которому относится ячейка справа с множеством текущей ячейки. (В самом низу статьи есть оглавление по поводу как правильно объединять множества)

4. Постепенно двигаясь слева направо по строке, модернизированной в пункте 3, будем решать ставить стенку снизу или нет:

   1. Стенку решили не ставить, просто не ставим и идем дальше

   2. Стенку решили ставить, стенку будем ставить, если множество, которому принадлежит текущая ячейка имеет более одной ячейки без нижней границы.

5. После 3 и 4 пункта, строка считается завершенной, далее принимаем решение продолжать генерировать строки или следующая строка последняя:

   1. Если решили сгенерировать ещë одну строку, то нужно скопировать текущую строку, удалить из нее все правые стенки, и там где были нижние стенки ячейкам присвоить пустые множества, удалить все нижние границы.

      1. Всем ячейкам имеющим пустые множества, присвоить новые (ранее не встречавшиеся) множества

      2. Повторяйте пункты 3 и 4 для каждой новой строки

   2. Если решили что, текущая строка последняя, то каждой ячейке присвойте нижнюю стенку и:

      1. Двигаясь слева направо, если множество текущей клетки и клетки справа не совпадает уберите между ними стенку (для того чтобы убрать замкнутые участки).

      2. Объедините множества текущей ячейки и ячейки справа.

Пошаговая генерация лабиринта 4 x 4

Посмотреть

• Для генерации лабиринта 4 х 4 сгенерируем случайные числа

Случайные числа для нашего случая

Пустая строка (Пункт 1)

Выдали каждой ячейке уникальное множество

Далее идет этап проставления правых стенок, посмотрим на первые три случайные числа, увидим что первое случайное число это ноль, значит по пункту 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 удалим стенки и объединим множества соответственно.

Готовый лабиринт 4 х 4

Важно

• Под понятием объединить множества, имеется в виду не просто приравнять значения текущей ячейки и ячейки справа, а изменить множество, которому принадлежит ячейка справа полностью!

Посмотреть

Пример

Допустим нужно объединить множества самой левой ячейки и ячейки правее от нее.

Пример неправильного объединения множеств

Рисунок выше иллюстрирует неправильное объединение множеств

Пример правильного объединения множеств

А вот так объединять уже правильно!

Полезные ссылки

• Хочу поделиться своим github'ом, буду признателен если вы оформите подписку:
  GitHub

• Статья, написанная мной, по генерации пещер:
  Генерация пещер

• Статья, написанная мной, по волновому алгоритму:
  Волновой алгоритм