Алгоритм создания лабиринта

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

Методы, основанные на теории графов

Лабиринт можно создать, начиная с заранее определенного расположения ячеек (чаще всего прямоугольной сетки, но возможны и другие расположения) со стенами между ними. Это заранее определенное расположение можно рассматривать как связный граф , ребра которого представляют возможные участки стен, а узлы представляют ячейки. Тогда можно считать, что целью алгоритма генерации лабиринта является создание подграфа, в котором сложно найти маршрут между двумя конкретными узлами.

Если подграф не связан , то есть области графа, которые тратятся впустую, поскольку они не вносят вклад в пространство поиска. Если граф содержит петли, между выбранными узлами может быть несколько путей. Из-за этого к созданию лабиринта часто относятся как к созданию случайного связующего дерева . Циклы, которые могут сбить с толку наивных решателей лабиринтов, могут быть введены путем добавления случайных ребер к результату в ходе работы алгоритма.

Анимация показывает этапы создания лабиринта для график, не лежащий на прямоугольной сетке.Сначала компьютер создает случайный планарный граф Gпоказано синим цветом, и его двойная буква Fпоказано желтым цветом. Во-вторых, компьютер проходит F, используя выбранныйалгоритм, такой как поиск в глубину, окрашивающий путь в красный цвет.Во время обхода всякий раз, когда красный край пересекает синий край,синий край удален.Наконец, когда все вершины F посещены, F стирается.и два ребра из G, одно для входа и одно для выхода, удалены.

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

Анимация генератора с использованием поиска в глубину

Другая анимация генератора, использующего поиск в глубину.

Этот алгоритм, также известный как алгоритм «рекурсивного обратного отслеживания», представляет собой рандомизированную версию алгоритма поиска в глубину .

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

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

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

Рекурсивная реализация

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

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

Учитывая текущую ячейку в качестве параметра
Отметить текущую ячейку как посещенную
Пока текущая ячейка имеет непосещенные соседние ячейки
1. Выберите одного из непосещенных соседей
2. Удалить стену между текущей ячейкой и выбранной ячейкой
3. Рекурсивно вызвать процедуру для выбранной ячейки

который вызывается один раз для любой начальной ячейки области.

Итеративная реализация (со стеком)

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

Выберите начальную ячейку, отметьте ее как посещенную и поместите в стек.
Пока стек не пуст
1. Извлечь ячейку из стека и сделать ее текущей ячейкой
2. Если у текущей ячейки есть соседи, которые не были посещены
  1. Отправить текущую ячейку в стек
  2. Выберите одного из непосещенных соседей
  3. Удалить стену между текущей ячейкой и выбранной ячейкой
  4. Отметьте выбранную ячейку как посещенную и поместите ее в стек.

Итеративный рандомизированный алгоритм Краскала (с наборами)

Анимация создания лабиринта 30 на 20 с использованием алгоритма Краскала.

Этот алгоритм представляет собой рандомизированную версию алгоритма Краскала .

Создайте список всех стен и создайте набор для каждой ячейки, каждая из которых будет содержать только одну ячейку.
Для каждой стены в случайном порядке:
1. Если клетки, разделенные этой стенкой, принадлежат разным множествам:
  1. Удалите текущую стену.
  2. Объедините наборы ранее разделенных ячеек.

Существует несколько структур данных, которые можно использовать для моделирования наборов ячеек. Эффективная реализация, использующая структуру данных с непересекающимися наборами, может выполнять каждое объединение и операцию поиска над двумя наборами почти за постоянное амортизированное время (в частности, $O(\alpha (V))$ время; $\alpha (x)<5$ за любое возможное значение $x$ ), поэтому время работы этого алгоритма по существу пропорционально количеству стен, доступных в лабиринте.

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

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

Итеративный рандомизированный алгоритм Прима (без стека, без множеств)

Анимация создания лабиринта 30 на 20 с использованием алгоритма Прима.

Этот алгоритм представляет собой рандомизированную версию алгоритма Прима .

Начните с сетки, полной стен.
Выберите ячейку, отметьте ее как часть лабиринта. Добавьте стены ячейки в список стен.
Пока в списке есть стены:
1. Выберите случайную стену из списка. Если посещена только одна из ячеек, которые разделяет стенка, то:
  1. Сделайте стену проходом и отметьте непосещенную ячейку как часть лабиринта.
  2. Добавьте соседние стены ячейки в список стен.
2. Удалите стену из списка.

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

Модифицированная версия

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

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

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

Обычно относительно легко найти путь к начальной ячейке, но трудно найти путь куда-либо еще.

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

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

Все вышеперечисленные алгоритмы имеют смещения различного рода: поиск в глубину смещен в сторону длинных коридоров, тогда как алгоритмы Крускала/Прима смещены в сторону множества коротких тупиков. алгоритм Вильсона, ^[1] с другой стороны, генерирует несмещенную выборку из равномерного распределения по всем лабиринтам, используя случайные блуждания со стиранием цикла .

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

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

Алгоритм Олдоса-Бродера

Алгоритм Олдоса-Бродера также создает однородные остовные деревья. Однако это один из наименее эффективных алгоритмов лабиринта. ^[2]

Выберите случайную ячейку в качестве текущей и отметьте ее как посещенную.
Пока есть непосещенные ячейки:
1. Выберите случайного соседа.
2. Если выбранного соседа не посетили:
  1. Удалить стену между текущей ячейкой и выбранным соседом.
  2. Отметить выбранного соседа как посещенного.
3. Сделать выбранного соседа текущей ячейкой.

Рекурсивный метод деления

**Иллюстрация рекурсивного деления**
оригинальная камера	разделение двумя стенами	дыры в стенах	продолжайте деление...	завершенный
шаг 1	шаг 2	шаг 3	шаг 4	шаг 5

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

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

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

Это простой и быстрый способ создать лабиринт. ^[3]

На каждой итерации этот алгоритм создает лабиринт вдвое большего размера, копируя себя 3 раза. В конце каждой итерации открываются 3 пути между 4 меньшими лабиринтами.

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

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

Существуют и другие алгоритмы, которым требуется память только для хранения одной строки 2D-лабиринта или одной плоскости 3D-лабиринта. Алгоритм Эллера предотвращает образование петель, запоминая, какие ячейки в текущей строке соединены через ячейки в предыдущих строках, и никогда не удаляет стены между любыми двумя уже соединенными ячейками. ^[4] Алгоритм Sidewinder начинается с открытого прохода вдоль всего верхнего ряда, а последующие ряды состоят из более коротких горизонтальных проходов с одним соединением с проходом выше. Алгоритм Sidewinder тривиален для решения снизу вверх, поскольку у него нет тупиков вверх. ^[5] Учитывая начальную ширину, оба алгоритма создают идеальные лабиринты неограниченной высоты.

Большинство алгоритмов создания лабиринта требуют поддержания связей между ячейками внутри него, чтобы гарантировать разрешимость результата. Однако действительные односвязные лабиринты можно создать, сосредоточив внимание на каждой ячейке независимо. Лабиринт с бинарным деревом — это стандартный ортогональный лабиринт, в котором в каждой ячейке всегда есть проход, ведущий вверх или влево, но никогда и то, и другое. Чтобы создать лабиринт с бинарным деревом, для каждой ячейки подбросьте монету, чтобы решить, добавить ли проход вверх или влево. Всегда выбирайте одно и то же направление для ячеек на границе, и в результате получится действительный односвязный лабиринт, похожий на двоичное дерево , с корнем в левом верхнем углу. Как и в случае с Sidewinder, в лабиринте с бинарным деревом нет тупиков в направлениях смещения.

Связанная форма подбрасывания монеты для каждой ячейки — создание изображения с использованием случайного сочетания символов прямой и обратной косой черты. Это создает не действительный односвязный лабиринт, а скорее набор замкнутых петель и уникурсальных проходов. В руководстве для Commodore 64 представлена программа на языке BASIC, использующая этот алгоритм, используя вместо этого графические символы диагональных линий PETSCII для более гладкого графического вида.

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

Определенные типы клеточных автоматов можно использовать для создания лабиринтов. ^[6] Два хорошо известных таких клеточных автомата, Maze и Mazectric, имеют строки правил B3/S12345 и B3/S1234. ^[6] В первом случае это означает, что клетки выживают от одного поколения к другому, если у них есть хотя бы один и не более пяти соседей . В последнем случае это означает, что клетки выживают, если у них есть от одного до четырех соседей. Если у клетки ровно три соседа, она рождается. Это похоже на «Игру жизни» Конвея в том смысле, что модели, в которых нет живой клетки, соседствующей с 1, 4 или 5 другими живыми клетками в любом поколении, будут вести себя идентично ей. ^[6] Однако для больших шаблонов он ведет себя совсем не так, как Life. ^[6]

При случайном исходном шаблоне эти клеточные автоматы, генерирующие лабиринты, разовьются в сложные лабиринты с четко выраженными стенами, очерчивающими коридоры. Mazecetric, имеющий правило B3/S1234, имеет тенденцию создавать более длинные и прямые коридоры по сравнению с Maze с правилом B3/S12345. ^[6] Поскольку эти правила клеточного автомата являются детерминированными , каждый генерируемый лабиринт однозначно определяется его случайным начальным шаблоном. Это существенный недостаток, поскольку лабиринты обычно относительно предсказуемы.

Как и некоторые из описанных выше методов, основанных на теории графов, эти клеточные автоматы обычно генерируют лабиринты из одного начального шаблона; следовательно, обычно относительно легко найти путь к начальной ячейке, но труднее найти путь куда-либо еще.

См. также

Ссылки

^ Уилсон, Дэвид Брюс (22–24 мая 1996 г.). «Генерация случайных связующих деревьев быстрее, чем время покрытия». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . Симпозиум по теории вычислений. Филадельфия: ACM. стр. 296–303. CiteSeerX 10.1.1.47.8598 . дои : 10.1145/237814.237880 . ISBN 0-89791-785-5 .
^ Джеймис Бак (17 января 2011 г.). «Генерация лабиринта: алгоритм Олдоса-Бродера» .
^ Зе Оливейра (18 июня 2023 г.). «Стены лабиринта» .
^ Джеймис Бак (29 декабря 2010 г.). «Поколение лабиринта: алгоритм Эллера» .
^ Джеймис Бак (3 февраля 2011 г.). «Генерация лабиринта: алгоритм Sidewinder» .
^ Перейти обратно: ^а ^б ^с ^д ^и Натаниэль Джонстон; и др. (21 августа 2010 г.). «Лабиринт — LifeWiki» . ЖизньВики . Проверено 1 марта 2011 г.

Внешние ссылки

Think Labyrinth: алгоритмы лабиринта (подробнее об этих и других алгоритмах создания лабиринтов)
Джеймис Бак: Презентация HTML 5 с демонстрациями алгоритмов генерации лабиринта
Визуализация генерации лабиринта
Java-реализация алгоритма Прима
Реализации алгоритма создания лабиринта DFS на нескольких языках в Rosetta Code
Армин Райхерт: 34 алгоритма лабиринта на Java 8 с демо-приложением
Задача кодирования № 10.1: Генератор лабиринта с p5.js. Часть 1. Алгоритм создания лабиринта в JavaScript с помощью p5
Генератор лабиринтов от Чарльза Бонда, COMPUTE! Журнал, декабрь 1981 г.

[1] Уилсон, Дэвид Брюс (22–24 мая 1996 г.). «Генерация случайных связующих деревьев быстрее, чем время покрытия». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . Симпозиум по теории вычислений. Филадельфия: ACM. стр. 296–303. CiteSeerX 10.1.1.47.8598 . дои : 10.1145/237814.237880 . ISBN 0-89791-785-5 .

[2] Джеймис Бак (17 января 2011 г.). «Генерация лабиринта: алгоритм Олдоса-Бродера» .

[3] Зе Оливейра (18 июня 2023 г.). «Стены лабиринта» .

[4] Джеймис Бак (29 декабря 2010 г.). «Поколение лабиринта: алгоритм Эллера» .

[5] Джеймис Бак (3 февраля 2011 г.). «Генерация лабиринта: алгоритм Sidewinder» .

[ca-6] Перейти обратно: ^а ^б ^с ^д ^и Натаниэль Джонстон; и др. (21 августа 2010 г.). «Лабиринт — LifeWiki» . ЖизньВики . Проверено 1 марта 2011 г.

[1]

[2]

[3]

[4]

[5]

[6]