Знаете, почему математики не любят направленные нецикличные графы? Потому что если они совершать ошибку, они не смогут вернуться.
С чего все началось
Графы — это не только математический объект, но и важный инструмент программистов. Они используются в играх, визуализации данных, социальных сетях и других серьезных проектах. Если вы не знаете, как работать с графами, то вы не программист. Конкретно раскладка графа в плоскости — задача не тривиальная. Но что делать, если вы хотите решить эту задачу легковесно и быстро?
Когда я начал работать над своим пет-проектом TESTAMENT, мне нужно было генерировать и отображать произвольные графы. Я хотел, чтобы локации были в виде простых шагов-событий, соединенных между собой. Примерами могут послужить проекты Slay The Spire, Cult of the Lamb, Darkest Dungeon и другие. Исследовав вопрос, я увидел, что существующие библиотеки слишком тяжелые и сложные для моих нужд.
QuickGraph — развитая библиотека, которая активно используется в промышленных системах. Наверное, самым мастодонт среди всех библиотек, которые я знаю.
GraphShape — форк и последующая переработка заброшенного GraphSharp. Куча алгоритмов раскладки. И скупая документация, кажется, для галочки.
Microsoft Automatic Graph Layout — мощное решение от лидера рынка корпоративных решений.
YWorks — красивое коммерческое решение.
Все эти штуки наверняка могут отобразить граф супер эффективным и академически правильным способом. Но тогда, возможно, код работы с графами станет наибольшей частью кодовой базы моего небольшого проекта. Я понял, что мне нужно простое и легковесное решение для небольших инди-игр, которое будет работать быстро и без лишних сложностей. Так я попробовал сделать набросок своего алгоритма раскладки и, о чудо, вышло быстро и дало неплохой результат. В этой статье я расскажу о моем наборе библиотек, который поможет вам создавать случайные графы и раскладывать их в плоскости с минимальными усилиями.
Какими будут мои графы:
Графы направленные. По сути — деревья.
Графы нецикличные.
Может быть несколько стартовых узлов.
Предполагается один финишный узел.
Из одного узла может выходить несколько ребер в разные соседние узлы.
Один узел может принимать несколько ребер от разных соседних узлов.
Все узлы одинакового размера.
Подойдет вариант визуализации, когда граф просто вытянут в линию. Возможно даже, такой вариант наиболее предпочтителен. Чтобы игрок проходил от начала (слева) до конца (направо).
При генерации:
Всегда должно быть несколько стартовых улов.
В определенный момент несколько узлов графа должны входить в один узел.
В определенный момент один узел должен разветвляться на строго определенное количество узлов.
Нужно полностью контроллировать, какими могут быть следущие узлы.
Минимальные графы
Моя библиотека 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().
Для того, чтобы «сгладить» эту проблему, выполним следующую доработку:
Назначаем вес корневым узлам. Вес назначается по порядку.
Для каждого соседнего узла считаем вес, как среднее всех весов узлов, которые входят.
Упорядочиваем узлы по весу в рамках одного уровня.
Рекурсивно повторяем для всех уровней.
Весь алгоритм в 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. Для работы с локациями (о чем была статья), для дерева навыков и рецептов крафта. А если потребуется более серьезная работа с графами, лучше использовать один из инструментов выше.
Тем не менее, я бы хотел получить обратную связь, разумную критику и предложения по улучшению. Я надеюсь, мои библиотеки помогут другим независимым разработчикам в их небольших проектах. Я готов помочь и дать советы по использованию библиотек. А если вы хотите что-то доработать — я буду только рад и тоже готов помочь разобраться! Так что давайте сделаем этот код круче вместе!
