Приведи пример использования Graph

Использование Graph в Unity: создание системы навигации

В Unity понятие Graph (граф) чаще всего ассоциируется с пакетом Graph Tools Foundation, визуальными редакторами типа NodeGraph или низкоуровневыми структурами данных для представления связей. Я приведу практический пример реализации системы навигации для NPC по точкам интереса на сцене, используя граф как структуру данных.

Проектирование графа навигации

Мы создадим граф, где вершины (Nodes) — это ключевые точки на уровне (например, углы комнаты, посты охраны), а рёбра (Edges) — допустимые пути между ними. Это позволит NPC планировать маршруты, избегая полного перебора всех объектов сцены.

Реализация классов графа

using System.Collections.Generic;
using UnityEngine;

[System.Serializable]
public class NavNode
{
    public int Id;
    public Vector3 Position;
    public List<int> ConnectedNodeIds; // Список Id связанных узлов
}

public class NavigationGraph : MonoBehaviour
{
    public List<NavNode> Nodes = new List<NavNode>();
    private Dictionary<int, NavNode> _nodeDictionary;

    void Awake()
    {
        BuildDictionary();
    }

    private void BuildDictionary()
    {
        _nodeDictionary = new Dictionary<int, NavNode>();
        foreach (var node in Nodes)
        {
            _nodeDictionary[node.Id] = node;
        }
    }

    // Поиск кратчайшего пути алгоритмом BFS
    public List<Vector3> FindPath(int startNodeId, int targetNodeId)
    {
        if (!_nodeDictionary.ContainsKey(startNodeId) || !_nodeDictionary.ContainsKey(targetNodeId))
            return null;

        var queue = new Queue<int>();
        var visited = new Dictionary<int, int>(); // Key: nodeId, Value: parentId
        queue.Enqueue(startNodeId);
        visited[startNodeId] = -1;

        while (queue.Count > 0)
        {
            int currentNodeId = queue.Dequeue();
            if (currentNodeId == targetNodeId)
                break;

            foreach (int neighborId in _nodeDictionary[currentNodeId].ConnectedNodeIds)
            {
                if (!visited.ContainsKey(neighborId))
                {
                    visited[neighborId] = currentNodeId;
                    queue.Enqueue(neighborId);
                }
            }
        }

        // Восстановление пути
        if (!visited.ContainsKey(targetNodeId))
            return null;

        List<int> pathIds = new List<int>();
        int current = targetNodeId;
        while (current != -1)
        {
            pathIds.Add(current);
            current = visited[current];
        }
        pathIds.Reverse();

        // Конвертация Id в позиции
        List<Vector3> pathPositions = new List<Vector3>();
        foreach (int id in pathIds)
        {
            pathPositions.Add(_nodeDictionary[id].Position);
        }
        return pathPositions;
    }
}

Интеграция с NPC

public class NPCNavigator : MonoBehaviour
{
    [SerializeField] private NavigationGraph _graph;
    [SerializeField] private float _movementSpeed = 3f;
    
    private List<Vector3> _currentPath;
    private int _currentPathIndex;
    private int _currentNodeId;
    private int _targetNodeId = 2;

    void Start()
    {
        // Найти начальный ближайший узел
        _currentNodeId = FindClosestNodeId(transform.position);
        // Рассчитать путь
        _currentPath = _graph.FindPath(_currentNodeId, _targetNodeId);
    }

    void Update()
    {
        if (_currentPath == null || _currentPath.Count == 0)
            return;

        Vector3 targetPosition = _currentPath[_currentPathIndex];
        transform.position = Vector3.MoveTowards(transform.position, targetPosition, _movementSpeed * Time.deltaTime);

        if (Vector3.Distance(transform.position, targetPosition) < 0.1f)
        {
            _currentPathIndex++;
            if (_currentPathIndex >= _currentPath.Count)
            {
                _currentPath = null; // Маршрут завершён
            }
        }
    }

    private int FindClosestNodeId(Vector3 position)
    {
        // Логика поиска ближайшего узла в графе
        // Упрощённая реализация
        return 0;
    }
}

Ключевые преимущества такого подхода

• Производительность: Поиск пути по графу из 100 узлов выполняется мгновенно, в отличие от навигации по сотням объектов в сцене.
• Контроль над маршрутами: Дизайнеры могут явно указать, какие точки связаны между собой, исключая невозможные пути.
• Динамическая модификация: Можно временно удалять рёбра графа при блокировке прохода или добавлять новые узлы при генерации уровней.
• Абстракция от Unity: Ядро графа не зависит от MonoBehaviour, что позволяет тестировать его отдельно и использовать в серверной логике.

Расширение функциональности

1. Взвешенные рёбра: Добавить стоимость перехода между узлами для реализации алгоритма Dijkstra или A*.
2. Визуальный редактор: Создать кастомный EditorWindow для расстановки узлов и соединения их линиями.
3. Графы состояний: Аналогичную структуру можно использовать для Behaviour Tree или диалоговых систем, где узлы представляют действия, а рёбра — условия перехода.

Такой подход демонстрирует, как графы из теоретической структуры данных превращаются в практический инструмент для решения типовых задач геймдева: навигации, AI и управления игровой логикой. Он балансирует между простотой реализации и достаточной мощностью для большинства инди-проектов и прототипов.