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

Ответ 1

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

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

Они производят только 10% мертвых концов

http://www.astrolog.org/labyrnth/sample/recursiv.gif

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

Ответ 2

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

• Kruskal's
• Прим
• Рекурсивный Backtracker
• Aldous-Broder
• Растущее дерево
• Hunt-and-Kill
• Уилсон
• Эллер
• Сотовый автомат (простой)
• Рекурсивный отдел (очень легко)
• Sidewinder (предсказуемый)
• Двоичное дерево (с ошибкой)

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

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

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

Ответ 7

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

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

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