...у рассмотренных инструментов есть общий недостаток. Их возможности по автоматическому размещению объектов, связанных в единую систему, сильно ограничены. Они могут автоматически расставить траву рядом с деревьями, или сгенерировать мусор рядом с мусорным баком, однако создать сложную структуру взаимосвязанных объектов, например, СИСТЕМУ ТРУБ, они не способны.
— Глеб, мой коллега по научно исследовательской работе
Привет, Хабр! Меня зовут Владимир Садовский и я трудоголик (вялые аплодисменты) работаю программистом инструментария в Nau Engine. А ещё — обожаю игры. С детства. Компьютер у меня появился, когда мне было восемь. Предполагалось, что для учебы, но на глаза мне попалась Carmageddon, и дальше всё как в тумане. Потом были Command & Conquer: Generals, Fallout 2, и, кажется, сотни других. Детское увлечение со временем превратилось в карьеру.
Увлекаться PCG я начал ещё в вузе (ИТМО). Тогда меня интересовало, как процедурная генерация контента помогает создавать игры с открытым миром и влияет на реиграбельность. Когда я стал игровым разработчиком, то заметил, что даже профессионалы часто путают процедурную генерацию и генеративный ИИ.
Про GAI поговорим как-нибудь в другой раз (потому что эта огромная интересная тема тоже заслуживает отдельного материала), а сегодня разберёмся, с чем едят процедурную генерацию контента, и как не подавиться как она используется в игровой индустрии. А заодно немного окунёмся в историю PCG (а она почти вдвое старше меня), рассмотрим популярные инструменты и обсудим самые перспективные алгоритмы.
Погнали!
Краткая история PCG
PCG-алгоритмы давно используют в геймдеве. Но изначально их применяли не для того, чтобы облегчить труд разработчика. Условия для развития PCG создали технические ограничения компьютеров конца 70-х — начала 80-х. По сути это был всего лишь один из способов оптимизировать хранение данных: процедурная генерация позволяла упаковать целые миры в несколько килобайт памяти. Не использовать её было просто невозможно.
Одной из первых игр, в основу которой легла PCG, стала Rogue. На первый взгляд всё было просто: почти бессюжетный данжен-кроулер, в котором всё окружение, монстры и предметы изображали текстовые символы. Зато каждое прохождение было уникальным, ведь все 26 уровней игрового подземелья с монстрами и сокровищами генерировались случайным образом. Так родился целый игровой жанр Rogue-like, элементы которого сегодня встречаются почти везде, от RPG до шутеров.
В 1984 году первая игра в серии Elite предложила нам нечто куда более масштабное. Здесь было восемь галактик по 256 планет в каждой — и все космические просторы умещались в 22 КБ магнитной ленты! При первом запуске игра запоминала некоторые начальное значение seed и после при каждом старте по этому значению восстанавливала галактики и небесные тела.
В 1994 году Arena, первая часть серии The Elder Scrolls, использовала PCG для создания целого фэнтезийного материка с тысячами NPC и сотнями населённых пунктов. Её продолжение The Elder Scrolls 2: Daggerfall до сих пор остаётся одной из самых больших игр с открытым миром: 161 600 км² площади, 15 000 городов и примерно 750 000 NPC. Да, мир был пустоват, квесты однообразны, а персонажи не то чтобы интересны… Но почти безграничная свобода искупала любые недостатки.
В том же 1996 году вышла Diablo. Конечно, она не могла похвастать масштабами Daggerfall, но её игровые уровни отличались завершенностью и отвечали метрикам геймдизайнера. Например, все они были проходимы, а некоторые объекты и фрагменты локаций, вроде логова Мясника или гробницы Леорика, располагались строго определенным образом. Если карта не отвечала заданным метрикам, то она генерировалась заново — до тех пор, пока все условия не выполнялись.
Но ещё более значимым наследием Diablo стала система генерации предметов. Сначала игра решала, выпадет ли предмет вообще. Потом — какого типа (лук, меч, броня и т.д.). Далее — магическим он будет или нет. Следом определялась его уникальность, характеристики, префикс и суффикс. Причём некоторые параметры попадались чаще других, а некоторые никогда не могли сочетаться.
На процедуру генерации влияла целая прорва переменных, начиная с уровня персонажа, заканчивая местом (город или подземелье) и источником (монстр или, скажем, сундук) появления вещи. В итоге под ноги героям падали тысячи уникальных предметов. Вдохновлённые Diablo разработчики до сих пор успешно пробуждают инстинкт собирателя в игроках, готовых набивать сотни часов в ARPG и лутер-шутерах в поисках новых случайно сгенерированных пушек поубойнее.
За 40 с лишним лет PCG прошла долгий путь от вынужденной меры преодоления платформенных ограничений до важного и нужного инструмента, избавляющего геймдизайнера от сотен часов рутинной работы. Сегодня процедурную генерацию используют для создания живых мегаполисов (Marvel’s Spider-Man), реалистичных лесов (Horizon Zero Dawn) и целых вселенных (No Man’s Sky). Ниже я покажу на конкретных примерах, что чаще всего создают при помощи PCG и какие средства для этого используют.
Произвольная расстановка объектов
При всей популярности PCG, не все игровые движки поддерживают даже базовые генеративные алгоритмы «из коробки». Так, например, Godot вообще лишён встроенных инструментов PCG (есть только несколько плагинов от сообщества), а Unity ограничен скромным набором самых необходимых генераторов. В то же время Unreal Engine 5 и Unigine обладают самыми богатыми возможностями для произвольной расстановки объектов.
Unigine позволяет размещать их следующим образом:
При помощи битовой маски. Этот метод нужен для массового заполнения объектами некоторой области. Он позволяет задать параметры частоты и рандомизации положения.
Посредством массивов координат. Этот инструмент используется для точечной расстановки объектов по координатам, которые можно получать из внешних источников, например из GeoJSON.
По сплайну. Обычно используется, когда нужно разместить контент вдоль линий: дорог, заборов или ЛЭП.
В Unreal Engine для процедурной генерации предназначен специальный фреймворк PCG. Для расстановки произвольных объектов необходимо создать отдельный объект, а также запрограммировать блюпринт, который во время генерации будет работать в пределах заданной области.
Формально в Unity тоже есть свой инструмент для произвольной расстановки объектов, но изначально он был предназначен для работы с растительностью. О нём я ещё расскажу ниже.
Алгоритмы для растительности
Инструменты для автоматической расстановки флоры появились в игровых движках одними из первых и сегодня встречаются в них чаще всего. Но общепринятой классификации таких алгоритмов не существует. Мне удобнее всего делить их на два класса по способу расстановки отдельных объектов генерации:
алгоритмы на основе распределения (в литературе их часто называют наивными);
алгоритмы на основе модели роста.
Алгоритмы на основе распределения не пытаются моделировать какие-то биологические процессы. Они используют математический аппарат, чтобы воссоздать массивы растительности, наиболее похожие на реальные.
Для этого можно воспользоваться тем или иным видом шума. В игровой индустрии наибольшее распространение получил шум Перлина, который, например, использовался для генерации биомов в Minecraft.
В тёмных областях генерируются более высокие биомы с густой флорой (преимущественно древесной), а в светлых — низменности с редкой растительностью.
Чтобы подсчитать плотность растительности, используют следующий метод. В некоторой выделенной области с помощью нормального распределения запускают процедурную генерацию. Далее подсчитывают расстояние от каждого из объектов генерации до его соседей. Если получившаяся плотность соответствует заданной, то генерацию оставляют неизменной. Иначе запускают процесс заново.
Неинтеллектуальные алгоритмы процедурной генерации растительности на основе распределения являются наиболее частой основой для создания инструментов для работы с флорой в игровых движках. Несмотря на то, что алгоритмы математически не моделируют реальные процессы роста растительности, они показывают хорошие результаты в кратчайшее время, что очень важно для игр с процедурной генерацией в рантайме.
Особенно ценно это свойство для разработчиков инструментов, которые должны быстро работать во время взаимодействия пользователя с движком. Например, всем нам привычная кисть, с помощью которой удобно расставлять растительность на ландшафте, чаще всего основана именно на алгоритме подсчёта плотности.
Алгоритмы на основе модели роста математически моделируют реальные биологические процессы. Обычно модель роста совмещают с одной из моделей конкуренции между растениями. Это позволяет точно располагать разновысотные растения одного типа. К примеру, мелкие кусты, которые стоят свободно, никак не будут влиять друг на друга. Но если рядом оказываются два больших дерева, то в результате работы алгоритма выживет лишь одно из них. Это позволяет создать более-менее обособленные области без растительности, так как не всем растениям хватит солнечного света или питательных веществ.
Как работает алгоритм на основе метода роста вместе в случае возникновения конкуренции?
Обычно алгоритмы на основе модели роста с конкуренцией функционируют следующим образом:
В начале работы алгоритма выбирается несколько точек, из которых начинается распространение растительности. Их можно расставить с помощью, например, случайного распределения или карты шума.
Далее следует этап роста. На каждой итерации математического моделирования дерево может стареть или расти. От возраста дерева зависит, с какой вероятностью оно умрёт, будет выбраковано из популяции и не сможет в дальнейшем участвовать в распространении семян.
Следом идёт этап размножения. Как только растения достигают возраста зрелости, они начинают распространять семена в той области, где находятся.
Заключительный этап самопрореживания добавляется в том случае, если дополнительно используются модели на основе конкуренции. Если деревья растут рядом, они начинают сражаться за жизненное пространство. Далее происходит отбраковка самого слабого из растений.
Эти шаги будут повторяться столько раз, сколько будет необходимо для симуляция массива растительности заданного возраста.
Обычно используют два метода конкуренции:
Симметричный, когда конкуренция делится между двумя объектами генерации поровну. Это означает, что если растения имеют одинаковый размер, то они представляют равную угрозу друг для друга.
Асимметричный, когда ресурсы распределяются между объектами генерации неравномерно. В зависимости от заданных параметров оценки, тот конкурент, который будет доминировать, получит больше ресурсов, а значит — больше шансов на выживание по сравнению с оппонентами.
Если в игровом движке используются алгоритмы на основе методов роста, то для моделирования конкуренции между растениями чаще всего выбирают симметричный метод, потому что его проще задать, чем ассиметричный. Тем более, что результаты на больших картах будут примерно одинаковыми.
Алгоритмы генерации на основе методов роста нечасто встречаются в игровых движках. Обычно они спрятаны в специализированных утилитах. Дело в том, что, в отличие от алгоритмов на основе распределения, они показывают куда более правдоподобные результаты в играх с видом сверху, а в других проектах не могут гарантировать заданную плотность посадки. Но на самом деле это не самая большая проблема.
Куда хуже то, что это грузные алгоритмы, которые работают продолжительное время. Следовательно, их нельзя использовать в играх, где важна генерация растительности «на лету». Кроме того, пользователь не сразу видит готовый результат. Надо дожидаться результатов генерации, и если что-то не так, то генерировать все заново. Поэтому генерацию на основе методов роста используют редко.
Теперь несколько слов о наиболее интересных инструментах из современных игровых движков.
Unity. Генератор деревьев Unity использует дополнительные ноды, которые отвечают за новые ветки или листья, а также за их формы.
Другой инструмент — Mass Place Trees — позволяет выращивать целые виртуальные леса одним щелчком мыши. Инструмент «кисть» даёт возможность настраивать вес каждого выбранного игрового ассета, регулировать их распределение и выбирать текстуру в подложке.
Ещё одна характерная особенность Unity — инструмент для расстановки импостеров деревьев. Импостер представляет собой совокупность 2D-текстуры и 3D-объекта (в виде двух перпендикулярных плоскостей, пересекающихся посредине), которые ортогональны камере и обычно используются при достаточном удалении от неё, чтобы оптимизировать нагрузку на компьютер при визуализации больших массивов растительности.
Unreal Engine тоже есть что предложить для работы с растительностью. Procedural Foliage Tool позволяет довольно точно в рамках определённой области генерировать список заданных сущностей с помощью настройки частоты спауна и модификаторов рандомизации положения. Отдельные коллайдеры позволяют вырезать области, где будет запрещён рост деревьев.
Кроме того, растительность в Unreal Engine можно расставлять с помощью кисти. Чаще всего такой подход используют для работы с травой. Наконец, с этой целью применяют вышеупомянутый Procedural Content Generation Framework.
В Unigine расстановка деревьев происходит так же, как генерация произвольных объектов.
Проприетарные движки тоже предлагают инструменты для работы с растительностью. Например, Dunia Engine, который использовали при разработке серии FarCry, позволяет размещать деревья (как и другие ассеты) с помощью кисти. Их особенность в том, что обычно они оперируют не каким-то набором однородных одиночных объектов, а сразу ставят целые массивы растительности: деревья с кустами и травой, которые взаимосвязаны друг с другом.
REDengine, на котором созданы игры серии The Witcher и Cyberpunk 2077, тоже содержит достаточно мощный инструмент для работы с растительностью. Он напоминает Procedural Foliage Tool из Unreal Engine, но позволяет точно настраивать распространение растительности на карте с помощью физических параметров.
Город-мечта
Генерация городов — ахиллесова пята всех представленных на рынке решений. Эта сложная задача требует учитывать множество параметров, чтобы город соответствовал ожиданиям игрока. Поэтому такие инструменты очень редко встречаются как в универсальных, так и в проприетарных движках.
В частности, Unity не имеет собственных решений для генерации городов. Впрочем, ряд сторонних разработок полностью покрывает потребности пользователей, от генерации целых районов до создания отдельных домов с внутренним убранством.
Unreal Engine не имел встроенных инструментов для генерации городов до версии 5.3, где их стало можно имитировать с помощью PCG. Epic Games уже давно работает над этой проблемой. Генерация Нью-Йорка в демонстрационной игре The Matrix Awakens происходила на UE5 в несколько этапов. При этом часть работы была проделана в Houdini Engine, там же настраивался базовый вид города.
Доступное пространство разбивалось на районы, а районы — на лоты. Дальше настраивалась высота района в зависимости от удалённости от центра, чтобы создать эффект небоскрёбов. Следом на основе средней высоты района и конкретного лота создавался объемный контур здания. На заключительном этапе вся эта информация передавалась уже дальше в движок с помощью специального плагина для работы с Houdini.
Генерация зданий тоже происходила в несколько этапов. На первом применялись формальные грамматики (о них — ниже). Их использовали для создания визуального стиля отдельных этажей. Потом с помощью плагина Unreal Engine для работы с WFC уточняли геометрию этих зданий: объекты на крышах, внешние инженерные системы и т.д.
Unigine — один из немногих движков с отдельным инструментом для генерации зданий. Здесь можно генерировать трёхмерные здания по заданным атрибутам в виде маски формы и координат, а также использовать геоданные из открытых источников, например из GeoJSON или OSM. Кроме того, Unigine позволяет генерировать городскую застройку по ряду параметров с выбором используемых материалов, настройкой высотности, формы крыш и т.д.
Своя атмосфера
Редкие движки способны полностью настраивать атмосферные явления без аддонов. Так, в Unity есть лишь базовый, неанимированный материал для скайбокса. А вот Unreal Engine и Unigine имеют схожие решения на основе объемных облаков.
В Unreal Engine компонент Sky Atmosphere Component физически моделирует освещение скайбокса и проникновение лучей в соответствии с настройками атмосферы и тумана. Unigine в свою очередь отличается широкими возможностями для кастомизации объёмных облаков и множеством их реалистичных типов.
Как пишется история
Ещё одно интересное направление в области генерации игрового контента — создание истории. Это может быть как хронология событий игры, которую формирует сам пользователь, так и история игрового мира до начала основного действия.
Разработчики нечасто пользуются такой возможностью, поэтому в универсальных движках нет специализированных инструментов для работы с генеративной историей. Да и не всякой игре нужен такой специфический инструмент.
Тем не менее такие системы способны стать настоящей визитной карточкой проекта. Значит, под них нужно готовить специализированный инструментарий на уровне движка в самой студии. Самый известный случай — LithTech Jupiter EX и LithTech Firebird, на которых созданы соответственно Middle-earth: Shadow of Mordor и Middle-earth: Shadow of War.
Запатентованная система Nemesis генерирует целую армию орков с индивидуальными особенностями и характеристиками. В начале они — однородная масса. Но потом враги начинают выстраивать определённые отношения с персонажем игрока. Как правило, в основе всего лежит ошибка пользователя: стоит герою умереть от меча орка, как тот будет повышен и обзаведётся собственными характеристиками, отражающими произошедшее событие. Это становится отправной точкой конфликта, личного не только для героя, но и для игрока.
При следующей встрече с героем «особенный» орк обязательно припомнит общее прошлое и попытается добавить новую главу в историю противостояния. Тут возможен целый ряд исходов, одни из которых способен контролировать игрок, а другие заботливо подкинет игра.
Чтобы мир выглядел ещё более динамичным, NPC начнут выстраивать отношения и друг с другом, заключать союзы или сражаться. В итоге ни одно прохождение не будет похоже на другое.
Иной способ сделать мир игры интереснее и правдоподобнее при помощи генерации — смоделировать его хронологию. Например, в начале партии в Dwarf Fortress мы попадаем не на пустую карту. До старта игры программа генерирует 100 лет ретроспективы: основание городов, войны, взлёты и падения целых империй. В итоге в распоряжении игрока оказывается уникальный живой мир, так и приглашающий его оставить собственный след в истории.
Если же рассматривать процедурную генерацию истории в более общем виде, не привязываясь к разработке специализированного инструмента игрового движка, то окажется, что это довольно частое явление.
Генерация имени или предыстории персонажа встречается во многих RPG. Не меньше и генераторов типовых квестов, как, например, в Fallout 4 («Генерал, ещё одно поселение нуждается в вашей помощи!») или в Sea of Thieves (квесты на поиск сокровищ). Под такие алгоритмы обычно не разрабатывают специализированные инструменты. Они просто дополняют уже существующие игровые механики.
Кастомные генераторы
Огромный прирост производительности при работе над игрой можно получить за счёт инструментов, позволяющих работать со структурами данных в виде графа. Небольшое число движков содержит готовые решения для создания сложных кастомных правил генерации.
В Unigine они отсутствуют. Здесь есть сложные готовые решения, скажем, для тех же зданий. Но при этом всё, что выходит за эти рамки, описывается с помощью простых настроек общих инструментов для генерации контента.
Unity за пределами базовых инструментов предоставляет сложные нодовые PCG редакторы только в платных плагинах, созданных сообществом.
Unreal Engine в этом плане ушёл далеко вперёд: у него есть несколько различных систем для работы со сложными правилами генерации. В рамках PCG есть широкая настройка правил через блюпринты, возможность определения типа поверхности, наклона и размера для спауна объектов.
Что ждёт нас в будущем
Напоследок немного расскажу про два алгоритма PCG, которые считаю наиболее перспективными.
Алгоритм WFC или Wave Function Collapse был вдохновлен понятием из квантовой механики, где объект может теоретически иметь много различных состояний, но под действием внешних факторов выбирается лишь одно из них.
WFC связан с распространением ограничений. Каждый следующий шаг уменьшает энтропию, то есть количество возможных выборов для данного конкретного шага. Действие алгоритма заканчивается в тот момент, когда из всего множества вариантов остаётся только один. Если изначальные ограничения не задавать, то вместо решателя для конкретной ситуации можно получить генератор определенного контента.
Благодаря тому, что этот алгоритм в чём-то схож с нейронными сетями (способен составить набор правил по заданному примеру), он всё шире распространяется в игровой индустрии.
Так, в The Matrix Awakens использовался специальный плагин для работы с WFC (его расширение на 3D-пространство), который уточнял геометрию зданий: добавлял мелкие детали, кондиционеры, пожарные лестницы, трубы и системы вентиляции на крышах.
Главное достоинство WFC является его же слабым местом. Без набора данных, который можно подать как пример для WFC, возникают проблемы написания правил генерации (а их может быть очень много) и составления ассетов, которые будет использовать генератор. Оскар Стольберг, создатель игр Bad North и Townscaper, говорил, что последняя использует несколько тысяч ассетов и несколько сотен правил генерации. В данном случае WFC применяется для уточнения геометрии зданий на нерегулярной сетке, где входным ограничением является ввод пользователя.
Другой перспективный подход к PCG — формальная грамматика. Это способ описания формального языка, алгоритм выделения некоторого подмножества из множество всех слов конечного алфавита.
Словами языка называются все последовательности символов, порождаемые из начального состояния по правилам вывода.
Различают два типа грамматик:
порождающие;
аналитические.
Порождающие грамматики наиболее интересны в контексте генерации игрового контента. О них я и хочу рассказать.
Чтобы задать порождающую грамматику, нужно задать алфавит терминальных и нетерминальных символов, правила вывода, а также начальное нетерминальное множество.
Под терминалами подразумевается какой-то символ, обозначающий, скажем, игровой ассет. Под нетерминальным символом понимается некоторая сущность языка, которая не имеет конкретного физического отображения, например формула, арифметическое выражение или команда.
Таким образом, из изначального нетерминального набора символов и правил вывода можно получить конкретное (терминальное) слово, которое будет соответствовать параметрам генерации. Это слово можно будет использовать в дальнейшем как начальное состояние другого генератора.
Формальные грамматики использовали, в частности, в уже упомянутой The Matrix Awakens. Там с их помощью задавался первоначальный визуальный стиль здания. В зависимости от входных ограничений (вроде длины стен) из определённого набора генерировалось слово. Каждому терминальному символу из слова соответствовал ассет, который заменял собой этот терминал при генерации уже 3D-объекта здания.
Ещё один хороший пример использования формальной грамматики — нормальные алгоритмы Маркова (НАМ).
Нормальный алгоритм Маркова представляет собой систему переписывания строк, которая использует некоторые правила для работы со строками символов. Доказано, что НАМ (в отличие от абстрактной формальной грамматики) являются полными по Тьюрингу, а значит, могут использоваться для общих вычислений и даже для моделирования математических выражений.
Алгоритмы Маркова уже давно известны и показали свою эффективность для моделирования случайных событий.
Алгоритмы процедурной генерации контента хорошо показывают себя в задачах, где нужно по определенному набору правил расставить заранее созданный контент.
В отличие от генеративного искусственного интеллекта, который я хочу рассмотреть в другом материале, алгоритмы PCG предоставляют всегда детерминированный результат от запуска к запуску при условии неизменности входных данных. Благодаря этому такие алгоритмы можно использовать в том числе в рантайме.
PCG позволяет, используя минимум ресурсов, создавать целые виртуальные миры. А это значит, что, несмотря на более чем сорокалетнюю историю и активную конкуренцию со стороны ИИ, процедурная генерация ещё долго не потеряет актуальности.
Полезные ссылки по теме PCG:
Генерация истории, и всё, что с ней связано:
Клеточные автоматы:
Полезное по теме PCG:
