Пройди свой путь в ширину: библиотеки для графов из инди-игры 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. Для работы с локациями (о чем была статья), для дерева навыков и рецептов крафта. А если потребуется более серьезная работа с графами, лучше использовать один из инструментов выше.

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