Алгоритм процедурной генерации подземелий

В этой статье объясняется методика генерации случайных подземелий, опубликованной на Gamasutra и впервые описанная разработчиком игры TinyKeep на Reddit. Здесь все шаги будут рассмотрены чуть подробнее. Демонстрацию алгоритма можно найти на этой странице (flash более не поддерживается), а в общем и целом алгоритм работает вот так:

Генерация комнат

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

Здесь вам может понадобиться функция getRandomPointInCircle:

function getRandomPointInCircle(radius)
local t = 2*math.pi*math.random()
local u = math.random()+math.random()
local r = nil
if u > 1 then r = 2-u else r = u end
return radius*r*math.cos(t), radius*r*math.sin(t)
end

Подробнее узнать о работе этой функции можно тут. В итоге у вас должно получаться что-то подобное:

Важное замечание: раз уж вы (по крайней мере на концептуальном уровне) имеете дело с сеткой из тайлов, нужно всё подгонять под эту сетку. На gif-изображении ниже размер тайла составляет 4 пикселя, следовательно все размеры комнат кратны четырём. Для этого я выполнил назначение позиции и ширины/высоты в виде функции, округляющей числа до размера тайла:

function roundm(n, m) return math.floor(((n + m - 1)/m))*m end

— Теперь мы можем поменять значение, полученное из getRandomPointInCircle:

function getRandomPointInCircle(radius)
...
return roundm(radius*r*math.cos(t), tile_size),
roundm(radius*r*math.sin(t), tile_size)
end

Разделение комнат

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

Сами физические тела никак не привязаны к тайловой сетке, но вызов roundm во время назначения позиций приводит к не пересекающимся комнатам, которые соответствуют сетке. На gif-картинке ниже этот процесс показан в действии – синим очерчены физические тела, их положение всегда немного не совпадает с комнатами из-за округлённых координат:

Вы можете столкнуться с определёнными трудностями, если комнаты должны быть вытянуты по горизонтали или вертикали. Как пример, вот игра, над которой я сейчас работаю:

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

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

Для создания комнат в полосе мы просто меняем функцию getRandomPointInCircle так, чтобы она строила точки в пределах эллипса (для примера ниже я устанавливал ellipse_width = 400 и ellipse_height = 20):

function getRandomPointInEllipse(ellipse_width, ellipse_height)
local t = 2*math.pi*math.random()
local u = math.random()+math.random()
local r = nil
if u > 1 then r = 2-u else r = u end
return roundm(ellipse_width*r*math.cos(t)/2, tile_size),
roundm(ellipse_height*r*math.sin(t)/2, tile_size)
end

Главные комнаты

Следующий шаг определяет, какие комнаты являются главными/центральными, а какие нет. Здесь в оригинале избран надёжный подход: выбор комнат с размерами выше определённого порогового значения. Для примера ниже я выбрал 1,25*среднее значение, то есть, если у нас width_mean и height_mean равны 24, то будут выбраны комнаты с размерами больше 30.

Триангуляция Делоне и построение графа

Теперь мы берём все центральные точки главных комнат и скармливаем их процедуре Делоне. Процедуру пишем самостоятельно или же пользуемся чьим-то готовым вариантом из Интернета. На моё счастье, такая процедура уже написана Yonaba. Как видно ниже, она берёт точки и выстраивает из них треугольники.

Когда у нас есть треугольники, можно строить граф. Это довольно простая процедура, при условии, что у вас на руках есть библиотека/структура данных графа. Если вы ещё этого не сделали, будет полезным присвоить объектам/структурам, отвечающим за комнаты, уникальные идентификаторы, чтобы эти идентификаторы можно было добавить в граф вместо утомительного копирования.

Минимальное остовное дерево

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

Минимальное остовное дерево обеспечит достижимость всех главных комнат, при этом не делая их слишком сильно связанными между собой. Это полезно, поскольку мы обычно не хотим, чтобы все комнаты в подземелье можно было проходить насквозь, но и не хотим изолированных островков. Однако, один единственный верный путь нам тоже не нужен, так что мы возвращаем пару рёбер из графа Делоне:

Это создаст дополнительные маршруты и подземелье получится более интересным. В оригинале возвращается 15 % рёбер, я же решил, что подходящим значением будет 8-10 %. Тут всё зависит от выбранной вами степени связанности подземелья.

Коридоры

И напоследок нам надо добавить коридоры. Для этого мы берём каждый узел графа и соединяем его линиями со всеми смежными узлами. Если узлы находятся примерно на одной горизонтали (похожая y-позиция), мы соединяем их горизонтальными линиями. Если примерно на одной вертикали – вертикальными. Если узлы расположены далековато друг от друга в обоих направлениях, соединяем их с помощью двух линий в форме Г.

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

На картинке выше есть примеры всех вариантов: узлы 62 и 47 соединены горизонтальной линией, 60 и 125 вертикальной, а 118 и 119 линией в форме Г. Важно знать, что я создаю не только эти линии. Это лишь те линии, что я провожу, но я делаю ещё 2 дополнительные по бокам от каждой на расстоянии tile_size, чтобы ширина всех коридоров составляла хотя бы три тайла.

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

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

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

На этом всё готово!

Заключение

Структуры данных, полученные мной после всей процедуры: список комнат (каждая комната – это структура с уникальным идентификатором, координатами x и y, и шириной/высотой); граф, где каждый узел указывает на идентификатор комнаты, а у рёбер расстояние между комнатами выражено в тайлах; сама 2D-сетка, где каждая ячейка может быть ничем (то есть пустой), указывать на главную комнату, на коридорную комнату или быть ячейкой коридора. Думаю, с этими тремя структурами из сгенерированной схемы возможно получить любой желаемый тип данных, после чего уже определяться с расположением дверей, врагов, предметов, боссов и так далее.

Gamasutra, Procedural Dungeon Generation Algorithm.