Введение

Автоматизированные методы создания лабиринтов

Алгоритмы генерации лабиринтов — это автоматизированные методы создания лабиринтов.

Рандомизированный поиск на глубине

Этот алгоритм, также известный как алгоритм "рекурсивного обхода с возвратом", является рандомизированной версией алгоритма поиска в глубину. Часто реализуемый с использованием стека, этот подход – один из самых простых способов генерации лабиринта на компьютере. Представьте пространство лабиринта как большую сетку ячеек (как большая шахматная доска), где каждая ячейка изначально имеет четыре стены. Начиная со случайной ячейки, компьютер выбирает случайную соседнюю ячейку, которая еще не была посещена. Затем компьютер удаляет стену между этими двумя ячейками, помечает новую ячейку как посещенную и добавляет ее в стек для последующего возврата. Компьютер продолжает этот процесс, пока ячейка не окажется в тупике – то есть, не будет иметь непосещенных соседей. Достигнув тупика, компьютер возвращается по пути до ячейки, имеющей непосещенный сосед, и продолжает генерацию пути, посещая эту новую ячейку (создавая новое ответвление). Этот процесс продолжается до тех пор, пока не будут посещены все ячейки, в результате чего компьютер вернется к исходной ячейке. Мы можем быть уверены, что каждая ячейка будет посещена. Как указано выше, этот алгоритм предполагает глубокую рекурсию, которая может привести к переполнению стека на некоторых компьютерных архитектурах. Алгоритм можно преобразовать в цикл, сохраняя информацию о возврате непосредственно в лабиринте. Это также предоставляет быстрый способ отображения решения, начиная с любой заданной точки и возвращаясь к началу. Лабиринты, сгенерированные с помощью поиска в глубину, имеют низкий коэффициент ветвления и содержат множество длинных коридоров, поскольку алгоритм исследует каждую ветвь настолько далеко, насколько это возможно, прежде чем вернуться назад.

Измененная версия

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

Упрощенная версия

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

Алгоритм Уилсона

Все вышеперечисленные алгоритмы имеют различные виды предвзятости: поиск в глубину склонен к длинным коридорам, а алгоритмы Крускала/Прима – к множеству коротких тупиков. Алгоритм Уилсона, напротив, генерирует несмещенную выборку из равномерного распределения по всем возможным лабиринтам, используя случайные блуждания с удалением петель. Мы начинаем алгоритм с инициализации лабиринта одной произвольно выбранной ячейкой. Затем мы начинаем с новой произвольно выбранной ячейки и выполняем случайное блуждание, пока не достигнем ячейки, уже находящейся в лабиринте. Однако, если в любой момент случайное блуждание достигает собственного пути, образуя петлю, мы удаляем эту петлю из пути, прежде чем продолжить. Когда путь достигает лабиринта, мы добавляем его к лабиринту. Затем мы выполняем еще одно случайное блуждание с удалением петель, начиная с другой произвольной ячейки, повторяя этот процесс, пока все ячейки не будут заполнены. Эта процедура остается несмещенной независимо от метода, используемого для произвольного выбора начальных ячеек. Таким образом, для простоты мы всегда можем выбирать первую незаполненную ячейку, например, слева направо и сверху вниз.

Метод рекурсивного деления

+ Иллюстрация рекурсивного деления исходное разделение камеры двумя стенами отверстия в стенах продолжают подразделение завершено

Лабиринты можно создавать с помощью рекурсивного деления, алгоритма, который работает следующим образом: Начните с пространства лабиринта, не имеющего стен. Назовите это камерой. Разделите камеру случайной стеной (или несколькими стенами), при этом в каждой стене должно быть случайным образом расположенное отверстие. Затем рекурсивно повторите этот процесс для подкамер, пока все камеры не достигнут минимального размера. Этот метод приводит к созданию лабиринтов с длинными прямыми стенами, пересекающими пространство, что облегчает определение областей, которых следует избегать. Например, в прямоугольном лабиринте постройте в случайных точках две взаимно перпендикулярные стены. Эти две стены разделят большую камеру на четыре меньшие камеры, разделенные четырьмя стенами. Случайным образом выберите три из этих четырех стен и сделайте в каждой из них отверстие шириной в одну ячейку в случайном месте. Продолжайте этот процесс рекурсивно, пока каждая камера не будет иметь ширину в одну ячейку в одном из двух направлений.

Алгоритм фрактальной тесселяции

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

Простые алгоритмы

Существуют и другие алгоритмы, которым требуется лишь достаточно памяти для хранения одной строки 2D-лабиринта или одной плоскости 3D-лабиринта. Алгоритм Эллера предотвращает образование циклов, запоминая, какие ячейки в текущей строке соединены через ячейки в предыдущих строках, и никогда не удаляет стены между двумя уже соединенными ячейками. Алгоритм Sidewinder начинается с открытого прохода вдоль всей верхней строки, а последующие строки состоят из более коротких горизонтальных проходов с одним соединением с проходом выше. Алгоритм Sidewinder тривиально решается снизу вверх, поскольку в нем нет тупиков, ведущих вверх. При заданной начальной ширине оба алгоритма создают идеальные лабиринты неограниченной высоты. Большинство алгоритмов генерации лабиринтов требуют поддержания связей между ячейками внутри лабиринта, чтобы гарантировать его решаемость. Однако валидные, просто связанные лабиринты можно сгенерировать, рассматривая каждую ячейку независимо. Бинарный лабиринт в виде дерева – это стандартный ортогональный лабиринт, в котором каждая ячейка всегда имеет проход, ведущий вверх или влево, но никогда и туда, и туда одновременно. Чтобы создать бинарный лабиринт в виде дерева, для каждой ячейки подбрасывается монета, чтобы определить, добавлять проход вверх или влево. Всегда выбирайте одно и то же направление для ячеек на границе, и результатом будет валидный, просто связанный лабиринт, который выглядит как двоичное дерево, с верхним левым углом в качестве корня. Как и в случае с Sidewinder, в бинарном лабиринте в виде дерева нет тупиков в направлении предпочтения. Связанный способ подбрасывания монеты для каждой ячейки – это создание изображения, используя случайную смесь символов прямого и обратного слэша. Это не генерирует валидный, просто связанный лабиринт, а скорее набор замкнутых циклов и однонаправленных проходов. В руководстве к Commodore 64 представлена программа на BASIC, использующая этот алгоритм, с применением диагональных графических символов PETSCII вместо этого для более плавного графического отображения.

Алгоритмы клеточных автоматов

Некоторые типы клеточных автоматов могут использоваться для генерации лабиринтов. Два известных клеточных автомата, Maze и Mazectric, имеют строки правил B3/S12345 и B3/S1234. В первом случае это означает, что клетки выживают из одного поколения в другое, если у них есть как минимум один и не более пяти соседей. Во втором случае это означает, что клетки выживают, если у них от одного до четырех соседей. Если у клетки ровно три соседа, она рождается. Это похоже на игру «Жизнь» Конвея в том, что паттерны, не имеющие живой клетки, соседствующей с 1, 4 или 5 другими живыми клетками в любом поколении, будут вести себя идентично. Однако, для больших паттернов, поведение автомата сильно отличается от «Жизни». При случайном начальном состоянии эти клеточные автоматы, генерирующие лабиринты, эволюционируют в сложные лабиринты с чётко очерченными стенами, образующими коридоры. Mazectric, использующий правило B3/S1234, склонен генерировать более длинные и прямые коридоры по сравнению с Maze, использующим правило B3/S12345. Поскольку правила этих клеточных автоматов детерминированы, каждый сгенерированный лабиринт однозначно определяется его случайным начальным паттерном. Это существенный недостаток, так как лабиринты, как правило, относительно предсказуемы. Как и некоторые из методов, основанных на теории графов, описанных выше, эти клеточные автоматы обычно генерируют лабиринты из одного начального паттерна; следовательно, обычно будет относительно легко найти путь к начальной ячейке, но сложнее найти путь куда-либо ещё.