Генерация Лабиринта | Алгоритм Эллера
Случайные числа для нашего случая
Пустая строка (Пункт 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
