Привет! Меня зовут Владимир Садовский и я трудоголик (вялые аплодисменты) работаю программистом инструментария в Nau Engine. А ещё — обожаю игры. С детства. Компьютер у меня появился, когда мне было восемь. Предполагалось, что для учебы, но на глаза мне попалась Carmageddon, и дальше всё как в тумане. Потом были Command & Conquer: Generals, Fallout 2, и, кажется, сотни других. Детское увлечение со временем превратилось в карьеру. 

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

Про GAI поговорим как-нибудь в другой раз (потому что эта огромная интересная тема тоже заслуживает отдельного материала), а сегодня разберёмся, с чем едят процедурную генерацию контента, и как не подавиться как она используется в игровой индустрии. А заодно немного окунёмся в историю PCG (а она почти вдвое старше меня), рассмотрим популярные инструменты и обсудим самые перспективные алгоритмы. 

Погнали!

В 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 и какие средства для этого используют.

В Unreal Engine для процедурной генерации предназначен специальный фреймворк PCG. Для расстановки произвольных объектов необходимо создать отдельный объект, а также запрограммировать блюпринт, который во время генерации будет работать в пределах заданной области.

Формально в Unity тоже есть свой инструмент для произвольной расстановки объектов, но изначально он был предназначен для работы с растительностью. О нём я ещё расскажу ниже.

В тёмных областях генерируются более высокие биомы с густой флорой (преимущественно древесной), а в светлых — низменности с редкой растительностью.

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

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

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

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

Как работает алгоритм на основе метода роста вместе в случае возникновения конкуренции?

Обычно алгоритмы на основе модели роста с конкуренцией функционируют следующим образом:

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

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

• Следом идёт этап размножения. Как только растения достигают возраста зрелости, они начинают распространять семена в той области, где находятся.
  
  

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

Эти шаги будут повторяться столько раз, сколько будет необходимо для симуляция массива растительности заданного возраста.

Обычно используют два метода конкуренции:

• Симметричный, когда конкуренция делится между двумя объектами генерации поровну. Это означает, что если растения имеют одинаковый размер, то они представляют равную угрозу друг для друга.
  
  

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

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

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

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

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

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, но позволяет точно настраивать распространение растительности на карте с помощью физических параметров.

Unreal Engine не имел встроенных инструментов для генерации городов до версии 5.3, где их стало можно имитировать с помощью PCG. Epic Games уже давно работает над этой проблемой. Генерация Нью-Йорка в демонстрационной игре The Matrix Awakens происходила на UE5 в несколько этапов. При этом часть работы была проделана в Houdini Engine, там же настраивался базовый вид города.

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

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

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

В Unreal Engine компонент Sky Atmosphere Component физически моделирует освещение скайбокса и проникновение лучей в соответствии с настройками атмосферы и тумана. Unigine в свою очередь отличается широкими возможностями для кастомизации объёмных облаков и множеством их реалистичных типов.

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

Иной способ сделать мир игры интереснее и правдоподобнее при помощи генерации — смоделировать его хронологию. Например, в начале партии в Dwarf Fortress мы попадаем не на пустую карту. До старта игры программа генерирует 100 лет ретроспективы: основание городов, войны, взлёты и падения целых империй. В итоге в распоряжении игрока оказывается уникальный живой мир, так и приглашающий его оставить собственный след в истории.

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

Генерация имени или предыстории персонажа встречается во многих RPG. Не меньше и генераторов типовых квестов, как, например, в Fallout 4 («Генерал, ещё одно поселение нуждается в вашей помощи!») или в Sea of Thieves (квесты на поиск сокровищ). Под такие алгоритмы обычно не разрабатывают специализированные инструменты. Они просто дополняют уже существующие игровые механики.

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

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

Благодаря тому, что этот алгоритм в чём-то схож с нейронными сетями (способен составить набор правил по заданному примеру), он всё шире распространяется в игровой индустрии.

Так, в The Matrix Awakens использовался специальный плагин для работы с WFC (его расширение на 3D-пространство), который уточнял геометрию зданий: добавлял мелкие детали, кондиционеры, пожарные лестницы, трубы и системы вентиляции на крышах.

Главное достоинство WFC является его же слабым местом. Без набора данных, который можно подать как пример для WFC, возникают проблемы написания правил генерации (а их может быть очень много) и составления ассетов, которые будет использовать генератор. Оскар Стольберг, создатель игр Bad North и Townscaper, говорил, что последняя использует несколько тысяч ассетов и несколько сотен правил генерации. В данном случае WFC применяется для уточнения геометрии зданий на нерегулярной сетке, где входным ограничением является ввод пользователя.

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

Словами языка называются все последовательности символов, порождаемые из начального состояния по правилам вывода.

 Различают два типа грамматик:

• порождающие;

• аналитические.

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

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

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

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

Формальные грамматики использовали, в частности, в уже упомянутой The Matrix Awakens. Там с их помощью задавался первоначальный визуальный стиль здания. В зависимости от входных ограничений (вроде длины стен) из определённого набора генерировалось слово. Каждому терминальному символу из слова соответствовал ассет, который заменял собой этот терминал при генерации уже 3D-объекта здания.

Ещё один хороший пример использования формальной грамматики — нормальные алгоритмы Маркова (НАМ).

Нормальный алгоритм Маркова представляет собой систему переписывания строк, которая использует некоторые правила для работы со строками символов. Доказано, что НАМ (в отличие от абстрактной формальной грамматики) являются полными по Тьюрингу, а значит, могут использоваться для общих вычислений и даже для моделирования математических выражений.

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

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

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

PCG позволяет, используя минимум ресурсов, создавать целые виртуальные миры. А это значит, что, несмотря на более чем сорокалетнюю историю и активную конкуренцию со стороны ИИ, процедурная генерация ещё долго не потеряет актуальности.