На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.

Разбиение пространства

Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.

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

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


Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.

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


Хорошие результаты даёт максимальное соотношение от 2.0 до 3.0:

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

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

Вот результаты:

Выбор рёбер

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

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


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

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

Генерация коридоров

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

Вот результаты:

Генерация пещер

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

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

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


Затем мы запускаем клеточный автомат:



Вот ещё несколько примеров результатов:


Позже я добавлю заливку для удаления недостижимых частей.

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

Удаление изолированных ячеек

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

Множественные коридоры между комнатами

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

Вот разница результатов до применения шума к соединяющимся комнатам и сразу после, параметр меняется всего на одну единицу:



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


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

Генерация тайлов для пещер

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

Вот примеры результатов:


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


Следующими этапами генерации подземелья будет добавление декораций и монстров.