Процедурная генерация уровней в Distrust

Алгоритмы и правила.

Читатель DTF рассказал о том, как создать убедительные и локации с помощью процедурной генерации, на примере собственного проекта Distrust. Статья была опубликована в пользовательском разделе DTF и отредактирована.

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

Distrust задумывался как survival в условиях заброшенной полярной станции, где игроку предстоит управлять командой из нескольких человек. Изначальной идеей было то, что база генерируется процедурно, что это будет 2D в изометрии, а геймплей — это не только стандартный для жанра поиск ресурсов и поддержание статов персонажей, но и взаимодействие между персонажами: диалоги и наблюдения. Их цель— вычислить среди участников команды нечто, что является угрозой для остальных персонажей.

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

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

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

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

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

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

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

Поначалу лишь проницательный техлид подшучивал над геймдизайнером, дескать тот, настраивая всё это, занимается ничем иным как программированием, но когда в и без того огромном списке действий для персонажей появились if-then-else action, for-each-hero action, при том, что все действия могут быть с безграничной вложенностью, а пару из них даже с рекурсией, то смех сдержать было уже невозможно всем, особенно в те моменты, когда очередную особо изощрённую «таску» и её действия приходилось настраивать с привлечением программистов

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

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

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

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

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

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

Следующий этап — создание сущностей для реквизита. Что это такое? Сущность представляет собой абстракцию, которая хранит состояние объекта на сцене, позволяет как-то им манипулировать. Именно она отвечает за инстанцирование префаба на сцену, его настройку, переключение состояний, выполнение персонажами «тасок» на объекте, его сохранение и загрузку. Фактически всё взаимодействие с игровыми объектами на сцене осуществляется с помощью сущностей.

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

И последнее, что нужно знать для понимания работы генератора на этом этапе — это понятие «тэг комнаты» . По сути это просто перечисление, которое характеризует тип локации, например, кухня, спальня или котельная. В зависимости от типа комнаты в ней может оказаться реквизит лишь соответствующего типа: кровать не может быть на кухне, а холодильник — в котельной. Конфигурация реквизита также содержит список «тэгов комнат», в которых он может быть расположен для сопоставления. Полученные сущности мебели генератор распределяет в зависимости от тэга, и на выходе отдаёт словарь, в котором ключом выступает «тэг комнаты», а значением — реквизит, разделённый по трём спискам: loot, utility и scenery. Причём первые два представляют из себя готовые и настроенные сущности мебели, в то время, как третий список — это лишь конфигурации реквизита, который выступает в качестве декораций. Генератору требуется расставить сущности из первых двух списков, в то время, как третий — вспомогательный и нужен для более естественного заполнения комнат. Итак, теперь мы можем вкратце описать происходящее на данный момент:

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

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

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

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

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

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

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

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

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

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

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

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

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

Генератор изучает весь список реквизита, который уже поставлен в комнату, на предмет соблюдения соотношения мебели трёх типов. Так, например, после постановки холодильника в кухню, в ней имеется одна единица реквизита, и соотношение выглядит как 100% лутовых, 0% утилитарных, 0% декоративных, но в конфигурации шаблона кухни указано MaxLootablePercentage равен 0.5, то есть лишь 50% мебели в комнате должно быть лутовой, поэтому следующим на вставку окажется реквизит из списка утилитарных, он будет выбран случайно и пусть это будет печь.

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

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

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

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

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

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

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

Подводя итоги двух предыдущих этапов генерации:

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

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

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

Можно считать генерацию законченной. Все сущности базы созданы и находятся на своих местах. Далее в дело вступает плагин Dungeon Architect из Asstet Store, но поверьте, от его использования почти ничего не осталось. Алгоритмы, работающие с геометрией и теорией вероятности? получились всё же самописными. В нашем проекте Dungeon Architect занимается лишь расстановкой тайлов снега, стен, крыш, одним словом — рутиной.

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

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

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

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