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

Автор оригинала: Pierre Vigier
  • Перевод

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

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


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

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

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


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

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


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


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


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

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


Выбор рёбер


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

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


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

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


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


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

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


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


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

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

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


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



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


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

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

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


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


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


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

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



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


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


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


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

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


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


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

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 22

    +6
    Вместо этого на этапе разбиения пространства я строю структуру двусвязного списка рёбер


    А потом в соседних тредах все как один доказывают, что математика, графы и деревья «нинужны!», что «я ни разу не пользовался, почему их спрашивают на собеседовании!».
      0
      Нужны канешн ), просто про деревья обычно спрашивают на собеде всякие штуки которые давным давно читал в учебнике, плюс придираются к формулировкам. А вакансия вообще про UI ), где большую часть времени надо старые префабы переделывать.

      По теме статьи — генерация контента очень прикольная и интересная тема ), результат у автора на первый взгляд ничошный такой.
        +2
        Тут использовались базовые структуры. Они, тригонометрия и линейка радостно вылезают при касании программистом геймдева. С другой стороны можно обойтись без какой-либо математики, но тогда будут решаться другие задачи или другими способами. Умение выбрать подходящую структуру и реализовать её (после чего, возможно, выкинуть свою реализацию и взять готовую) — чертовски ценно и именно оно требуется программистам. На собеседованиях же могут спросить нюансы вращения B+tree с размером указателей в ребёнке перевалившим за размер сектора диска. Когда мне попадалось такое — я уходил. Сам когда искал людей — таким не страдал.
          –2
          А я скажу так:
          Для программирования математика не нужна. Программирование вообще сугубо гуманитарная дисциплина. Это ведь в первую очередь язык и умение им пользоваться. Вы ведь разговор/письмо на английском не считаете тех. дисциплиной? Конечно, я понимаю, что в основном на этом языке говорят о теоремах и выражениях, но все же. Да и посмотрите на языки высокого уровня — мы всячески идем к тому, чтобы в свободной форме изложить компу задачу, а как ее делать он решал сам.)

          Другое дело, если разговор заходит о графах и деревьях.

          В тех тредах абсолютно правы — там собираются веб программисты. Для веба мозгов не надо. Представьте, если вы пришли устраиваться кассиром в Ашан, а вас просят деревьями повертеть. (Поэтому веб-комьюнити радостно ищет идолов во всяких SOLID'ах. А то иначе тру от нетру не отличить.)

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

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

              0

              А я не считаю, что делаю не крутые вещи, хоть и вебом занимаюсь. И в геймдеве, к слову, успел поработать, вот со всеми этими, с матаном, линалом, структурами, алгоритмами и т. д. Но надо понимать, что применение этих знаний, необходимо в очень ограниченном количестве, 90% это вся та же самая рутина, с копипастой и прочими атрибутами. В настоящий момент мне удается получать удовольствие, например от решения какой-нибудь необычной архитектурной задачи, и все также пригождаются специфичные знания и опыт, aka мозги.

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

            Вы плохо тут статью прочитали — там жаловались на то что вопросы были НЕ СВЯЗАННЫЕ С РАБОТОЙ.


            Если бы после собеседования про графы, математику и генерацию пещер вас бы взяли на работу ВНЕЗАПНО делать графы и генерировать пещеры — все супер.


            Проблема когда вас после математических вопросов берут перекрашивать кнопку из синего в красный, а потом это по ФТП на прод заливать

              0
              А никто заранее не знает чем будет заниматься разработчик в команде. То есть, конечно, преполагается, что он что-то будет делать… но потом тимлид понимает возможности каждого конкретного человека и, если это хороший тимлид, он старается выжать из него максимум. Меня вот брали на должность перекрашивать кнопки, в итоге занимаюсь бакендом. Т.е. вся эта вот математика, графы и все такое вот.
                +2
                А никто заранее не знает чем будет заниматься разработчик в команде.
                Вот так придешь на разраба, а тебе кофе заваривать поручат. XD
            0
            Глядя на результат генерации пещер из комнат интуитивно подставился алгоритм двумерного шума. При генерации шума можно задать уровни комнат и стен такими значениями, чтобы любые шумовые отклонения не выводили их за пороговое значение. Тогда в конце получившийся «рельеф» заливается по уровню «водой» и получаем примерно такой же результат в виде связаных пещер или островов и каналов (для разных игр можно трактовать по разному). Я бы выбрал этот алгоритм как более контролируемый.
              0
              Ну базовый алгоритм будет тот же, просто вместо клеточного автомата можно использовать шум.
              +2
              «Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора» и она такая хитрая что автор о ней решил просто промолчать. Прекрасно зачем тогда было писать статью…
                0

                А чего там хитрого? Там видно же, как он сделал.
                Для каждого соединения:


                1. Взять две соединенные комнаты
                2. Получить дельту позиций комнат и выбрать максимальный по модулую компонент (x или y).
                  Так мы понимаем, горизонтальный или вертикальный коридор и с какой стороны
                3. Получить минимальную и максимальную позицию коридора (для y:
                  minY = Max(firstRoom.y, secondRoom.y)
                  maxY = Min(firstRoom.y + firstRoom.height, secondRoom.y + secondRoom.height)
                  Min и Max не перепутаны)
                4. Если min > max, тоннель нужно "сломать" посередине
                5. Выбрать позицию из указанного интервала: tunnelY = Random.Range(minY, maxY — tunnelHeight)
                6. Нарисовать тоннель

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

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


                  А зачем запрет на пересекание? Было бы больше всяких ветвистых коридоров с перекрёстками.
                    0
                    Видимо за тем, что это игровой уровень, а не обои на рабочий стол. Там надо боссов расставлять, ловушки, двери, ключи. А смысл, если от рандома зависит срежем мы путь от старта до финиша или нет.
                    Перекрёстки должны допускаться только умышленно.
                      0
                      В примерах есть ветвления, но они идут через другие комнаты (например маленькая комната в центре на первом рисунке). Тут не описано что должен быть один путь через все комнаты в определённом порядке (хотя, я мог пропустить). Выходит, монстров, босов, закрытые двери итд всё равно нужно руками расставлять.
                        0

                        В том-то и дело, что нет. В описанном варианте у нас сначала строится граф связности, а потом на его основе все рисуется. Руками ничего расставлять не нужно, все можно автоматизировать.
                        Проблема не в том, что будет два пути или один, а в том, чтобы иметь возможность этим управлять. Если допустить чрезмерную эрозию стен, то могут появиться незапланированные и не описанные исходным графом дыры. Их придётся детектировать, учитывать, отбраковывать лабиринты с неудобными подходами… Лучше чтобы сразу все по порядку шло предсказуемо и по плану.

                    0
                    Разбиение пространства напомнило работы Пита Мондриана:
                    image
                    Генерацию подобных картин я когда-то делал с помощью Wolfram Mathematica. Для более равномерного разбиения я тогда использовал бета-распределение.
                      0
                      А можете выложить код в свободный доступ? Интересно посмотреть, почитать…
                        0
                        это же перевод) надо идти на источник и там вопрошать

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

                      Самое читаемое