Хабрахабр

[Перевод] Генерация подземелий и пещер для моей игры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть