Всем привет! Меня зовут Максим, и я хочу рассказать о том, как мы делали процедурную генерацию, а точнее о том, какой она в итоге у нас получилась. Эта статья не претендует на звание полной документации, что потребовало бы намного больше текста. Статья ставит своей целью описать основные механизмы генерации игрового мира и его сущностей, не вдаваясь в отдельные узкие правила и исключения, коих довольно много.
Перед вами здание- склад, сгенерированное процедурно:
Об игре
«Distrust» задумывался как survival в условиях заброшенной полярной станции, где игроку предстоит управлять командой из нескольких человек. Изначальной идеей было то, что база генерируется процедурно, что это будет 2D в изометрии, а геймплей это не только стандартный для жанра поиск ресурсов и поддержание статов персонажей, но и различные взаимодействия между персонажами, диалоги и наблюдения, цель которых — вычислить среди участников команды нечто, которое является угрозой для остальных персонажей.
В процессе разработки мы пересмотрели часть идей, например, в силу того, что игровой мир по большей части скрыт во мраке и игроку приходится часто светить фонарём, свет и тени хотелось сделать особенно красивыми, и сделать это оказалось проще в 3D.
Это было сложное, интересное, полное совершенно разнообразных событий приключение, которое в данный момент подходит к своему логическому завершению: сейчас в Steam доступна бесплатная демоверсия игры, а полная версия выходит во второй половине августа.
Описание игрового мира
Игровой мир Distrust представляет собой полярную станцию или базу, которая состоит из нескольких зон. Зона представляет собой территорию, огороженную забором с одним переходом в следующую зону. Проход представляет собой запертую калитку, бронированную дверь, просто завал из снега и тому подобное. Чтобы открыть проход в следующую зону, игроку требуется выполнить определённый квест: расчистить сугроб трактором, собрать бомбу и взорвать дверь, подобрать код и прочее. Цель игрока — вывести персонажей с базы, пройдя все зоны с первой до последней и, соответственно, выполнив все квесты.
Зона состоит из зданий. Здания могут быть разных типов: госпиталь, склад, жилой блок и т.д. Внутри здания размечены на комнаты, которые также могут быть разных типов: кухни, лаборатории, котельные, спальни и другие. Каждый тип комнаты выглядит по- своему и может быть обставлен определённым реквизитом.
Геймплей заключается в выполнении разных задач героями команды под управлением игрока. Задачи — это 70% геймплея игры. Они могут быть совершенно разнообразными — начиная с лутания тумбочки и заканчивая жертвоприношением, но по сути всё это одна и та же сущность — таска, как мы её называем, разница лишь в конфигурации. Нетрудно догадаться, что тасок в нашей игре огромное количество, и функционал, который они предоставляют, огромен!
Основная смысловая нагрузка всех тасок — это действия, которые применяются к персонажам в процессе выполнения таски. Эти действия могут быть выполнены перед стартом таски, в процессе с определённой периодичностью или же по завершении таски. На картинке изображены действия по окончании весьма изощрённой таски. Действия или экшены, как мы их называем, меняют статы персонажам, добавляют или снимают эффекты и вообще представляют из себя очень многочисленные сущности, которые служат инструментом настройки игры для геймдизайнера, и совершенно внезапно для нас они превратились в визуальный язык программирования! Поначалу лишь проницательный техлид подшучивал над геймдизайнером, дескать тот, настраивая всё это, занимается не чем иным как программированием, но когда в и без того огромном списке действий для персонажей появились if-then-else action, for each hero action, при том, что все действия могут быть с безграничной вложенностью, а пару из них даже с рекурсией, то смех сдержать было уже невозможно всем, особенно в те моменты, когда очередную особо изощрённую таску и её экшены приходилось настраивать всем миром с привлечением программистов.
Реквизит
Прежде чем мы поняли какую именно генерацию мы хотим видеть в игре, какие принципы должны лежать в её основе, чтобы получить игровой мир, которого мы добивались, мы пробовали разные варианты, что- то добавляли, что- то переделывали и конфигурировали заново и, лишь получив определённый опыт и набив некоторые шишки, мы нашли решение, которое позволило нам процедурно создавать такие миры, в которые будет интересно играть.
В итоге мы остановились на следующем варианте: каждая зона генерируется таким образом, чтобы вместить в себя заранее сконфигурированный бюджет, и начинается с самой малой сущности генерации — итемов лута. Лут — это какие- то предметы, которые игрок может увидеть в инвентаре и с его помощью манипулировать ими. Примерами таких предметов могут служить: конфеты, бинты, аптечки, отмычки и тому подобное. Получить лут в игре можно, лишь выполнив определённые таски.
Основная часть бюджета каждой зоны — лут и список реквизита, который может быть использован при генерации. Под реквизитом мы понимаем объекты игрового мира, с которыми так или иначе взаимодействуют персонажи. Это могут быть тумбочки, кровати, электрогенераторы, печи, шкафы и так далее. Реквизит при генерации мы разделяем на три группы:
Scenery — не несут никакой функциональной нагрузки и служат для того, чтобы комнаты выглядели естественно и разнообразно — это стулья, ящики, трубы и т. п.
Loot — призваны разместить в себе лут — это шкафы, тумбочки, складские полки и т. п.
Utility — всегда несут на себе определённую функциональную нагрузку и необходимы персонажам для выживания — это кровати, печи, плиты и т.п.
Бюджет зоны состоит из списков лута, реквизита, дверей и прочих списков
В бюджете лута для каждого итема указаны таски, в которых он может оказаться, сколько итемов выдаёт конкретная таска и сколько итемов в зоне должно быть
Итак, процедурный генератор начинает свою работу с подготовки бюджета лута. На этом этапе входными данными является конфигурация бюджета лута для всей зоны, который необходимо как-то распределить. Как уже было упомянуто выше, лишь определённая таска может выдать определённый лут, например, таска «полутать овощи» выдаст вам пакет замороженных овощей, а таска «полутать отмычки» выдаст вам отмычки. При этом таска «полутать овощи» не может появиться на тумбочке, только на холодильнике.
Исходя из этих двух постулатов приходим к выводу, что генератор должен сформировать список тасок, с помощью которых персонажи смогут собрать весь лут. Делать он это должен на основании предоставленного бюджета, то есть так, чтобы замороженные овощи оказались в холодильнике, патроны — в шкафчике для оружия и так далее, а эта мебель была бы доступна для конкретной зоны, исходя из настроек самой зоны. Генератор устанавливает эти соответствия, просматривая список лутового реквизита бюджета, в этом списке хранятся конфигурации каждого отдельно взятого реквизита, в нём указывается ссылка на префаб, список состояний, перечислены таски, которые поддерживает данный реквизит и некоторые другие свойства.
Таким образом, сопоставляя бюджеты лута и реквизита, доступного для зоны, генератор формирует список лута, на его основе формирует множество тасок, выбирая их из тех, что указаны в каком- либо реквизите из бюджета для данной зоны, и наполняет конкретные таски в зависимости от типа определённым лутом. Например, для зоны необходимо распределить три аптечки, таска «выдать аптечку» может выдать лишь одну аптечку, значит в зоне нужно распределить три таких таски.
Следующим этапом выступает создание сущностей для реквизита. Что это такое? Сущность представляет собой абстракцию, которая хранит состояние объекта на сцене, позволяет как-то манипулировать им, именно она отвечает за инстанцирование префаба на сцену, его настройку, переключение его состояний, выполнение персонажами тасок на объекте, его сохранение и загрузку. Фактически всё взаимодействие с игровыми объектами на сцене осуществляется с помощью сущностей. Входными параметрами на данном этапе служит список лутовых тасок с прошлого этапа и тот же бюджет реквизита, но уже не только лутового, но и функционального, который мы называем утилитарным. В случае с лутовым реквизитом генератор сперва создаёт сущности таким образом, чтобы вместить в них все лутовые таски, например, чтобы распределить те же три аптечки, генератор выбирает из бюджета реквизита тот, который поддерживает таски «выдать аптечку», например лабораторный стол или медицинский шкафчик. А утилитарный реквизит создаётся напрямую исходя из конфигурации, в которой описано, какие объекты и в каком количестве может быть в зоне. Например, в зоне может быть от пяти до семи электрогенераторов, от трёх до пяти кроватей и так далее.
И последнее, что нужно знать для понимания работы генератора на этом этапе — это понятие «тэг комнаты». По сути это просто перечисление, которое характеризует тип комнаты, например, кухня, спальня, котельная и так далее. В зависимости от типа комнаты в ней может оказаться реквизит лишь соответствующего типа, кровать не может оказаться на кухне, а холодильник — в котельной. Конфигурация реквизита также содержит список тэгов комнат, в которых он может быть расположен для сопоставления. Полученные сущности мебели генератор распределяет в зависимости от тэга, и на выходе отдаёт словарь, в котором ключом выступает тэг комнаты, а значением является реквизит, разделённый по трём спискам: loot, utility и scenery. Причём первые два представляют из себя готовые и настроенные сущности мебели, в то время, как третий список — это лишь конфигурации реквизита, который выступает в качестве декораций. Генератору требуется расставить сущности из первых двух списков, в то время, как третий — вспомогательный и нужен для более естественного заполнения комнат. Итак, теперь мы можем вкратце описать происходящее на данный момент:
На основании тасок, выдающих лут, подготовленных на одном из шагов, и конфигурации реквизита, а также тэгов комнат, генератор создаёт словарь, в котором для каждого типа комнаты имеется два списка, которые необходимо расположить где- либо в зоне, плюс один вспомогательный, из которого генератор будет создавать новые сущности налету по необходимости.
Для более ясного понимания уточню, что по завершении описанного этапа игровые сущности определённой зоны уже созданы, подготовлены таски и в них содержится необходимый игроку лут. Очертания зоны пусть не геометрически, но геймплейно уже прослеживаются.
Здания и комнаты
Взяв словарь из предыдущего этапа, генератор последовательно расставляет реквизит из лутового и утилитарного списка. Но, спросите вы, в мире ведь ещё нет ничего кроме сущностей самой этой мебели? Куда можно её расставить? Генератор может поставить мебель лишь в какую-нибудь комнату. Комнаты могут быть лишь в каком-нибудь здании и поэтому, если существуют какие-либо здания, то они исследуются на предмет такой комнаты, что сможет принять нужную мебель, причём, эта комната должна быть не заполнена полностью. Разумеется всё, что касается комнат, также конфигурируется из редактора. Мы называем конфигурации комнат шаблонами комнат.
В этих шаблонах отмечен тэг комнаты, общая площадь наполненности комнаты — Filled Space, на основании которой генератор считает комнату заполненной или нет, и соотношения реквизита трёх типов в комнате, с помощью которых генератору удаётся равномерно и естественным образом обставить комнату. Каждая зона имеет список шаблонов комнат, которые могут появиться в её зданиях. Итак, возвращаясь к созданию комнат и зданий. Проще всего описать этот механизм как ленивый, то есть, пока есть незаполненная комната нужного типа, она будет заполняться реквизитом таким образом, чтобы соблюсти отношение между функциональным, лутовым и декоративным согласно шаблону комнаты. Как только нужной комнаты не окажется, генератор попробует создать ещё одну такую комнату в одном из зданий, причём заполнение зданий комнатами также подчинено многочисленным правилам. Так, например, склады не бывают в одном здании с лабораторией, в одном здании не может быть больше двух котельных и так далее. Если и это не удаётся, и ни одно из существующих зданий не готово принять новую комнату, то создаётся новое здание. Происходит это следующим образом.
Генерация форм
Пришла пора познакомить вас с геометрическим сердцем нашей генерации. Именно оно ответственно за корректное размещение реквизита внутри комнат, создание комнат внутри зданий, зданий внутри зон и зон внутри целой базы. Генератор форм отвечает за то, чтобы игровые объекты впоследствии не врезались друг в друга, здания стояли на определённом расстоянии друг от друга, за генерацию форм комнат и зданий и тому подобные вещи.
Форма — это сущность, в основе которой лежит список квадратов, каждый из которых представлен списком точек. С помощью форм генератор фактически делает разметку игрового мира, по которой в последующих этапах будут расставлены все игровые объекты на сцене — будь то префабы реквизита, стены зданий или забор вокруг зон. Но обо всём по порядку.
На предыдущем этапе мы остановились на том, что генератор вынужден внутри зоны создать новое здание, в котором он сможет создать такую комнату, в которую разместит нужный реквизит. Создание зданий начинается с выбора заготовки, которая представляет собой небольшую картинку в .png. Картинка превращается в то, что мы понимаем под формой — список квадратов и точек — с помощью алгоритма, который, кстати, наш коллега нашёл на просторах Хабра.
На картинке изображена заготовка формы здания, увеличенная в пять раз
Алгоритм строит комнаты в белой области картинки и строить их он начинает с точек, отмеченных зелёным. Оригинальная реализация обходится без этих точек, но для большей управляемости разбиением здания на комнаты мы модифицировали алгоритм
Этот алгоритм попиксельно исследует картинку, формируя форму здания в виде списка точек и разбивает её на прямоугольники, на основании которых затем формируются комнаты. То есть, получив на вход специальную картинку, алгоритм возвращает форму здания и формы комнат внутри него. Далее в доме строится маршрут между комнатами, подбираются позиции дверей внутри здания и позиция входной двери в здание. Помимо формы для здания сразу создаётся его сущность, которая будет контролировать комнаты внутри, а одна из только что размеченных в нём комнат объявляется комнатой нужного генератору типа, в зависимости от выставляемого реквизита, и для неё создаётся сущность. Например, если генератору пришлось сгенерировать новое здание в процессе размещения холодильника, то одна из комнат в новом здании будет объявлена кухней, так как тэг комнаты для холодильника — это кухня, и в силу того, что она пустая, холодильник явно будет в неё поставлен и удалён из списка лутового реквизита.
Чтобы поставить мебель в комнату, генератор форм пробует выбрать случайную точку внутри комнаты таким образом, чтобы при создании игрового объекта холодильник оказался на нужном расстоянии от стен. Регулируется это также его конфигурацией, как и то, какая площадь ему нужна, но об этом ниже. Помимо холодильника комната будет обставлена и прочим реквизитом, подходящим по тэгу комнате, в данном случае кухне. Причём процесс размещения этого реквизита выглядит следующим образом.
Генератор изучает весь список реквизита, который уже поставлен в комнату, на предмет соблюдения соотношения мебели трёх типов. Так, например, после постановки холодильника в кухню в ней имеется одна единица реквизита, и соотношение выглядит как 100% лутовых, 0% утилитарных, 0% декоративных, но в конфигурации шаблона кухни указано MaxLootablePercentage равен 0.5, то есть лишь 50% мебели в комнате должно быть лутовой, поэтому следующим на вставку окажется реквизит из списка утилитарных, он будет выбран случайно и пусть это будет печь. Чтобы поставить печь, генератор также выбирает случайную точку так, чтобы та не угодила в стену, но помимо этого генератору нельзя допустить, чтобы печка оказалась в холодильнике! Для этой цели мы используем встроенное решение от Unity — коллайдеры.
У каждого префаба реквизита настроены коллайдеры, которые характеризуют, во-первых, саму площадь, занимаемую им, это та площадь, по которой персонажи не смогут ходить, иными словами, это площадь самого игрового объекта, его родной коллайдер, а во- вторых, один дополнительный коллайдер, шире «родного», который мы называем ковриком. Предназначение этого коврика — обеспечить доступность реквизита для персонажей. Персонажи могут выполнять таски на реквизите лишь из определённых точек и, нетрудно догадаться, они должны быть доступны и не могут быть заставлены другой мебелью, что сделало бы их недосягаемыми. При расстановке мебели генератор проверяет, что собственные коллайдеры мебели не пересекаются с собственными коллайдерами и ковриками другой мебели, в то время как коврики могут пересекаться между собой, но не с собственными коллайдерами других предметов. Такая схема позволяет избежать пересечения объектов мебели друг с другом, а также обеспечивает доступность интерактивных точек для персонажей игры.
Генератору на эту процедуру отводится определённое количество попыток, дабы избежать зацикливания. Если за указанное число попыток генератор не смог разместить печь, то пробует поставить другой объект, пока не попробует всё из двух доступных списков — утилитарного и сценарного (так как в кухне на данный момент есть лутовая мебель, но нет других типов) с целью соблюсти отмеченное выше соотношение. В случае если вставить больше реквизита не удаётся, или площадь комнаты заполнена на значение Filled Space, то комната считается заполненной. На этом этапе участвует множество и других правил, описание которых навевает мысли об Икее, — среди них то, должна ли мебель стоять вплотную к стене или наоборот на расстоянии, прикроватная тумбочка ставится рядом с кроватью и многое, многое другое, не столь важное в этом описании, однако, одно правило всё же стоить отметить, без него комнаты выглядели как шахматное поле — каждая единица реквизита немного вращается генератором на случайный угол, диапазон значений которого также указан в конфигурации. Эта мелочь оказалась действительно важной и сделала комнаты намного более естественным и живыми.
Эта картинка отлично иллюстрирует работу генератора: пустые прямоугольники, обведённые по контуру — коллайдеры — визуализация того, как генератор пробовал расставить определённые предметы в процессе генерации. Закрашенные прямоугольники красного, жёлтого и зелёного цвета — это коллайдеры утилитарного, лутового и сценарного реквизита соответственно. Над лутовым реквизитом также отображается лут, который в нём лежит, например, доски, бинты, изолента и прочее.
Подводя итоги двух предыдущих этапов генерации:
Генератор расставляет в зоне реквизит, по необходимости создавая новые здания и размечая комнаты в них по форме и типу и создавая сущности к ним, таким образом, чтобы все комнаты были обставлены согласно заданным пропорциям реквизита трёх типов и многим другим правилам генерации, не столь важным для понимания общей сути.
Заключительный этап
С предыдущего этапа генерации мы имеем фактически готовый игровой мир. На сцене пока что нет игровых объектов, но достаточно вызвать один метод каждой из созданных сущностей, как он появится! Но прежде генератор осуществляет ещё одну важную процедуру — определяет позиции зданий внутри зоны. До сих пор каждое новое здание находилось в точке ноль ноль и нас не волновало, что их там может быть несколько. Генератор случайным образом выбирает направление куда двигать здание от нулевой позиции и смещает его вместе со всем содержимым с заданным шагом до тех пор, пока форма здания не перестанет пересекаться со всеми остальными формами зданий и расстояние до всех других зданий не станет больше либо равным, указанному в конфигурации. Проделав эту процедуру, генератор на основании положения зданий определяет форму зоны. По контуру этой формы будет построен забор, а также форма зоны будет учавствовать в аналогичном зданиям процессе «раздвигания», только с другими зонами. После генерации всех зон внутри базы, они также находятся в позиции 0:0 и раздвигаются друг от друга таким образом, чтобы избежать пересечения, но сохранить при этом общую сторону, в которой будет построена калитка.
Можно считать генерацию законченной по завершении описанного этапа. Все сущности базы созданы и находятся на своих местах. Далее в дело вступает небезызвестный плагинчик из Asset Store под названием Dungeon Architect, но, поверьте, от его использования почти ничего не осталось. Алгоритмы, работающие с геометрией и теорией вероятности получились всё же самописными, а не из плагинов. В нашем проекте Dungeon Architect занимается лишь расстановкой тайлов снега, стен, крыш, одним словом рутиной. Немного труда стоило бы нам отказаться от него вовсе, но поначалу казалось, что он решит все наши проблемы и сделать генерацию с ним будет просто, а желания и времени выпилить его полностью просто не было. Занимается он уже непосредственным интсанцированием объектов и префабов на сцену.
Ещё немного генерации:
Набросок плана генерации улицы
Внутри зон, помимо зданий, также генерируется реквизит на улице, освещение разного типа и тропинки, причём тропинки генерируются с помощью каноничной реализации алгоритма Ли буквально так, как он описан в Википедии
Вместо послесловия
Процедурная генерация оказалась совершенно нетривиальной задачей. В процессе работы мы иногда ловили себя на мысли кардинально упростить сценарий, например, отказаться от генерации комнат, а лишь расставлять заранее готовые.
Но после того, как мы набрались опыта и перепробовав разные варианты и подходы, нам удалось сделать генерацию именно такой, как мы и хотели. Всей командой мы провели огромное количество времени в обсуждениях, чтобы сделать процедурную генерацию нашей полярной базы технически возможной, настраиваемой и красивой. Признаться, мы нередко заворожённо рассматриваем получившиеся комнаты и то, как они обставлены, действительно живо и логично — если это раздевалка, то у одной стенки шкаф, напротив лавочка, а в стороне вешалки. С гордостью хочется сказать, что, хоть это было нелегко, да чего уж там — кровопролитно и зубодробительно, но результатом я очень доволен и могу заявить, что мир в нашей игре действительно генерируется процедурно, это не пара деревьев, которые появляются в разных концах карты или случайные тайлы снега. Это действительно генерируемый мир, основанный на всевозможных алгоритмах, построенных на законах теории вероятности, нормального распределения и геометрии.
Автор: Moximko
