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

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 х 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 удалим стенки и объединим множества соответственно.

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

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

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