Какие способы представления графов вы знаете?

Способы представления графов в Unity и C#

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

1. Матрица смежности (Adjacency Matrix)

Это двумерный булевый или целочисленный массив matrix[i][j], где значение указывает на наличие и вес ребра между вершинами i и j.

public class GraphMatrix
{
    private int[,] matrix;
    private int vertexCount;

    public GraphMatrix(int n)
    {
        vertexCount = n;
        matrix = new int[n, n];
    }

    public void AddEdge(int from, int to, int weight = 1, bool directed = false)
    {
        matrix[from, to] = weight;
        if (!directed)
            matrix[to, from] = weight;
    }

    public bool HasEdge(int from, int to) => matrix[from, to] != 0;
}

• Плюсы: Быстрая проверка наличия ребра O(1), удобна для плотных графов.
• Минусы: Потребление памяти O(V²), итерация по соседям требует полного перебора строки.
• В Unity: Используется редко, разве что для небольших графов состояний или матриц переходов.

2. Список смежности (Adjacency List)

Наиболее частый выбор в геймдеве. Каждая вершина хранит динамический список (массив, List<>) смежных вершин, часто вместе с данными ребра.

public class GraphAdjacencyList
{
    public List<List<(int to, float weight)>> edges;

    public GraphAdjacencyList(int vertexCount)
    {
        edges = new List<List<(int, float)>>(vertexCount);
        for (int i = 0; i < vertexCount; i++)
            edges.Add(new List<(int, float)>());
    }

    public void AddEdge(int from, int to, float weight = 1f, bool directed = false)
    {
        edges[from].Add((to, weight));
        if (!directed)
            edges[to].Add((from, weight));
    }

    public List<int> GetNeighbours(int vertex)
    {
        var neighbours = new List<int>();
        foreach (var edge in edges[vertex])
            neighbours.Add(edge.to);
        return neighbours;
    }
}

• Плюсы: Экономия памяти O(V + E), эффективный перебор соседей O(k), где k — число соседей. Идеально для разреженных графов (навигационные меши, социальные графы).
• Минусы: Проверка наличия конкретного ребра дольше (O(k)).
• В Unity: Основа для NavMesh (граф навигации строится именно так), для систем путей (A*), графов диалогов или Tech-деревьев.

3. Список рёбер (Edge List)

Простой список всех рёбер, где каждое ребро — структура (from, to, weight).

public struct Edge
{
    public int from;
    public int to;
    public float cost;
}

public class GraphEdgeList
{
    public List<Edge> edges = new List<Edge>();
    public int vertexCount;

    public void AddEdge(int from, int to, float cost = 1f, bool directed = false)
    {
        edges.Add(new Edge { from = from, to = to, cost = cost });
        if (!directed)
            edges.Add(new Edge { from = to, to = from, cost = cost });
    }
}

• Плюсы: Минимальный расход памяти на хранение только рёбер O(E), простая сериализация.
• Минусы: Медленный поиск соседей или проверка ребра O(E).
• В Unity: Подходит для хранения статических данных уровня (например, список тропинок между точками), которые затем конвертируются в более эффективное представление (список смежности) для поиска пути.

4. Неявное представление (Implicit / Algorithmic Graph)

Граф не хранится в памяти явно, а генерируется "на лету" через правила или алгоритмы.

• Как работает: Вершины — возможные состояния системы (позиция на сетке, комбинация в пазле). Соседи вершины вычисляются по формуле в момент запроса.
• Пример: A* на бесконечной сетке или гексагональной карте.

// Пример: получение соседей клетки в сетке 2D
public List<Vector2Int> GetGridNeighbours(Vector2Int cell, bool allowDiagonals)
{
    var neighbours = new List<Vector2Int>();
    neighbours.Add(new Vector2Int(cell.x + 1, cell.y));
    neighbours.Add(new Vector2Int(cell.x - 1, cell.y));
    // ... Добавляем остальных соседей по правилам
    return neighbours;
}

• Плюсы: Нулевые накладные расходы на хранение графа, подходит для огромных или динамически меняющихся пространств.
• Минусы: Вычислительная нагрузка на генерацию соседей, невозможность быстрого обхода всего графа.
• В Unity: Ключевой метод для процедурной генерации, алгоритмов на тайловых картах или поиска пути в стратегических играх.

Практический выбор в Unity

• Для навигации (NavMeshAgent, свой A*) — почти всегда используется список смежности, построенный на основе данных NavMesh или узлов (Waypoint).
• Для графа поведения (Behavior Tree, диалоги) — чаще используется список смежности или специализированные классы Node и Connection в редакторе Unity.
• Для разреженных связей (друзья в соц. сети игры) — список смежности.
• Для физики или систем частиц (где связи редки) — иногда эффективнее список рёбер.

Вывод: В Unity разработчик чаще всего работает со списками смежности (для поиска путей) и неявными графами (для процедурного контента). Матрица смежности используется в нишевых случаях, а список рёбер — как промежуточное или хранимое представление данных. Понимание плюсов каждого подхода позволяет выбирать оптимальное решение, балансируя между производительностью и расходом памяти, что критически важно в разработке игр.