[Перевод] Как генерируются подземелья в Enter The Gungeon06.08.2019 16:19

В последнее время я много играл в Enter The Gungeon. Это потрясающая, ужасно сложная игра в жанре bullet hell, сильно напомнившая мне Binding of Isaac. Но чем больше я играл в неё, тем больше осознавал малозаметную гениальность дизайна подземелий.

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

Поэтому я, естественно, запустил декомпилятор, чтобы Gungeon раскрыла мне все свои секреты. В этой статье я поделюсь с вами тем, что мне удалось найти.

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

Карта типичного уровня 1

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

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

Особенность генератора становится заметной, когда вы начинаете играть. Уровни кажутся… чуть более спланированными, чем можно ожидать от случайности. Комната с боссом всегда находится на разумном расстоянии от начала. Комнаты с врагами всегда разумно перемежаются спокойными комнатами, лавками и перекрёстками. И самое важное — многие сундуки расположены за петлями с односторонней проходимостью.

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

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

Обычные комнаты (Normal room) — это случайно выбираемые комнаты с врагами, комнаты-перекрёстки или большие комнаты с несколькими выходами. Награды (Reward) и босса (boss) объяснять не нужно. Здесь не показаны «соединительные» комнаты, то есть комнаты без врагов, часто с природными опасностями. Остальные комнаты или задаются заранее, или выбираются из особой таблицы комнат.

В Gungeon существует довольно мало таких схем, называемых «потоками» (flow). На уровнях Hollow их меньше всех (всего 4), а в Gungeon Proper — больше всех (8). Это не простые схемы, их дизайн создан на основе определённой особенности, которую можно заметить при многократном прохождении. Это может быть гигантская петля, или важная развилка из множества путей, или необходимость добраться до лавки, чтобы пройти уровень. Они настолько заметны, что спидраннеры заметили различия и составили графики, по которым можно максимально быстро найти босса. Я подготовил полный список схем, который можно скачать отсюда.

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

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

Преобразование потока

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

Затем «инъектируются» ещё несколько дополнительных узлов. Эта функция довольно гибка и используется для множества разных целей.

Каждая «инъекция» содержит данные, определяющие, какой тип объекта должен быть вставлен, где он должен быть вставлен, вероятность создания и любые условия, которые должны быть выполнены (например, наличие master round, высокого curse или то, что игрок пока не спас персонажа). Например, секретные комнаты обычно создаются в тупиках, но имеют вероятность 1/5 быть присоединёнными к любой комнате. Они имеют вероятность появления 90% и не требуют никаких дополнительных условий.

Почти каждая специальная комната в игре определяется инъекцией узла, в том числе и торговцы (не включая основную лавку), тюрьмы, комнаты с каминами и лифтами.

Одна из тюремных камер, которая может быть инъектирована в уровень

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

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

Составные объекты

После завершения создания потока он разбивается на «составные объекты». Каждый составной объект — это или отдельная петля из комнат, или набор связанных комнат без петель (т.е. дерево). Это реализуется поиском наименьшей петли на карте и вырезанием её как составного объекта. Операция повторяется, пока на карте не останется петель. Остальная часть карты становится набором разделённых деревьев и соединениями между отдельными составными объектами.

Тот же самый поток после инъектирования и разделения на составные объекты

Схема составных объектов

Затем каждый составной объект создаётся по отдельности, на отдельной карте. Соединены вместе они будут позже.

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

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

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

Окончательная сборка

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

Та же самая карта в виде составных объектов перед окончательной сборкой

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

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

В заключение

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

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

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

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

Бонусы

Изучение этого генератора стало моим первым шансом на исследование создания профессиональной игры в Unity. Разработчики из Dodge Roll постарались и написали хороший код. Он хорошо читаем, а в некоторых местах довольно забавен — похоже, их любовь к каламбурам распространилась и на код. Мне понравились вот такие:

Движок жидкостей в игре называется DeadlyDeadlyGoopManager
Код генерации подземелий называется Dungeonator
Различные этапы называются CASTLEGEON/GUNGEON/MINEGEON/CATACOMBGEON и т.д. Интересно, вдохновлялись ли разработчики Diablo 1, в которой используется очень похожая схема?
Буквально каждая комната имеет своё название, обычно в виде каламбура (или в честь какого-то Джо; вероятно, это художник с большим самомнением).

Также я заметил, что изначально у студии были планы на этапы в тематике космоса, джунглей и Дикого Запада. Увы, им не суждено было появиться. Dodge Roll решила, что её работа над Gungeonзавершена. Я буду ждать их следующую игру и надеюсь, что они вложат в неё столько же любви и внимания.