Создаём случайные подземелья: принципы процедурной генерации 3D-пространств

C подробным описанием всего процесса и ссылкой на репозиторий.

Разработчик под ником Vazgriz опубликовал на YouTube видео, в котором описал принципы работы генератора подземелий в 3D на Unity. Он отметил, что в основе лежит принцип создания 2D-карт, но многоэтажность может добавить несколько проблем. Чтобы справиться с ними, надо использовать 3D-версии алгоритмов и значительно переработать алгоритм поиска пути A*. Выбрали из видео главное.

Алгоритм создания 3D-подземелий похож на таковой для 2D-простанств, поэтому сперва опишем принципы генерации плоских карт.

Сначала нужно рандомно разместить комнаты в пространстве.

Следующий шаг — создание переходов между комнатами. Представим, что каждое помещение — это точка, а линии между ними — коридоры. В результате получится сетка. Для создания этой сетки автор решил использовать триангуляцию по алгоритмам Делоне — этот подход позволяет избежать появления длинных острых треугольников и создать множество сравнительно коротких связей между точками. Чтобы реализовать триангуляцию Делоне, автор использовал алгоритм Боуэра-Уотсона.

Теперь нужно уменьшить количество переходов между помещениями, потому что в игре не нужно так много коридоров. Для этого Vazgriz решил исключить петли и придать сетке древовидную структуру при помощи алгоритма Minimum Spanning Tree (MST). Чтобы сделать это, автор использовал алгоритм Прима.

Следующий важный шаг — поиск путей между комнатами. Для этого Vazgriz использовал алгоритм A* — он нужен, чтобы найти оптимальный путь между двумя точками.

Теперь можно переходить к 3D-подземелью. Общий принцип тот же, но на каждом шаге нужно использовать 3D-версии алгоритмов.

Сперва нужно создать помещения в 3D-пространстве. Главное отличие от предыдущего примера — теперь комнаты находятся на разных этажах.

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

Последний шаг, поиск пути, получился самым сложным. Чтобы реализовать пэсфайндинг в 3D, разработчику пришлось добавить алгоритму A* возможность подниматься и опускаться. Но проблема в том, что в А* не заложено специфическое поведение для таких ситуаций.

Чтобы добавить лестницу, автор решил сделать особую группу тайлов, которая появляется каждый раз, когда нужно создать вертикальный переход.

Чтобы справиться с проблемой, разработчику нужно было научиться помечать всю группу тайлов как занятую — только так A* не прокладывал бы через них путь. Но это намного сложнее, чем может показаться на первый взгляд.

Всё дело в том, что A* в момент поиска пути одновременно прокладывает сразу множество дорожек и одна и та же клетка в одном случае может использоваться в качестве обычного прохода, а в другом — в качестве лестницы. И если добавить тайлы, которые больше одной базовой клетки, то это помешает прокладывать остальные пути. В результате правильный путь может быть не найден, потому что лестница займёт нужное пространство. Если же игнорировать лестницы, то тайлы будут накладываться друг на друга.

Для решения проблемы Vazgriz сделал так, чтобы тайлы сохраняли информацию о всём пути, который ведёт к ним. Если окажется, что следующий тайл находится на пути к предыдущему тайлу, то A* не будет использовать его.

Если использовать такой подход, могут получиться самые разные варианты подземелья: с широкими лестницами, двумя лестницами, ведущими к одной двери, с лестничной площадкой, объединёнными залами и так далее.

В результате весь процесс генерации 3D-подземелий можно описать пятью пунктами.

Если вы хотите более подробно ознакомиться с проектом, вот ссылка на репозиторий.

#левелдизайн #генерация