Какой хороший алгоритм для создания лабиринта?

StackOverflow https://stackoverflow.com/questions/38502

  •  09-06-2019
  •  | 
  •  

Вопрос

Скажем, вы хотите простой лабиринт на сетке N by M с одним проходом и большим количеством тупиков, но это выглядит " right " (то есть, как будто кто-то сделал это вручную, не слишком много маленьких крошечных тупиков и все такое). Есть ли известный способ сделать это?

Это было полезно?

Решение

От http://www.astrolog.org/labyrnth/algrithm.htm

  

Рекурсивный бэк-трекер. Это в некоторой степени связано с методом решения рекурсивного бэк-трекера, описанным ниже, и требует стека до размера лабиринта. При вырезании будьте как можно более жадными, и всегда делайте вырезки на необработанный участок, если он находится рядом с текущей ячейкой. Каждый раз, когда вы переходите в новую ячейку, вставляйте прежнюю ячейку в стек. Если рядом с текущей позицией нет неразделенных ячеек, вставьте стек в предыдущую позицию. Лабиринт делается, когда вы вытаскиваете все из стека. Этот алгоритм приводит к лабиринтам примерно с & Quot; river & Quot; фактор, насколько это возможно, с меньшим, но более длинным тупиком, и, как правило, очень длинный и извилистое решение. Он работает довольно быстро, хотя алгоритм Прима немного быстрее. Рекурсивное отслеживание в обратном направлении не работает как сумматор, так как это приводит к пути решения, который следует за внешним краем, где вся внутренняя часть лабиринта прикреплена к границе одним стержнем.

Они создают только 10% тупиков

является примером лабиринта, созданного этим методом.

Другие советы

Оказывается, существует 12 классических алгоритмов для генерации " perfect " лабиринты. Лабиринт идеален, если в нем есть одно и только одно решение. Вот несколько ссылок на каждый алгоритм в порядке моих предпочтений.

<Ол>
  • Kruskal's
  • Prim's
  • Recursive Backtracker
  • Aldous-Broder
  • Растущее дерево
  • Охота и убийство
  • Wilson's
  • Эллера
  • Сотовый автомат (легко)
  • Рекурсивное деление (очень просто)
  • Sidewinder (предсказуемый)
  • Двоичное дерево (с недостатками)

    • Для получения дополнительной информации, ознакомьтесь с mazelib в GitHub, библиотеке Python, реализующей все стандартные алгоритмы создания / решения лабиринтов.

    Довольно простым решением может быть присвоение произвольных весов краям графа и применение алгоритма Крускала найти минимальное остовное дерево.

    Лучшая дискуссия об алгоритмах создания лабиринтов: http://www.jamisbuck.org/ Presentations / rubyconf2011 / index.html (был на HN пару дней назад).

    Как ни странно, немного изменив «канонические» правила и начав со случайной конфигурации, Конвея Игра Жизни , кажется, генерирует довольно хорошие лабиринты!

    (я не помню точное правило, но это очень простая модификация, которая имеет тенденцию «уплотнять» популяцию клеток ...)

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

    Изменяя веса для разных типов ребер, вы можете создавать лабиринты с множеством отличительных характеристик или " индивидуальности " ;. Смотрите мой пример здесь:

    https://mtimmerm.github.io/webStuff/maze.html

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

    Начните с сетки, полной стен. Выберите клетку, отметьте ее как часть лабиринта. Добавьте стены ячейки в список стен. Пока в списке есть стены:

    Выберите случайную стену из списка. Если ячейка на противоположной стороне еще не в лабиринте:

    (i) Сделайте стену проходом и отметьте клетку на противоположной стороне как часть лабиринта.

    (ii) Добавьте соседние стены ячейки в список стен.

    Если ячейка на противоположной стороне уже была в лабиринте, удалите стену из списка.

    Для большего понимания нажмите здесь

    Вот алгоритм DFS, записанный в виде псевдокода:

    создайте CellStack (LIFO) для хранения списка местоположений ячеек
    установить TotalCells = количество ячеек в сетке
    выберите ячейку наугад и назовите ее CurrentCell
    set VisitedCells = 1

    while VisitedCells < TotalCells найти всех соседей CurrentCell со всеми неповрежденными стенами
    если один или несколько найдены выберите один наугад
    сбить стену между ней и CurrentCell
    нажмите местоположение CurrentCell на CellStack
    сделать новую ячейку CurrentCell
    добавить 1 в VisitedCells еще вытолкнуть последнюю запись ячейки из CellStack
    сделать это CurrentCell ENDIF endWhile

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top