Я много занимался деконструкцией инди-игры 2017 года Unexplored Джориса Дорманса. Она идеально воплощает идею процедурно генерируемых подземелий в стиле Zelda, и я обязан был выяснить, как происходит эта магия. К счастью, основная часть логики генерации написана на специализированном языке PhantomGrammar, поэтому с помощью разработчиков я получил достаточно полное представление о том, как она работает.

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

Графы

Графы — это понятие из компьютерных наук (никак не связанное с построением графиков). График содержит несколько узлов и соединяющих их рёбер. С их помощью очень удобно описывать связи между элементам. Я достаточно подробно описал графы в статье Lock and Key Dungeons.

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


Неориентированный граф с 5 узлами и 4 рёбрами

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

Преобразование графов

Преобразование графов (Graph Rewriting) очень похоже на текстовую замену — мы находим паттерн, соответствующий небольшому подмножеству всех данных, и подставляем паттерн, заменяющий только соответствующую часть. О том, что поиск и замена используются различными способами, я писал в своей статье о Diablo [перевод на Хабре], но там рассматривалась фиксированная сетка.


Пример из «Generating Missions and Spaces for Adaptable Play Experiences» Джориса Дорманса и Сандера Баккеса

На рисунке выше приведён пример правила замены.

Правило имеет левую и правую части. В левой части указано то, что нужно найти — в данном случае, оно ищет узел типа A, связанный с узлом типа B. Мы назовём их узлами 1 и 2.

В правой части находится то, чем нужно заменять. Узел 1 теперь превратился в узел типа a, а узел 2 превратился в узел типа A. Были созданы два новых узла, а рёбра переместились.

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


(1) показывает граф до того, как мы применили описанное выше правило.

(2) показывает соответствующий правилам паттерн поиска для части графа.

(3-6) демонстрируют изменение графа согласно паттерну замены.

(7) показывает граф после применения правила. Обратите внимание, что если бы мы применили правило повторно, то оно бы сопоставило только что созданные узлы A и B, и создало бы ещё более сложный граф.

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

Использование преобразования графов

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

В Enter the Gungeon [перевод на Хабре] используются некоторые правила замены графов, чтобы разнообразить содержимое подземелий. Но обычно паттерны поиска находятся только в одной комнате.

Dungeon Architect, популярный ассет Unity/Unreal для процедурной генерации подземелий, поддерживает сложные паттерны, но без петель.


Редактор правил Dungeon Architect

В своей статье «Generating Missions and Spaces for Adaptable Play Experiences» Дорманс и Баккес рассказывают, как простые правила, генерирующие и изменяющие порядок пар «замок-ключ», можно комбинировать для генерирования сложной структуры.


Правило, преобразующее линейную серию задач в разветвляющийся путь


Правило, вставляющее систему «замок и ключ»


Правило, перемещающее замок вперёд


Правило, перемещающее ключ назад

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

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