Создание идеального лабиринта с помощью упрощённого алгоритма Прима

[Spirit412]

Есть ли алгоритмы для построения 2.5D лабиринта. Когда есть мосты/тунели через стену?

Как то давно видел такое. Напечатанное в журнале. Вид - изометрия.

Намного увлекательнее обычного 2D.

[Pochemuk]

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

[rivo]

Скорее всего это Wave Function Collapse (WFC)

[Pochemuk]

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

Искал на просторах Инета. По-буржуйски такие лабиринты называются "Layered Pipe Maze" (Лабиринт из слоёв труб), но толкового описания алгоритма генерации не нашел. Вернее, пока что не нашел вообще никакого.

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

1. На разных уровнях должны находится только пересечения, а не коридоры, идущие в одном направлении.

2. Тупики не должны находится под/над другим коридором.

Иначе лабиринт станет не наглядным и трудным для восприятия.

[wataru]

Если вам надо, чтобы все еще был ровно один путь к выходу, то алгоритм вообще не меняется. Меняются только ребра. У автора выше каждая клетка связана лишь с 4 соседями по стороне. у вас же добавляются еще мосты. Если их должно быть не много, то добавьте их в граф случайным образом, потом какие-то из них будут включены алгоритмом в остовное дерево и их надо будет взять в лабиринт. Остальные - выкинуть.

[Pochemuk]

По сути, меняются даже не рёбра, а их количество.

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

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

1. Допустим по горизонтали есть подряд 4 клетки A, B, C и D. A соединена с C, а B с D. Таким образом, между B и C есть участок, полностью скрытый под другим участком. Его не будет видно, что скажется на визуальном восприятии лабиринта.

2. Если тупик будет заканчиваться над перпендикулярным коридором, то будет казаться, что он его разрывает. А если завести тупик под мост, то тоже будет выглядеть неаккуратно.

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

[Pochemuk]

Всё же интереснее не упрощенный, а модифицированный алгоритм Прима.

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

Краткое описание модифицированного алгоритма Прима:

1. Клетки (комнаты) могут находится в следующих состояниях: "raw" (еще не обработанные), "done" (присоединенные к лабиринту, "candidate" (кандидаты на присоединение) и "none" (неприсоединяемые клетки за пределами лабиринта или внутри области построения).

2. Вначале все клетки имеют значение "raw" или "none".

3. Выбираем случайную "raw"-клетку и назначаем ей значение "done" (присоединяем её к пустому лабиринту).

4. Все "raw"-клетки из окружения присоединенной переводим в состояние "candidate".

5. Если список "candidate" пуст, то лабиринт завершен (п. 9). Иначе - следующий пункт.

6. Cлучайным образом выбираем клетку из списка "candidate" и убираем стену между нею и "done"-клеткой из её окружения. Если таких "done"-клеток несколько, то выбираем одну из них случайным образом.

7. Рассмотренную "candidate" клетку присоединяем к лабиринту (назначаем ей значение "done").

8. Повторяем с п. 4.

9. Выход.

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

Но самое интересное, что это позволяет ввести еще и дополнительные модификации:

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

Т.е. одним вероятностным параметром задается, следует ли присоединять одну из последних добавленных в "candidate" клеток, а второй параметр задаёт, взять ли самую последнюю "candidateЭ-клетку (а самой последней записывается та, которая продолжает направление движения из клетки, к которой идет присоединение).

Первый параметр влияет на протяженность коридоров, а второй - на их прямолинейность.

[ScienceInCode]

Интересная реализация!
Вопрос по производительности: как ведёт себя алгоритм на больших размерах (10000x10000+)?
Из опыта работы с процедурной генерацией: для игр часто критична не только скорость генерации, но и локальность — возможность генерировать лабиринт по частям (chunk-based).
Можно ли адаптировать Prim под потоковую генерацию? Или для этого лучше подойдёт Recursive Backtracker / Wilson's algorithm?
P.S. Для второй реализации с random edge — не пробовали использовать heap/priority queue вместо списка? Должно дать прирост на больших лабиринтах с O(n²) до O(n log n).

[uzra]

Асимптотика алгоритма - O(количества рёбер), что примерно равно O(0.5*a*b)
Для размеров 10000 на 10000 время выполнения на питоне примерно 3-5 минут

[wataru]

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

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

[Pochemuk]

При генерации пещерных лабиринтов используют схожую идею:

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

2. В некоторых общих участках делаются проходы (собственно, генерация лабиринта, только не на регулярном поле, а на иррегулярном.).

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

4. Эти комнаты соединяются между собой через проходы коридорами.

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