Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

Поколения Maze алгоритмы автоматизированы методы для создания лабиринтов .

Этот лабиринт, созданный модифицированной версией алгоритма Прима, показан ниже.

Методы, основанные на теории графов [ править ]

Анимация метода на основе теории графов (рандомизированный поиск в глубину)

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

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

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

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

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

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

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

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

Смещение горизонтального прохода

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

Рекурсивная реализация [ править ]

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

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

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

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

Итеративная реализация [ править ]

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

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

Рандомизированный алгоритм Краскала [ править ]

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

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

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

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

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

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

Алгоритм рандомизированного Прима [ править ]

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

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

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

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

Измененная версия [ править ]

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

Упрощенная версия [ править ]

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

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

Алгоритм Вильсона [ править ]

Основная статья: Случайное блуждание со стиранием цикла

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

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

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

Алгоритм Олдоса-Бродера [ править ]

Алгоритм Олдоса-Бродера также создает однородные остовные деревья.

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

Рекурсивный метод деления [ править ]

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

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

Рекурсивное создание лабиринта

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

Простые алгоритмы [ править ]

3D-версия алгоритма Прима. Вертикальные слои пронумерованы от 1 до 4 снизу вверх. Лестница наверх обозначена "/"; лестница вниз с "\" и лестница вверх и вниз с "x". Исходный код включен в описание изображения.

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

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

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

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

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

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

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

См. Также [ править ]

  • Алгоритм решения лабиринта
  • Самопроизвольная прогулка

Ссылки [ править ]

  1. ↑ Уилсон, Дэвид Брюс (22–24 мая 1996 г.). «Генерация случайных остовных деревьев быстрее, чем время покрытия». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . Симпозиум по теории вычислений. Филадельфия: ACM. С. 296–303. CiteSeerX  10.1.1.47.8598 . DOI : 10.1145 / 237814.237880 . ISBN 0-89791-785-5.
  2. ^ Jamis Buck (29 декабря 2010). «Генерация лабиринта: алгоритм Эллера» .
  3. ^ Jamis Buck (3 февраля 2011). «Генерация лабиринта: алгоритм сайдвиндера» .
  4. ^ a b c d e Натаниэль Джонстон ; и другие. (21 августа 2010 г.). «Лабиринт - LifeWiki» . LifeWiki . Проверено 1 марта 2011 года .

Внешние ссылки [ править ]

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