Генерация подземелий: принципы создания случайных запутанных локаций

Поэтапное формирование уровня.

Французский инди-разработчик Пьер Вигьер продолжает описывать процесс создания игры Vagabond в своём блоге. На этот раз он рассказал о генерации подземелий и подходах, которые он использовал.

В прошлом тексте Пьер описывал процесс создания точечного источника освещения.

Есть много способов для генерации подземелий — рандомное размещение, с помощью агента, физического движка, separation steering behavior и так далее. Но Пьер в своём проекте использовал метод разбиения пространства.

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

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

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

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

Обычно в генераторах подземелий, основанных на двоичном разбиении пространства, двоичное дерево также используется и для создания коридоров. Пьер решил отказаться от этого из-за ограничений подхода. Вместо этого он применяет полурёберную структуру данных, которая позволяет узнать, какие ячейки находятся рядом друг с другом.

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

На данный момент он использует алгоритм Краскала с манхэттенским расстоянием для выбора рёбер.

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

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

Идея Пьера заключается в том, чтобы использовать клеточные автоматы для получения природного вида комнат, но задавать ограничения, чтобы иметь управляемый результат. Вместо того, чтобы использовать только два состояния — «мёртвое» или «живое», он использует четыре: «однозначно мёртвое», «мёртвое», «живое», «однозначно живое». Состояния «однозначно» не могут меняться от одного шага к другому — они нужны для ограничения результата.

Комнаты и коридоры, созданные на предыдущих этапах, заполнены «однозначно живыми» клетками. Таким образом, сохраняется понятие комнат, которые связаны друг с другом. Границы заполняются «однозначно мёртвыми» клетками, чтобы не появились новые пути между комнатами. Вокруг комнат и коридоров рандомно располагаются «живые» клетки.

Затем запускается клеточный автомат, чтобы получить природный вид помещений.

Вот ещё несколько примеров.

Следующий шаг — убрать ячейки, оторванные от основной карты.

По ходу работы Пьер обнаружил интересный эффект — если повысить параметр шума вокруг комнат и увеличить их размер, то появится больше коридоров, а в некоторых случаях помещения почти объединятся.

В результате получаются очень интересные локации, но при этом сохраняется структура графа и понятие комнат.

Очевидно, что для генерации подземелий можно использовать самые разные подходы, поэтому не нужно ограничиваться описанным методом. Тем не менее Пьер создал генератор, который отвечает всем критериям и выдаёт нужные локации.

#генерация #опыт #истории