Процедурная генерация случайных игровых подземелий

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

Оригинальное описание алгоритма

1. Сначала я задаю нужное количество комнат – к примеру, 150. Естественно, цифра произвольная, и чем она больше, тем сложнее будет подземелье.

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

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

Кроме того я проверяю, что соотношение длины и ширины комнаты не слишком велико. Нам не нужны как идеально квадратные комнаты, так и сильно вытянутые.

3. И вот у нас есть 150 случайных комнат, расположенных на небольшом пространстве. Большинство из них наезжают друг на друга. Теперь мы осуществляем их разделение по технологии separation steering, чтобы разделить прямоугольники так, чтоб они не пересекались. В результате они не пересекаются, но находятся достаточно близко друг от друга.

4. Заполняем промежутки клетками размером 1х1. В результате у нас получается квадратная решётка из комнат различного размера.

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

6. Следующий шаг – связывание комнат вместе. Для этого мы строим граф, содержащий центры всех комнат при помощи триангуляции Делоне. Теперь все комнаты связаны меж собой непересекающимися линиями.

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

8. Дерево получается аккуратным, но скучным – никаких вам замкнутых ходов. Поэтому мы случайным образом добавляем обратно примерно 15% ранее исключённых рёбер графа. В результате получится граф, где все комнаты гарантированно достижимы, с несколькими замкнутыми ходами.

9. Чтобы превратить его в коридоры, для каждого ребра строится серия прямых линий (в форме Г), идущих по рёбрам графа, соединяющим комнаты. Тут нам пригождаются те клетки, которые остались неиспользованными (те, что не превратились в комнаты). Все клетки, накладывающиеся на Г-образные линии, становятся коридорами. А из-за разнообразия размеров клеток стены коридоров будут неровными, что как раз хорошо для подземелья.

И вот пример результата!

Осторожно — под катом много монстров анимированных гифок!

В посте на Gamasutra пользователь A Adonaac взял на себя труд подробнее описать некоторые детали. В целом работа алгоритма визуально выглядит следующим образом:

Создание комнат

Сначала необходимо создать несколько комнат с определёнными высотой и шириной, случайным образом расположенных внутри заданного круга. Алгоритм с TKdev использовал нормальное распределение для выбора размеров комнат, и мне кажется, что это неплохая идея – у вас появляется больше параметров, с которыми можно поиграться. Разного вида подземелий можно добиться, выбирая различные отношения высоты к ширине и стандартные отклонения.

Одна из функций, которые вам могут понадобиться — 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

Вот здесь подробнее описана её работа. После этого можно будет получить нечто вроде следующего:



Очень важно отметить, что поскольку вы имеете дело с решёткой из плиток, вам необходимо будет разместить все комнаты вдоль одной решётки. В вышеприведённой гифке плитки имеют размер в 4 пикселя, поэтому все позиции и размеры комнат должны быть кратны 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

Разделяем комнаты

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



Физические тела не привязаны к нашей решётке, но, назначая комнатам позиции, мы обёртываем их в вызовы roundm, в результате чего получаются комнаты, не накладывающиеся друг на друга и расположенные на решётке. На гифке представлен этот процесс. Голубые контуры обозначают физические тела. Между ними и реальными позициями комнат есть небольшое несоответствие из-за постоянных округлений.



Одна из проблем, которые могут возникнуть при этом, может встретиться вам, если вы специально пытаетесь вытянуть комнаты преимущественно вдоль одной из осей. Рассмотрим для примера игру, над которой я работаю:



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



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



Для случайного распределения комнат в полоске поменяем функцию 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

Основные комнаты

На следующем шаге мы определяем комнаты, которые станут основными. В алгоритме TKdev всё просто – выбрать те комнаты, высота и ширина которых превышают заданные значения. На следующей гифке я использовал ограничение 1,25*mean – то есть, если width_mean и height_mean равны 24, тогда основными станут комнаты с высотой и шириной больше 30.

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

Теперь мы берём центры выбранных комнат и скармливаем данные в процедуру обработки. Её можно написать самому или взять готовую – мне повезло, и я нашёл готовую, за авторством Yonaba. Она принимает точки и выдаёт треугольники



Получив треугольники, можно конструировать граф. Подсказка: удобно назначить комнатам уникальные id, и работать с ними, а не копировать сами объекты комнат.

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

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



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



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

Коридоры

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

Я осуществлял такую проверку, находя среднюю точку между положениями двух узлов, и проверяя, находятся ли координаты этой точки на уровне комнаты (на горизонтали или вертикали). Если они находятся на уровне, я провожу одну линию. Если нет – две, от комнаты до точки, и от точки до другой комнаты.



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

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



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

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



Вот и всё, ребята!



В результате я получаю структуру данных, в которой есть:

• список комнат (каждая из которых – структура с уникальным id, позицией x/y, и высотой/шириной)
• граф, в котором каждый узел указывает на id комнаты, а рёбра содержат расстояния между комнатами в клетках
• 2д-решётку, в которой каждая клетка может быть пустой, указывать на основную комнату, указывать на комнату, принадлежащую к системе коридоров, или на клетку узкого коридора

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