Теория графов в геймдизайне

Граф как основа дизайна

Граф G (V, E) состоит из множества вершин V и множества рёбер E ⊆ V × V. Рёбра бывают ориентированными: однонаправленные дуги, как запертая дверь, открываемая только с одной стороны, или неориентированными: симметричные связи, как двусторонний коридор.

Вес ребра отражает стоимость, расстояние, уровень доверия или время. Сценарии применения:

• веса – стоимость перемещения, цена открытия, сила влияния, пропускная способность ресурсов
• узлы – комнаты, способности, квесты, фракции, ресурсы, состояния диалога
• рёбра – переходы, предусловия, отношения, торговые маршруты.

Формальное описание системы через граф делает механику проверяемой и пригодной для анализа.

Поиск пути

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

Четыре алгоритма, которые должен знать каждый геймдизайнер:

Таблица 1 – Алгоритмы поиска

A* (A-star) сегодня часто применяется в разработке игр. Алгоритм использует эвристику h(n), чаще всего расстояние до цели, и сокращает область поиска быстрее универсальных методов. Скорость A* зависит от структуры данных для открытого множества.

Приоритетная очередь даёт вставку и извлечение за O(log ⁡n), тогда как наивный список может ухудшить работу до O(n²)

Рис. 1 – Pac-Man: игровой процесс

Четыре призрака в Pac-Man используют разные модели преследования на графе лабиринта. Блинки (Shadow) движется прямо к игроку, Пинки (Speedy) выбирает цель на четыре тайла впереди, создавая ощущение скоординированного ИИ через простые правила навигации. GTA, PUBG и Minecraft применяют сходный класс алгоритмов для движения NPC и транспорта.

Деревья навыков

Рис. 2 – Дерево умений: ориентированный ациклический граф

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

Рис. 3 – Path of Exile: дерево навыков

Дерево навыков в Path of Exile – показательный случай. Граф содержит тысячи узлов и множество циклов, поэтому выходит за пределы строгого DAG. При этом зависимости отдельных умений можно описывать через ациклические подграфы требований. Недостижимый конечный узел при любой допустимой стартовой конфигурации означает тупик прогрессии, то есть баг.

Формально для DAG с n навыками число допустимых порядков открытия определяется количеством топологических сортировок. Такое комбинаторное пространство создаёт ощущение нелинейности в глубоких системах развития даже при относительно разреженной структуре.

Генерация подземелий

Рис. 4 – Граф подземелий: процедурная генерация

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

Рогалик Unexplored Йориса Дорманса (2017) использовал циклическую генерацию подземелий – подход на основе перезаписи графов, формально решающий проблему возвратов. Вместо выращивания дерева из стартового узла генератор начинает с цикла: двух разных путей, соединяющих вход с целью. Затем рекурсивно встраиваются подциклы.

Математическую основу составляет перезапись графов – операция поиска и замены, применяемая к топологии подземелья. Дорманс потратил несколько лет на реализацию в Unexplored. Циклическая генерация элегантна в теории, но сложна в инженерном воплощении.

Рис. 5 – Unexplored: игровой процесс

Для дизайнеров рогаликов и игр в стиле Metroidvania практический вывод носит архитектурный характер: система «ключ-замок» моделируется как ориентированный граф до формирования геометрии. Структура графа определяет движение игрока, визуальный слой накладывается поверх.

Нарративный дизайн

Рис. 6 – Граф сюжетных событий: нарративный дизайн

Ветвящийся нарратив порождает комбинаторную сложность. При n бинарных точках выбора возникает 2ⁿ уникальных сюжетных путей. Пять глав с одним бинарным выбором дают 32 истории, семь глав – 128. Писать, озвучивать и тестировать экспоненциально растущий контент практически невозможно. Теория графов предлагает решение – паттерн обратного схождения (foldback).

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

Mass Effect – хрестоматийный индустриальный пример. В первом акте более 20 выборов влияют на состав отряда, состояние отношений и распределение ресурсов в богато связанном нарративном графе. К третьему акту пути сходятся к одной финальной миссии, но разный пройденный подграф делает кульминацию личной.

Guerrilla Games формализовали этот паттерн в инструменте квестов для Horizon: Zero Dawn: квесты представлены как узлы ориентированного графа, рёбра кодируют временны́е и условные зависимости, анализ структуры автоматизирует проверку согласованности динамических диалогов.

Экономические системы

Рис. 7 – Граф экономических процессов: экономические системы

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

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

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

Системы фракций

Рис. 8 – Граф отношений между фракциями

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

w(A→C)=f(w(A→B), w(B→C))

где f транзитивно комбинирует веса и политическую логику «враг моего союзника – мой враг». Двумерная модель рёбер отражает реальную политическую динамику и создаёт более тонкие взаимодействия игрока с фракциями, чем бинарные флаги «друг/враг».

Введение независимых измерений рёбер привязанности и подозрительности открывает состояния фракций, невозможные в одномерной модели. Фракция может иметь отношение +5 и подозрительность +3, что означает готовность помочь при сохранении сомнений в мотивах игрока.

Заключение

Практическая ценность теории графов для геймдизайна заключается не только в отдельных алгоритмах, но и в подходе к проектированию игровых систем. Редактор квестов Horizon: Zero Dawn, планировщик навыков Path of Exile и генератор подземелий Ludoscope в Unexplored по сути представляют собой редакторы графов с предметно-ориентированным визуальным синтаксисом.

Определите узлы. Задайте семантику рёбер. Зафиксируйте инварианты: ацикличность, достижимость, границы минимального разреза. Примените математику. Ясность структуры, предсказуемость поведения системы и возможность формального анализа – главные преимущества графового подхода в геймдизайне.