На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.
Разбиение пространства
Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.
Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.
Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:
Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Поэтому я использовал другой способ, преимущество которого заключается в том, что он обладает одним параметром и легко понятен: максимальным допустимым соотношением между длиной и шириной ячеек. При сэмплировании нового разделения я сначала вычисляю минимальное и максимальное значения, которые оно может иметь, чтобы соотношение для двух новых ячеек было меньше предельного, а затем выполняю равномерное сэмплирование между этими двумя границами. Вот результат при варьировании максимально допустимого соотношения:
Хорошие результаты даёт максимальное соотношение от 2.0 до 3.0:
Генерация комнат
Следующий этап — генерация в каждой ячейке комнаты. Здесь нет особых проблем, я просто задал ограничения, чтобы комнаты не были слишком маленькими и не оказались слишком близко к стенам ячейки.
Вот результаты:
Выбор рёбер
В генераторах подземелий на основе двоичного разбиения пространства двоичное дерево, использовавшееся на этапе разбиения пространства, обычно используется повторно для генерации коридоров. Я не делал этого, потому что такой подход мне кажется ограничивающим.
Вместо этого на этапе разбиения пространства я строю структуру двусвязного списка рёбер, который позволяет знать, какие ячейки расположены рядом друг с другом. Таким образом я получаю следующие графы:
У такого подхода есть три преимущества. Первое: если в дальнейшем я захочу изменить способ разбиения пространства, то остальная часть генератора останется действующей, потому что она получает на входе только полурёберную структуру данных. Второе: теперь для выбора рёбер, которые станут коридорами, я могу использовать любой алгоритм генерации лабиринтов. Третья: если я захочу добавить в подземелье петли, то легко смогу это реализовать.
Пока я просто использую алгоритм Крускала и расстояние городских кварталов для выбора рёбер. Вот результаты:
Генерация коридоров
Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора, потому что мне нужно быть аккуратным, чтобы ни один коридор не пересекался с другим.
Вот результаты:
Генерация пещер
Предыдущие результаты подходили для создания подземелий, склепов и других рукотворных структур, но пещерам и шахтам я хотел придать более природный вид. Классический способ генерации пещер — использование клеточного автомата, как это описано в данной статье на RogueBasin. Большая проблема клеточных автоматов заключается в том, что их результаты не совсем контролируемы.
Я решил всё равно использовать для создания естественного внешнего вида клеточные автоматы, но наложить на них ограничения для получения контролируемого результата. Вместо всего двух состояний: мёртвый и живой, я использую четыре: совершенно точно мёртвый, мёртвый, живой, совершенно точно живой. «Совершенно точные» состояния не могут изменяться в процессе, они используются для ограничения результатов.
Комнаты и коридоры, сгенерированные на предыдущих этапах, заполняются «точно живыми» клетками. То есть у нас всё равно остаются опорные комнаты и мы гарантируем, что они будут соединены друг с другом. Рёбра, которые не были выбраны, заполняются «точно мёртвыми» клетками, чтобы между комнатами не появлялось никаких новых путей. Наконец, вокруг комнат и коридоров мы случайным образом делаем некоторые ячейки живыми. Вот изначальная конфигурация:
Затем мы запускаем клеточный автомат:
Вот ещё несколько примеров результатов:
Позже я добавлю заливку для удаления недостижимых частей.
Это первый шаг в длинном пути по созданию генератора интересных подземелий. Я доволен результатами. Особенно я горжусь методом клеточных автоматов с ограничениями, создающим контролируемые и естественные пещеры. Ещё мне нравится то, что каждый этап генерации отделён от остальных и может модифицироваться индивидуально.
Удаление изолированных ячеек
Затем я реализовал заливку для удаления недоступных ячеек:
Множественные коридоры между комнатами
Экспериментируя с параметрами генератора я обнаружил, что если добавить между соединяющимися комнатами немного шума, то получатся интересные результаты.
Вот разница результатов до применения шума к соединяющимся комнатам и сразу после, параметр меняется всего на одну единицу:
Если сделать комнаты немного больше, то результат получится ещё более интересным:
Здорово, что у нас есть случайность и возникают красивые структуры, но в то же время сохраняется структура графа и обозначения комнат, которые будут полезны:
Генерация тайлов для пещер
Почти всё своё время я потратил на генерацию тайлов. Это не очень трудно, но для правильной реализации нужны небольшие хитрости.
Вот примеры результатов:
Очень здорово то, что можно очень легко переключиться с каменной пещеры на песчаную или ледяную:
Следующими этапами генерации подземелья будет добавление декораций и монстров.
Комментарии (22)
Mishootk
24.07.2019 18:08Глядя на результат генерации пещер из комнат интуитивно подставился алгоритм двумерного шума. При генерации шума можно задать уровни комнат и стен такими значениями, чтобы любые шумовые отклонения не выводили их за пороговое значение. Тогда в конце получившийся «рельеф» заливается по уровню «водой» и получаем примерно такой же результат в виде связаных пещер или островов и каналов (для разных игр можно трактовать по разному). Я бы выбрал этот алгоритм как более контролируемый.
SadOcean
24.07.2019 22:26Ну базовый алгоритм будет тот же, просто вместо клеточного автомата можно использовать шум.
shaman4d
24.07.2019 21:19+2«Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора» и она такая хитрая что автор о ней решил просто промолчать. Прекрасно зачем тогда было писать статью…
nightrain912
25.07.2019 12:39А чего там хитрого? Там видно же, как он сделал.
Для каждого соединения:
- Взять две соединенные комнаты
- Получить дельту позиций комнат и выбрать максимальный по модулую компонент (x или y).
Так мы понимаем, горизонтальный или вертикальный коридор и с какой стороны - Получить минимальную и максимальную позицию коридора (для y:
minY = Max(firstRoom.y, secondRoom.y)
maxY = Min(firstRoom.y + firstRoom.height, secondRoom.y + secondRoom.height)
Min и Max не перепутаны) - Если min > max, тоннель нужно "сломать" посередине
- Выбрать позицию из указанного интервала: tunnelY = Random.Range(minY, maxY — tunnelHeight)
- Нарисовать тоннель
Если проще: понять, горизонтальный или вертикальный коридор нужно нарисовать и нарисовать его, не выходя за границы комнат.
IntActment
25.07.2019 12:06Возможно, я просто придираюсь, но мне не очень нравится результат самой первой итерации дробления пространства: из-за деления «от одной стенки до противоположной — одной прямой линией» сразу бросается в глаза строгая граница, делящая лабиринт пополам, и это свойство алгоритма проявляется в любом варианте генерации. Да, позже добавленные коридоры немного ослабляют эффект, но все же.
CryptoPirate
25.07.2019 12:56Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора, потому что мне нужно быть аккуратным, чтобы ни один коридор не пересекался с другим.
А зачем запрет на пересекание? Было бы больше всяких ветвистых коридоров с перекрёстками.
trapwalker
25.07.2019 14:31Видимо за тем, что это игровой уровень, а не обои на рабочий стол. Там надо боссов расставлять, ловушки, двери, ключи. А смысл, если от рандома зависит срежем мы путь от старта до финиша или нет.
Перекрёстки должны допускаться только умышленно.CryptoPirate
25.07.2019 15:43В примерах есть ветвления, но они идут через другие комнаты (например маленькая комната в центре на первом рисунке). Тут не описано что должен быть один путь через все комнаты в определённом порядке (хотя, я мог пропустить). Выходит, монстров, босов, закрытые двери итд всё равно нужно руками расставлять.
trapwalker
26.07.2019 08:27В том-то и дело, что нет. В описанном варианте у нас сначала строится граф связности, а потом на его основе все рисуется. Руками ничего расставлять не нужно, все можно автоматизировать.
Проблема не в том, что будет два пути или один, а в том, чтобы иметь возможность этим управлять. Если допустить чрезмерную эрозию стен, то могут появиться незапланированные и не описанные исходным графом дыры. Их придётся детектировать, учитывать, отбраковывать лабиринты с неудобными подходами… Лучше чтобы сразу все по порядку шло предсказуемо и по плану.
ybeltukov
25.07.2019 19:25Разбиение пространства напомнило работы Пита Мондриана:
Генерацию подобных картин я когда-то делал с помощью Wolfram Mathematica. Для более равномерного разбиения я тогда использовал бета-распределение.
staticmain
А потом в соседних тредах все как один доказывают, что математика, графы и деревья «нинужны!», что «я ни разу не пользовался, почему их спрашивают на собеседовании!».
Brightori
Нужны канешн ), просто про деревья обычно спрашивают на собеде всякие штуки которые давным давно читал в учебнике, плюс придираются к формулировкам. А вакансия вообще про UI ), где большую часть времени надо старые префабы переделывать.
По теме статьи — генерация контента очень прикольная и интересная тема ), результат у автора на первый взгляд ничошный такой.
Zibx
Тут использовались базовые структуры. Они, тригонометрия и линейка радостно вылезают при касании программистом геймдева. С другой стороны можно обойтись без какой-либо математики, но тогда будут решаться другие задачи или другими способами. Умение выбрать подходящую структуру и реализовать её (после чего, возможно, выкинуть свою реализацию и взять готовую) — чертовски ценно и именно оно требуется программистам. На собеседованиях же могут спросить нюансы вращения B+tree с размером указателей в ребёнке перевалившим за размер сектора диска. Когда мне попадалось такое — я уходил. Сам когда искал людей — таким не страдал.
ledocool
А я скажу так:
Для программирования математика не нужна. Программирование вообще сугубо гуманитарная дисциплина. Это ведь в первую очередь язык и умение им пользоваться. Вы ведь разговор/письмо на английском не считаете тех. дисциплиной? Конечно, я понимаю, что в основном на этом языке говорят о теоремах и выражениях, но все же. Да и посмотрите на языки высокого уровня — мы всячески идем к тому, чтобы в свободной форме изложить компу задачу, а как ее делать он решал сам.)
Другое дело, если разговор заходит о графах и деревьях.
В тех тредах абсолютно правы — там собираются веб программисты. Для веба мозгов не надо. Представьте, если вы пришли устраиваться кассиром в Ашан, а вас просят деревьями повертеть. (Поэтому веб-комьюнити радостно ищет идолов во всяких SOLID'ах. А то иначе тру от нетру не отличить.)
Так вот, математика нужна когда начинаешь делать крутые вещи, а не копипастить REST контроллеры со stack overflow.
alloky
Не соглашусь. Программирование это в первую очередь техническая смекалка: как организовать обработку данных чтобы было удобно пользоваться и поддерживать
movl
А я не считаю, что делаю не крутые вещи, хоть и вебом занимаюсь. И в геймдеве, к слову, успел поработать, вот со всеми этими, с матаном, линалом, структурами, алгоритмами и т. д. Но надо понимать, что применение этих знаний, необходимо в очень ограниченном количестве, 90% это вся та же самая рутина, с копипастой и прочими атрибутами. В настоящий момент мне удается получать удовольствие, например от решения какой-нибудь необычной архитектурной задачи, и все также пригождаются специфичные знания и опыт, aka мозги.
ledocool
Вот у меня так не получается. Почему-то веб никак не выходит считать серьезной дисциплиной. И оттого особенно грустно, что в общем-то дальше веба мне никуда не уползти.
knotri
Вы плохо тут статью прочитали — там жаловались на то что вопросы были НЕ СВЯЗАННЫЕ С РАБОТОЙ.
Если бы после собеседования про графы, математику и генерацию пещер вас бы взяли на работу ВНЕЗАПНО делать графы и генерировать пещеры — все супер.
Проблема когда вас после математических вопросов берут перекрашивать кнопку из синего в красный, а потом это по ФТП на прод заливать
Ckpyt
А никто заранее не знает чем будет заниматься разработчик в команде. То есть, конечно, преполагается, что он что-то будет делать… но потом тимлид понимает возможности каждого конкретного человека и, если это хороший тимлид, он старается выжать из него максимум. Меня вот брали на должность перекрашивать кнопки, в итоге занимаюсь бакендом. Т.е. вся эта вот математика, графы и все такое вот.
ledocool