Генерация уровней в Unexplored 2

Мы очень гордимся генератором уровней игры Unexplored 2, это программа, отвечающая всем современным требованиям. В посте я расскажу о том, как создаются уровни игры.

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

Имитация «человеческого» дизайна уровней

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

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

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


Рисунок 1: Простой набросок уровня

На следующем этапе добавляются детали: появляется группа комнат, соединённых воротами, которые рассчитаны на прохождение в определённом направлении:


Рисунок 2: Добавленная структура

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


Рисунок 3: Базовый граф

В графе некоторые узлы содержат подузлы, в нашем случае большинство ворот помечены как опасные (H), а одни помечены как открытые (O).

На основании довольно простого анализа и генеративных правил к графу добавляются новые элементы. Например, конечная точка (G) располагается в месте, которое находится достаточно далеко от входов. Кроме того, к графу добавляются небольшие опасности, чтобы сделать уровень более угрожающим.


Рисунок 4: К графу добавлены новые элементы.

Тем временем тайловая карта низкого разрешения преобразуется при помощи нескольких функций шума в тайловую карту высокого разрешения для придания ей более естественного вида:


Рисунок 5: Тайловая карта высокого разрешения

Затем информация из графа используется для украшения тайловой карты и добавления новых элементов:


Рисунок 6: Украшенная тайловая карта.

Карта как она есть генерируется исключительно для представления в геймплее. Белыми тайлами обозначены открытые пространства, а почти все остальные тайлы обозначают очень конкретные геймплейные элементы, например, тайный проход через кусты (зелёные круги), «ворота в зарослях» (зелёные квадраты и сиреневые полосы) или места спауна для привязки деревьев (красные круги с буквой s). Основная часть уровня по-прежнему неопределена, и на этом этапе генератор предполагает, что эти области должны быть заполнены так, чтобы блокировать перемещение игрока.

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


Рисунок 7: Типы поверхности земли (трава, грязь и камни)


Рисунок 8: Вода


Рисунок 9: Растительность и другие украшения

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


Рисунок 10: Готовый уровень

Добавление геймплея

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

Возьмём для примера пещерную карту в более классическом стиле подземелья (по сравнению с лесным уровнем из примера выше). Базовый граф этого уровня имеет всего один вход и ещё пару новых типов ворот. Пара из них закрыта (L): одни ворота ловят игрока с одной стороны в ловушку (T), а тёмно-зелёные я называю «клапаном»: такой тип ворот позволяет игроку проходить только в одном направлении.


Рисунок 11: Базовый граф пещеры

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


Рисунок 12: В пещеру добавлены замки и ключи

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


Рисунок 13: Пещерный уровень в полной детализации

Подведём итог

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

Часть 2. Из тайлов в кривые, или забавы с графами Вороного

Генератор контента Unexplored 2 генерирует тайловые карты. Типичный результат выглядит так:


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

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


Мне думается, что мы довольно неплохо спрятали тайлы, и вот, как мы этого добились.

Магия Вороного

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

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


В Unexplored 2 мы используем другой вид распределения порождающих точек. Во-первых, мы порождаем по одной точке для каждого тайла. Так мы можем быть уверенными, что каждый тайл на тайловой карте будет соответствовать одной ячейке в диаграмме Вороного.

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



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

Результат выглядит примерно так:



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

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



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


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

Игра использует эту информацию для смещения порождающих точек графа Вороного. Каждый загруглённый угол сдвигает местоположение порождающей точки (см. изображение ниже). Кроме того, он также сдвигает порождающие точки четырёх его ортогональных соседей. Этот процесс кумулятивен; порождающие точки могут сдвигаться несколько раз, если они находятся рядом с несколькими углами. Однако после обработки всех смещений порождающие точки немного рандомизируются (примерно на 10% от ширины тайла в каждом из направлений), и окончательное смещение ограничивается максимумом в 40% от ширины тайла.


Результат уже получается довольно качественным:



Но мы ещё не закончили…

Украшаем с умом

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


Результат выглядит так:


Далее мы использовали 3D-ассеты, чтобы добавить обрывам текстур:


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

Локальная вариативность

Углы — не единственный тип смещения, который мы используем. В частности, мы хотим, чтобы рядом с искусственными структурами (например, показанными ниже разрушенными стенами) края были прямее:


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



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


Разве это не красиво?

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

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