Реализация циклической генерации подземелий “изнутри”: да что тут сложного?05.05.2024 20:15

Вам нравятся старые Legend of Zelda времён SNES и GBA? Может быть, вам пришлась по вкусу Dark Souls? А, возможно, вы ещё и фанат Quake?

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

В наше время расцвета жанра rogue-lite вопрос генерации игровых уровней актуален как никогда. Однако по-настоящему интересные уровни в жанре — большая редкость, я бы даже сказал, феноменальная. Чаще всего уровни представляют собой просто наборы заранее заготовленных комнат-коробок, случайным образом приставленных друг к другу, без какой-либо логичной высокоуровневой картины, с малой связностью или же, напротив, хаотичной повсеместной связностью комнат. Именно по этой причине множество игр с процедурной генерацией смещают внимание игрока с игровых уровней в сторону каких-либо других геймплейных элементов. Фактически, левелдизайн как таковой остаётся весьма нехитрым — есть уровни, и ладно. 

Но, всё же, я знаю одну игру, которая взяла принципиально другой подход: Unexplored. На мой взгляд, она пересмотрела устоявшийся стереотип об ограничениях левелдизайна в рогаликах. Всё, что для этого понадобилось — циклическая генерация подземелий (Cyclic dungeon generation).

К сожалению, описаний этого алгоритма в Сети мною было найдено всего лишь два, одно из которых — статья автора игры Джориса Дорманса (Joris Dormans) [1], а другая — углублённый пересказ этой статьи с прискорбно малым количеством технических деталей, которые ещё и ссылаются на отсутствующие в свободном доступе инструменты [2]. Обе из статей весьма поверхностны и описывают алгоритм слишком высокоуровнево для адекватного воспроизведения. Открытых инструментов, использующих циклическую генерацию, нет вообще, как нет и сколько-нибудь большого количества игр, использующих её.

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

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

Что в этом подходе такого особенного для игрока?

Здесь и далее для простоты нашего подхода будем иметь в виду такие игры, вне зависимости от их жанра (но с уклоном в поджанр adventure), где игрок управляет только одним персонажем. Также мы не рассматриваем игры с открытым миром и «песочницы», так как их левелдизайн преследует иные цели и находится за рамками нашего обсуждения.

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

Абстрактный пример предельно линейного левелдизайна, которому соответствует большинство «рельсовых шутеров» наподобие Call of Duty.  Приведён для наглядности и не более того.

Отличный пример уровней в общей канве подавляющего большинства рогаликов (включая классические) можно видеть в Binding of Isaac.

Уровень из Binding of Isaac и его упрощённый граф.

Это прямо-таки энциклопедический пример древовидного уровня. Для своей игры он отлично справляется с задачей, да и в реализации такой подход наиболее прост, но назвать это полноценным образцом левелдизайна adventure-игры, как по мне, нельзя. 

Какие проблемы можно увидеть, если рассматривать уровни с подобной структурой без привязки к конкретной игре?

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

2. Трудности с логичным размещением интерактивных элементов на уровне. Если бы мы хотели запереть некоторые двери ключами, перед нами встанет проблема осмысленного расположения этих самых ключей — их сбор не должен заставить игрока слишком долго бродить по карте, чтобы не усугубить предыдущую проблему. В идеале игрок должен находить ключи просто «по пути» к финишу уровня, а не тратить лишнее время на поиск того, куда генератор карт этот ключ поставил.

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

3. Крайне малая концентрация player agency в прохождении карты. Отсутствие возможности сделать геймплейно-ориентированные разветвления на картах, когда выбор «идти налево или направо» означает выбор того, как именно мы играем. Фактически, большинство игроков постараются проходить карту, посетив по возможности все комнаты (если речь не про спидран, конечно). Даже если игра даёт возможность проходить уровень несколькими разными маршрутами, смысла в них как таковых мало. За вычетом геймплейных нюансов игроку выгоднее всего проходить уровень в порядке сокровище — магазин — особая комната — испытание — босс, и чаще всего к такому порядку вдумчивый игрок и будет стремиться. Иными словами, даже если вариантов прохождения много, правильным из них является только один. В этом смысле уровень мог бы с тем же успехом быть линейным, чем тратил бы намного меньше времени игрока на брождение по уже исследованным частям.

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

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

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

Пример генерации уровней из Unexplored (взято из [1])

Не правда ли, такой подход звучит интереснее?

Идея генератора

Генератор, бесспорно, хорош, и, пожалуй, действительно наиболее близок к тому, как подземелья проектирует человек. Но как именноэто реализовано?  

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

На самом деле, циклический генератор подземелий работает ещё интереснее. Он не включает в себя готовые рукотворные графы уровней. Совсем! Сами эти графы как таковые генерируются на лету по определённым наборам правил.

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

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

Начальное состояние графа

Простые примеры правил подстановки

Эти правила работают с любыми двумя смежными вершинами А и Б, заменяя их подграф на другой, более сложный подграф.

Пример применения обоих правил к рёбрам изначального графа.

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

Сложности реализации

Звучит достаточно просто, верно? Но, как говорится, дьявол кроется в деталях. Давайте посмотрим на список требований ко внутренней работе такого алгоритма.

Итак:

1. Граф уровня случайно генерируется (не задаётся дизайнером заранее);

2. Граф уровня должен быть планарным (то есть, его должно быть возможно изобразить на плоскости без пересечения рёбер);

3. Граф уровня должен помещаться в квадратной сетке — в нашем случае ведь используется тайловая карта;

4. Граф уровня должен помещаться в достаточно маленьком пространстве — если рассматривать сетку комнат, а не тайлов (а генератор работает с комнатами), то нам не нужны сотни комнат на уровень — пары десятков вполне достаточно (к примеру, типичный размер уровня в той же Unexplored — 5×5 комнат);

5. Сетка, на которой расположены вершины, подразумевает, что смежные вершины графа являются смежными ещё и в геометрическом смысле слова;

6. Граф уровня должен, в общем случае, достаточно хорошо использовать это пространство, не оставляя половину уровня пустой;

7. Алгоритм генерации должен работать за адекватное время.

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

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

Наивный подход даст нам приблизительно следующий алгоритм.

1. Начинаем с неким базовым графом;

2. Делаем один шаг подстановки на этом графе;

3. Проверяем, планарен ли результат;

4. Проверяем, разместим ли он на сетке;

5. Если уровень дорос до необходимых размеров, завершаем генерацию, иначе — GOTO 2.

Подход по ряду причин нельзя назвать приемлемым. Что мы будем делать, если пункты 2 или 3 не выполняются? Мы можем:

• Начать генерацию заново, либо откатиться на один или несколько шагов назад, получив проблему времени работы алгоритма;

• Завершить работу, как только граф более нельзя наращивать без нарушения планарности — чем, скорее всего, получим куцый уровень без нормальной плотности контента.

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

Что же всё-таки сработает?

Итак, наша самая большая проблема — геометрическая (расположение вершин на сетке). Возможно, стоит от этого и отталкиваться?  

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

Итак, начнём с такого графа. Для простоты (и чтобы результат был читаем) рассмотрим граф-сетку размером в 4×4 вершины:

Исходный граф, состояние до начала генерации. Для представления такой структуры подходит обычный двухмерный массив

Показанные рёбра графа — все, возможные на такой структуре при соблюдении правила геометрического соседства смежных узлов.

В реальном случае ни вершин, ни стрелок нет, они все на начальном этапе выключены.

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

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

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

Пример такого правила:

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

Обратите внимание на «квадратность» расположения вершин. Правила, в данном контексте, учитывают сетку, ведь относительное расположение вершин для нас важно. 

Сформулируем его человекочитаемым образом:

1. Берём две смежные активные вершины А и Б, причём такие, что их ребро направлено из А в Б, и что под ними есть две неактивные вершины.

2. Убираем ребро А — Б.

3. Активируем две вершины ниже А и Б, на одну ставим тэг «тревога», на другую — «спящий монстр».

4. Активируем рёбра А — Тревога, Тревога — Спящий монстр, Спящий монстр — Б.

Теперь попробуем применить алгоритм подстановки на графе к такой структуре данных.

Начнём с пустой структуры (в этот раз все неактивные рёбра не будут показаны), заполненной по некому рукотворному начальному правилу. Пусть для примера это будет «два пути от старта до финиша». Применим к этому состоянию указанное выше правило подстановки.

Единственное место, куда это правило «влезет» — вершина слева от финиша и сам финиш. Возьмём их как А и Б соответственно.

Изначальное состояние уровня. Первый цикл со стартом и финишем задан вручную как один из вариантов изначального состояния

Применяем вышеописанное правило

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

Что ж, в целом, вроде бы, работает. Но что, если мы применим это же правило ещё раз?…

Ой. А ведь некуда. Единственные подходящие на роль А и Б вершины — вновь добавленные «тревога» и «спящий монстр», но ниже них заканчивается карта. А ведь хотелось бы, чтобы наши правила также могли «поворачиваться» и, например, растить уровень «вверх», если там есть место.

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

Примеры работы генератора, или немного ASCII

Мой proof-of-concept написан на Go, и рисует результаты генерации в консоль, поэтому примеры работы будет проще для восприятия перерисовать как граф.

Пример работы генератора. Холст, масло, ASCII, Konsole.

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

Тот же пример, в более читаемом виде

Для прохождения обязателен ключ 2 и любой из ключей 1 или 3, поэтому игрок может пройти уровень множеством способов. Игрок может отправиться за ключом 1, но попадёт в ловушку сразу после взятия ключа. С другой стороны, можно пройти по большому циклу и собрать ключ 3 из двух половин, что сразу откроет дорогу к боссу и финишу уровня. Также немаловажно, что у игрока есть возможность пройти уровень, почти не возвращаясь в уже посещённые комнаты, тем самым количество обязательного бэктрекинга минимально.

Вот другой пример.

Игрок может взять сокровище, взяв ключ 1 и пройдя через босса. Также можно обойти босса двумя способами — либо найдя секретный проход у старта (нужен ключ 1), либо найдя секретный проход внизу карты, причём там ключ не нужен. Как секреты, так и боссы опциональны.

Нерешённые проблемы

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

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

Во-первых, в генераторе пока ещё не реализована процедура преобразования графа комнат в тайловую карту. Хотя такая процедура не является частью циклической генерации как таковой, а играет роль скорее завершающего шага, в общем случае генератор для игр пока всё ещё не применим. Его пока можно использовать «как есть» только для игр с «покомнатным» геймплеем, а-ля тот же Binding of Isaac.

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

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

Заключение

Конечно, не всякая игра со случайными картами нуждается в по-настоящему интересных уровнях. Нередко геймплей строится вокруг элементов, не имеющих непосредственного отношения к окружению игрока — например, в серии Diablo не так важны карты, как важны шмотки, а в той же Binding of Isaac игра строится вокруг безумной комбинаторики подбираемых предметов, а не вокруг зельдо-подобного геймплея с уровнями-головоломками. 

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

Как бы то ни было, циклическая генерация вполне способна добавить глубины и разнообразия в любую игру, претендующую на жанр приключенческой, и помочь ей сделать ещё один шаг в сторону разрушения стереотипа «рогалики это однообразно». Давайте использовать её почаще?

Источники

1. https://habr.com/ru/articles/468957/

2. https://www.boristhebrave.com/2021/04/10/dungeon-generation-in-unexplored/

© Habrahabr.ru