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

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

    С http://www.astrolog.org/labyrnth/algrithm.htm

    Рекурсивный backtracker: это в некоторой степени связано с рекурсивным методом решения обратного отслеживания, описанным ниже, и требует, чтобы стек был размером с лабиринт. Когда высекаете, будьте как можно более жадны и всегда высекайтесь в немолотый участок, если он находится рядом с текущей ячейкой. Каждый раз, когда вы переходите к новой ячейке, нажмите бывшую ячейку в стеке. Если нет неотмеченных ячеек рядом с текущей позицией, поместите стек в предыдущую позицию. Лабиринт делается, когда вы выкладываете все со стека. Этот алгоритм приводит к тому, что Mazes имеет как можно более высокий «речной» коэффициент, с меньшим, но более длинным тупиком и обычно очень длинным и извилистым решением. Он работает довольно быстро, хотя алгоритм Prim немного быстрее. Рекурсивный откат не работает как сумматор стены, потому что это приводит к тому, что путь решения следует за внешним краем, где вся внутренность лабиринта прикрепляется к границе одним стеблем.

    Они производят только 10% тупиков

    http://sofru.miximages.com/maze/recursiv.gif

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

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

    1. Краскала
    2. Прима
    3. Рекурсивный Backtracker
    4. Олдос-Бродер
    5. Растущее дерево
    6. Hunt-и Безубойные
    7. Уилсона
    8. Эллер – х
    9. Сотовый автомат (Easy)
    10. Рекурсивный отдел (очень легко)
    11. Sidewinder (предсказуемый)
    12. Двоичное дерево (ошибочное)

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

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

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

    Как ни странно, слегка изменив «канонические» правила и исходя из случайной конфигурации, Game of Life от Conway, похоже, создает приятные лабиринты!

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

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

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

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

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

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

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

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

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

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

    Чтобы узнать больше, нажмите здесь.

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

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

    в то время как VisitCells если один или несколько найденных выбирают один случайным образом
    сбить стену между ней и CurrentCell
    нажмите CurrentCell на CellStack
    сделать новую ячейку CurrentCell
    add 1 to ПосещенныеCells else вывести последнюю ячейку со CellStack
    сделать его CurrentCell endIf endWhile

    Давайте будем гением компьютера.