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

Question

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

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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

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

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

Answer 7

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

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

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