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

			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);
		

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

// 2. Получаем разметку графа.
var config = new ConcreteLayoutConfig();
var layouts = visualizer.Create(campaignGraph, config);
		

			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;
}
		

			// Создаем свою реализацию трансформаций узлов

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

			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();