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

[XakeR]

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

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

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

Когда я начал работать над своим пет-проектом 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. Нужно полностью контроллировать, какими могут быть следущие узлы.

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

Моя библиотека предоставляет единственный интерфейс для работы с графами 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. Пример графа // 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) — выполняет обход поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже

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

Рисунок 2. Поуровневое представление графа в памяти

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

Рисунок 3. Выравнивание узлов графа по высоте

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

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

Рисунок 4. Проблема с пересечением ребер

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

1. Назначаем вес корневым узлам. Вес назначается по порядку.
2. Для каждого соседнего узла считаем вес, как среднее всех весов узлов, которые входят.
3. Упорядочиваем узлы по весу в рамках одного уровня.
4. Рекурсивно повторяем для всех уровней.

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

Рисунок 5. Алгоритм раскладки в UML

Реализация​

Библиотека содержит реализацию этого алгоритма. Разберем, как раскатать этот граф в плоскости.

// 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, которые мы задали при создании графа. }

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

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

Реализация​

Для генерации используется эта библиотека.

Все начинается с создания путей. Чтобы создать путь, нужно создать экземпляр 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 можно визуализировать так, как я рассказал в статье выше.

Резюме​

Рисунок 5. Пример использования библиотек

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

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