Материал: АиСД. Проектная работа

Пример работы

Таким же случайным образом генерируется вторая строка

1.1.4 Алгоритм Recursive Backtracking

Алгоритм Recursive Backtracking — алгоритм генерации лабиринта поиском в глубину. Требует стека, объём которого может доходить до размеров лабиринта.

Алгоритм:

1.Изначально все поле содержит стены.

2.Выбираем любую ячейку.

3.Выбираем любую стену и делаем проход в соседнюю ячейку, но только если соседняя ячейка еще не посещена. Новая ячейка становится текущей ячейкой.

4.Если все соседние ячейки были посещены, возвращаемся к последней ячейке, которая имеет не вырезанные стенки, и повторяем с №3.

5.Алгоритм заканчивается, когда процесс полностью возвращается к начальной ячейке.

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

Recursive Backtracking нельзя реализовать с добавлением стен, потому что в этом случае он склонен создавать путь решения, который следует вдоль внешнего края, где вся внутренняя часть лабиринта соединена с границей единственным проходом.

11

Таблица 5

Пример работы

Случайно выбираем ячейку

В этой ячейке случайным образом выбираем стену и делаем проход в соседнюю ячейку, но только если соседняя ячейка еще не посещена. Новая ячейка становится текущей ячейкой.

Продолжаем…

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

Если все соседние ячейки были посещены, то нам следует вернуться к последней ячейке, которая имеет не вырезанные стенки, и повторить алгоритм для неё.

12

Пример работы

Вырезаем проход

1.1.5 Алгоритм рекурсивного деления Алгоритм рекурсивного деления — алгоритм, работающий со стенами.

Алгоритм:

1.Изначально все поле не содержит стены.

2.Разделяем поле стеной по горизонтали или вертикали.

3.Добавляем один проход через стену.

4.Повторяем шаги №2-3 с областями по обе стороны от стены. Продолжаем

рекурсивно, пока лабиринт не достигнет желаемого разрешения.

Причем: для наилучших результатов следует добавить отклонение в выборе горизонтали или вертикали на основе пропорций области, например, область, ширина которой вдвое больше высоты, должна более часто (или всегда) делиться вертикальными стенами.

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

Рекурсивное деление нельзя использовать для вырезания проходов, потому что это приводит к созданию очевидного решения, которое или следует вдоль внешнего края, или иначе напрямую пересекает внутреннюю часть.

13

Таблица 6

Пример работы

Начинаем с пустого поля. В нашем случае 5×5.

Разделяем поле стеной по горизонтали или вертикали.

Затем мы случайным образом добавляем пробел в стену, чтобы сохранить связность.

И это завершает первую итерацию.

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

Сначала обработаем поле справа. Разрежем это поле пополам горизонтально, а затем добавим проход.

Поле в верхнем правом углу является квадратом, поэтому мы можем произвольно выбирать между горизонтальным или вертикальным делением пополам.

Пойдем по вертикали.

Мы не можем делить их дальше, так как наша сетка составляет всего 5×5. Итак, рекурсия заканчивается, и мы перематываем обратно в стек.

Далее мы обрабатываем нижний правый край. Потом нижний левый.

И наконец верхний левый.

14

Пример работы

1.1.6 Алгоритм Эллера Алгоритм Эллера — особый алгоритм, потому что он не только довольно быстр,

но и не имеет очевидной смещенности или недостатков; кроме того, при его создании память используется наиболее эффективно. (Для него не требуется, чтобы в памяти находился весь лабиринт; он использует объём, пропорциональный размеру строки.)

Алгоритм:

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

получиться наборов, где — количество ячеек первой строки. Т. е. для 8-ми ячеек: [1 2 3 4 5 6 7 8].

2.Теперь случайным образом объединяем соседние ячейки в один набор (но только если они не находятся в одном наборе) или разделяем их. При

объединении соседних ячеек объединяем ячейки обоих наборов в один набор, указывая, что все ячейки в обоих наборах теперь связаны. По итогу может получиться следующее: [1 1 1|4 5|6 6 6].

3.Добавляем нижние границы. Убедимся, что каждый набор имеет хотя бы одну ячейку без нижней границы. Если это условие не будет выполнено, то мы создадим изолированные области. По итогу: [1 _1_1_|4 _5_|6 6 _6_].

4.Перемещаем на следующий ряд те ячейки наборов, которые не имели нижних

15