image

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

image

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


Сначала необходимо создать несколько комнат с определёнными высотой и шириной, случайным образом расположенных внутри заданного круга. Алгоритм с 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


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

image

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

image

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

image

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

image

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

image

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

image

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

image

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

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


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

image

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

image

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

Коридоры


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

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

image

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

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

image

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

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

image

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

image

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

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


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

image

Комментарии (16)


  1. bigfatbrowncat
    22.01.2016 23:56
    +2

    «Коридоры» широковаты, на мой взгляд. Хотя, это лучше, чем ADOM.


    1. Idot
      24.01.2016 06:14
      +1

      Предлагаете соединить комнаты узкими лазами вентиляции?


      1. bigfatbrowncat
        24.01.2016 12:30
        +1

        Нет, просто на диаграмме «комната» от «не комнаты» отличается весьма слабо. Визуально если вы возьмете, скажем, diablo 2 (хотя там лабиринты делались явно иначе), но там «коридор» — это место, где с монстром разминуться точно не удастся. Он шире двери раза в три, от силы.


  1. Sdiwerick
    23.01.2016 10:04
    +9

    Мне кажется, использование физического движка для такой задачи, мне кажется чем-то из разряда «Вещи становятся удивительно похожими на гвозди, если из инструментов у вас только молоток»


    1. Fen1kz
      23.01.2016 17:48
      +1

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

      Так вот, отлично расталкиваю комнаты вот таким кодом:

      Заголовок спойлера
      while(!separated) {
        let separated = true;
        this.preRooms.forEach((room1) => {
          let velocity = new geom.Point();
          let center1 = room1.createRectangle().createCenter();
          this.preRooms.forEach((room2) => {
            if (room1 === room2) return;
      
            if (!geom.Rectangle.intersect(room1.createRectangle(), room2.createRectangle())) return;
      
            let center2 = room2.createRectangle().createCenter();
      
            let diff = center1.clone().sub(center2);
      
            let diffLength2 = diff.length2();
      
            if (diffLength2 > 0) {
              diff.nor();
              velocity.add(diff);
            }
          });
      
          if (velocity.length2() > 0) {
            separated = false;
      
            velocity.nor().mult(4);
      
            room1._position.add(velocity);
            room1.setxy(room1._position);
          }
        });
      }
      


      1. xiWera
        23.01.2016 19:06
        +6

        зачем вообще вводить лишние этапы, вроде «расталкивания», если всё прекрасно можно сгенерить без них?


        1. Roosso
          24.01.2016 00:28
          +5

          Ктстати + в тему.
          Сам писал не раз алгоритмы для ADnD и никогда не прибегал к вопросу о рассталкивании комнат. Даже никогда не шел подобным путем…

          P.S. Не думал, что Хабру интересны подобные алгоритмы. Надо что ли своих статей написать по ним :)


        1. Fen1kz
          24.01.2016 03:18
          +1

          Не поделитесь алгоритмом?


  1. Rylov
    24.01.2016 23:31
    +1

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


    1. FeNUMe
      25.01.2016 00:33
      +2

      У нарисованного руками есть один большой минус — почти нулевая реиграбельность.


      1. DrLivesey
        25.01.2016 11:33
        +1

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


        1. FeNUMe
          25.01.2016 17:31
          +3

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


          1. Tairesh
            26.01.2016 06:22
            -1

            очень мало игроков захотят 3+ раз бегать по одним и тем же локациям и сражаться с одними и теми же противниками

            Вот и я этим дотерам так же говорю, а они глазами хлопают


            1. bigfatbrowncat
              26.01.2016 10:31
              +2

              Думаю, товарищ выше имел в виду singleplayer. В multiplayer противники как раз очень разные


          1. DrLivesey
            26.01.2016 14:00
            +1

            А как же бессмертные Fallout 1/2?


            1. T-D-K
              26.01.2016 17:58

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