Пройди свой путь в ширину: библиотеки для графов из инди-игры TESTAMENT

Знаете, почему математики не любят направленные нецикличные графы? Потому что если они совершать ошибку, они не смогут вернуться.

С чего все началось

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

Когда я начал работать над своим пет-проектом TESTAMENT, мне нужно было генерировать и отображать произвольные графы. Я хотел, чтобы локации были в виде простых шагов-событий, соединенных между собой. Примерами могут послужить проекты Slay The Spire, Cult of the Lamb, Darkest Dungeon и другие. Исследовав вопрос, я увидел, что существующие библиотеки слишком тяжелые и сложные для моих нужд.

• QuickGraph — развитая библиотека, которая активно используется в промышленных системах. Наверное, самым мастодонт среди всех библиотек, которые я знаю.

• GraphShape — форк и последующая переработка заброшенного GraphSharp. Куча алгоритмов раскладки. И скупая документация, кажется, для галочки.

• Microsoft Automatic Graph Layout — мощное решение от лидера рынка корпоративных решений.

• YWorks — красивое коммерческое решение.

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

Какими будут мои графы:

1. Графы направленные. По сути — деревья.

2. Графы нецикличные.

3. Может быть несколько стартовых узлов.

4. Предполагается один финишный узел.

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

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

7. Все узлы одинакового размера.

8. Подойдет вариант визуализации, когда граф просто вытянут в линию. Возможно даже, такой вариант наиболее предпочтителен. Чтобы игрок проходил от начала (слева) до конца (направо).

При генерации:

1. Всегда должно быть несколько стартовых улов.

2. В определенный момент несколько узлов графа должны входить в один узел.

3. В определенный момент один узел должен разветвляться на строго определенное количество узлов.

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

Минимальные графы

Моя библиотека https://github.com/kreghek/CombatDicesTeam.Graphs предоставляет единственный интерфейс для работы с графами IGraph<TNodePayload>, где TNodePayload — любой тип данных, которые будут содержать узлы графа. Интерфейс графа, на самом деле, одноклеточный:

• AddNode — добавляет узел в граф.

• ConnectNodes — соединяет два узла ребром.

• GetAllNodes — возвращает все узлы графа.

• GetNext — возвращает узлы, соединенные с указанным узлом.

Самая простая и наивная реализация для ориентированных графов — DirectedGraph.

Пример использования. Введем свой тип данных. У меня в игре это, например, граф локаций. Локации можно описать примерно так.

interface ILocationFactory {     // Какие-то методы предоставления информации о локации     // и конструирования игровых объектов. } ///<summary> /// В этой локации будет сражение героев с монстрами. ///</summary> sealed class CombatLocationFactory: ILocationFactory { } ///<summary> /// В этой локации с героями произойдет случайное событие. ///</summary> sealed class EventLocationFactory: ILocationFactory { } ///<summary> /// В этой локации герои смогут восстановиться. ///</summary> sealed class RestLocationFactory: ILocationFactory { } ///<summary> /// Это конечная локация с наградой. ///</summary> sealed class RewardLocationFactory: ILocationFactory { }

Создадим простой нецикличный граф вроде такого. Игрок должен начать бой. Затем у него есть выбор — легкий или сложный путь. И награда в конце.

// 1. Создаем объект графа. var graph = new DirectedGraph<ILocationFactory>(); // 2. Создаем узлы графа var combatNode = new GraphNode<ILocationFactory>(new CombatLocationFactory()); graph.AddNode(combatNode); var restNode = new GraphNode<ILocationFactory>(new RestLocationFactory()); graph.AddNode(restNode); var eventNode = new GraphNode<ILocationFactory>(new EventLocationFactory()); graph.AddNode(eventNode); var extraCombatNode = new GraphNode<ILocationFactory>(new CombatLocationFactory()); graph.AddNode(extraCombatNode); var rewardNode = new GraphNode<ILocationFactory>(new RewardLocationFactory()); graph.AddNode(rewardNode); // 3. Соединяем узлы графа ребрами. // Легкий путь к спасению. graph.ConnectNodes(combatNode, restNode); graph.ConnectNodes(restNode, rewardNode); // Путь железного человека ради славы и опыта. graph.ConnectNodes(combatNode, eventNode); graph.ConnectNodes(eventNode, extraCombatNode); graph.ConnectNodes(extraCombatNode, rewardNode);

Раскладка графа

Алгоритм

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

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

BFS (Breadth First Search) — выполняет обход поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже

Получается массив массивов.

Далее нам нужно выдать координаты каждому узлу. Для получения x-координаты просто перемножаем уровень на ширину узла. Для получения y-координаты нам нужно индекс узла умножить на высоту узла. А так же нужно выровнять узел по центру по высоте.

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

Но тут есть нюанс. По контракту, граф не гарантирует порядок соседних узлов в методе GetNext().

Для того, чтобы «сгладить» эту проблему, выполним следующую доработку:

1. Назначаем вес корневым узлам. Вес назначается по порядку.

2. Для каждого соседнего узла считаем вес, как среднее всех весов узлов, которые входят.

3. Упорядочиваем узлы по весу в рамках одного уровня.

4. Рекурсивно повторяем для всех уровней.

Весь алгоритм в UML:

Реализация

Библиотека https://github.com/kreghek/CombatDicesTeam.Graphs.Layout содержит реализацию этого алгоритма. Разберем, как раскатать этот граф в плоскости.

// 1. Создаем визуализатор. Будет работать с графами целых чисел. // Этот визуализатор раскладывает граф слева-направо в одну линию. var visualizer = new HorizontalGraphVisualizer<ILocationFactory>(); // 2. Получаем разметку графа. var config = new ConcreteLayoutConfig(); var layouts = visualizer.Create(campaignGraph, config);

Визуализатор возвращает набор объектов типа IGraphNodeLayout<TNodePayload> 

 с данным для отображения каждого узла.

• Node — ссылка на исходный узел графа.

• Position — это целочисленные координаты (X, Y), где нужно отрисовать узел.

• Size — это размер узла. Сейчас значения для всех узлов будут одинаковыми.

Пример конфига для визуализатора:

sealed class ConcreteLayoutConfig : ILayoutConfig {     private const int LAYOUT_NODE_SIZE = 32;     private const int CONTENT_MARGIN = 5;          public int NodeSize => LAYOUT_NODE_SIZE + CONTENT_MARGIN * 2; }

Графы в линию — это конечно решение, но не для крутой игры. Поэтому были добавлены пост-процессоры раскладки графов, чтобы добавить некоторый хаос в граф.

• RetryTransformLayoutPostProcessor — Выполняет произвольную трансформацию узла графа и валидирует изменения. Если изменения не валидны, то повторяет трансформацию. Идея в том, чтобы случайно подвигать узлы графа. Но если узел после перемещения начинает пересекать другие узлы, то попробовать выбрать другую случайную позицию.

• RepeatPostProcessor — Повторяет указанный набор постпроцессоров указанное число раз. Идея в том, чтобы если нам не удалось выбрать подходящую позицию для первых узлов (которые ближе у корню), то мы попробуем еще раз.

• PushHorizontallyPostProcessor — Расталкивает все узлы по горизонтали на указанное значение. Этот процессор нужен, чтобы заранее дать простор для случайных перемещений по горизонтали. Таким образом, по горизонтали будет разное расстояние между узлами.

• RotatePostProcessor — Поворачивает граф на указанный угол в радианах вокруг начала координат. В начале координат будет самый первый корень. В моей игре я поворачиваю на случайный угол от 0 до Pi. По соображениям Ui/UX. Чтобы для игрока движение по графу все еще было слева-направо сверху-вниз.

Вот как это используется у меня:

// Создаем свою реализацию трансформаций узлов  class RandomPositionLayoutTransformer : IGraphNodeLayoutTransformer<ILocationFactory> {     private readonly Random _random;     private readonly int _offsetDistance;      public RandomPositionLayoutTransformer(Random random, int offsetDistance)     {         _random = random;         _offsetDistance = offsetDistance;     }      /// <inheritdoc />     public IGraphNodeLayout<ILocationFactory> Get(IGraphNodeLayout<ILocationFactory> layout)     {         // Calculate new random position of layout.         var offset = new Position(_random.Next(-_offsetDistance, _offsetDistance), _random.Next(-_offsetDistance, _offsetDistance));         var position = new Position(layout.Position.X + offset.X, layout.Position.Y + offset.Y);          // And create new layout.         // If new generated position is not valid it will be failed by validation above.         return new GraphNodeLayout<ILocationFactory>(layout.Node, position, layout.Size);     } }

Собственно, главная сцена. Исказим стройный граф!

// 1. Создаем конвейер пост-процессоров  var random = new Random();  const int TRANSFORM_REPEAT_COUNT = 5; const int TRANSFORM_RETRY_COUNT = 10; var postProcessors = new ILayoutPostProcessor<ILocationFactory>[] {     // Увеличиваем расстояние между узлами.     new PushHorizontallyPostProcessor<ILocationFactory>(config.NodeSize / 2),     // Поворачиваем весь граф на произвольный угол.     new RotatePostProcessor<ILocationFactory>(random.NextDouble() * Math.PI),     // Следующие трансформации будут выполняться несколько раз.     new RepeatPostProcessor<ILocationFactory>(TRANSFORM_REPEAT_COUNT,         // Пробуем сдвинуть узел в слечайном направлении через нашу реализацию трасформаций.         // Если узел начал пересекать другие узлы после сдвига, то повторяем попытку сдвинуть.         new RetryTransformLayoutPostProcessor<ILocationFactory>(     new RandomPositionLayoutTransformer(random, config.NodeSize / 2),             new IntersectsGraphNodeLayoutValidator<ILocationFactory>(), TRANSFORM_RETRY_COUNT)) };  // 2. Обрабатываем набор узлов. foreach (var postProcessor in postProcessors) {     layouts = postProcessor.Process(layouts); }  // 3. Отрисовываем узлы. Тут уже ваш код. foreach (var layout in layouts) {     // Используй:     // - layout.Position.X и layout.Position.Y как координаты, где нужно отрисовывать узел.     // - layout.Size.Width и layout.Size.Height чтобы получить размер узла в пикселях.     // - layout.Node.Payload чтобы прочитать данные узла. В нашм случае это будут целые числа 1-4, которые мы задали при создании графа. }

Генерация графов

Генерация графов — это настоящее творчество. Чтобы локации были интереснее, мне нужно создать уникальные и интересные графы. Чтобы игроку каждый раз было интересно планировать новый маршрут. Но чтобы было больше контроля над локацией, нужно использовать какие-то шаблонные решения. Развивая эту идею, можно создать шаблон основных путей графа. По сути, это будет тоже направленный граф, только более высокого порядка. Алгоритм работы прост: мы обходим граф путей, материализуем шаблоны в конкретные узлы и соединяем начальные и конечные узлы ребрами. Поехали!

Реализация

Для генерации используется библиотека https://github.com/kreghek/CombatDicesTeam.Graphs.Generation.

Все начинается с создания путей. Чтобы создать путь, нужно создать экземпляр GraphWay. Путь — это набор шаблонов, которые являются реализаций интерфейса IGraphTemplate.

Пример:

sealed class CombatLocationTemplate: IGraphTemplate<ILocationFactory> {     IGraphNode<ILocationFactory> Create(IGraphTemplateContext<ILocationFactory> context)     {         // Создаем узел итогового графа return new GraphNode<ILocationFactory>(new CombatLocationFactory());     }      bool CanCreate(IGraphTemplateContext<ILocationFactory> context)     {         // Этот метод может быть использован в других шаблонах.         return true;     } }  ///<summary> /// Выбирает один случайный шаблон или указанный шаблон, если случайный нельзя использовать. ///</summary> sealed class RandomLocationTemplate: IGraphTemplate<ILocationFactory> {     private readonly Random _random;     private readonly IGraphTemplate<ILocationFactory> _fallbackTemplate;     private readonly IGraphTemplate<ILocationFactory>[] _availableTemplates;      public RandomLocationTemplate(Random random, IGraphTemplate<ILocationFactory> fallbackTemplate, params IGraphTemplate<ILocationFactory>[] availableTemplates)     {         _random = random; _fallbackTemplate = fallbackTemplate;         _availableTemplates = availableTemplates;     }          IGraphNode<ILocationFactory> Create(IGraphTemplateContext<ILocationFactory> context)     {         var rolledIndex = _random.Next(0, _availableTemplates.Length - 1); var rolledTemplate = _availableTemplates[rolledIndex];  if (!rolledTemplate.CanCreate(context)) {     return _fallbackTemplate.Create(context); }          // Создаем узел итогового графа return rolledTemplate.Create(context);     }      bool CanCreate(IGraphTemplateContext<ILocationFactory> context)     {         // Этот метод может быть использован в других шаблонах.         return true;     } }

Далее формируем граф путей

public IGraph<GraphWay<ILocationData>> CreateWaysGraph() {     var random = new Random();     var wayGraph = new Graph<GraphWay<ILocationFactory>>();      var way1Templates = new IGraphTemplate<ILocationFactory>[]     {         new CombatLocationTemplate(),         new RestLocationTemplate(),         new CombatLocationTemplate()     };      var way2Templates = new IGraphTemplate<ILocationFactory>[]     {         new CombatLocationTemplate(),         new RandomLocationTemplate(random, new RestLocationTemplate(), new CombatLocationTemplate(), new EventLocationTemplate()),     };      var way3Templates = new IGraphTemplate<ILocationFactory>[]     {         new CombatLocationTemplate(),         new RestLocationTemplate()     };      var regular1Way = new GraphWay<ILocationFactory>(way1Templates);     var way11Node = new GraphNode<GraphWay<ILocationFactory>>(regular1Way);     var way12Node = new GraphNode<GraphWay<ILocationFactory>>(regular1Way);     var way13Node = new GraphNode<GraphWay<ILocationFactory>>(regular1Way);      var regular2Way = new GraphWay<ILocationFactory>(way2Templates);     var way2Node = new GraphNode<GraphWay<ILocationFactory>>(regular2Way);      var regular3Way = new GraphWay<ILocationFactory>(way3Templates);     var way31Node = new GraphNode<GraphWay<ILocationFactory>>(regular3Way);     var way32Node = new GraphNode<GraphWay<ILocationFactory>>(regular3Way);      var rewardNode = new GraphNode<GraphWay<ILocationFactory>>(new GraphWay<ILocationFactory>(new[]     {     new RewardLocationFactory(_services)     }));      wayGraph.AddNode(way11Node);     wayGraph.AddNode(way12Node);     wayGraph.AddNode(way13Node);      wayGraph.AddNode(way2Node);      wayGraph.ConnectNodes(way11Node, way2Node);     wayGraph.ConnectNodes(way12Node, way2Node);     wayGraph.ConnectNodes(way13Node, way2Node);      wayGraph.AddNode(way31Node);     wayGraph.AddNode(way32Node);      wayGraph.ConnectNodes(way2Node, way31Node);     wayGraph.ConnectNodes(way2Node, way32Node);      wayGraph.AddNode(rewardNode);      wayGraph.ConnectNodes(way31Node, rewardNode);     wayGraph.ConnectNodes(way32Node, rewardNode);      return wayGraph; }

И, наконец, создаем граф по шаблону.

var wayGraph = CreateWaysGraph(); var graphGenerator = new TemplateBasedGraphGenerator<ILocationData>(new TemplateConfig<ILocationData>(wayGraph)); var worldGraph = graphGenerator.Create();

Далее worldGraph можно визуализировать так, как я рассказал в статье выше.

Резюме

Я знаю, что код не идеален. Сейчас он решает очень узкую задачу. Но этот код используется в игре TESTAMENT. Для работы с локациями (о чем была статья), для дерева навыков и рецептов крафта. А если потребуется более серьезная работа с графами, лучше использовать один из инструментов выше.

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