Разработка системы навигации (NavMesh/Pathfinding) мобильной игры

Разработка системы навигации (NavMesh/Pathfinding) мобильной игры

Противник, который ходит сквозь стены, или NPC, застрявший в углу — это не баг, это отсутствие нормальной системы навигации. NavMesh и pathfinding решают конкретную задачу: дать агенту маршрут от точки A до точки B с обходом препятствий, и сделать это быстро.

NavMesh: статическая геометрия навигации

NavMesh — это упрощённое представление уровня, по которому может перемещаться агент. Строится один раз при загрузке уровня (или заранее запекается в редакторе). В Unity — встроенный NavMesh с NavMeshAgent компонентом. В Godot — NavigationServer3D / NavigationServer2D.

Ключевые параметры запекания NavMesh, которые влияют на качество:

Agent Radius: 0.4      // радиус капсулы агента — NavMesh строится с отступом
Agent Height: 1.8      // высота — для обнаружения низких проходов
Max Slope: 45°         // максимальный угол подъёма
Step Height: 0.4       // высота ступеньки, которую агент преодолевает

На мобильных устройствах важно: NavMesh запекается заранее в Editor, не в runtime. Runtime baking (через NavMeshBuilder.BuildNavMeshAsync) доступен, но на слабых устройствах занимает 100–500ms и создаёт GC давление.

A* и его варианты

Для поиска пути по NavMesh Unity использует встроенный A* с эвристикой Euclidean distance. Для большинства мобильных игр это оптимально. Но есть сценарии, где стандартный A* не справляется:

Динамические препятствия — игрок выставил баррикады, дверь закрылась. Стандартный NavMesh нужно перестраивать. Решение — NavMeshObstacle с Carve = true: компонент «вырезает» себя из NavMesh в runtime, но пересчёт затратен. Альтернатива для частых изменений — Flow Field pathfinding: заранее рассчитываем векторное поле для цели, агенты следуют по полю без индивидуального поиска пути.

Много агентов к одной цели — зомби-игры, tower defense. A* для каждого агента отдельно при 100+ агентах убивает производительность. Flow Field считается один раз для всего поля — агенты читают значение своей ячейки. O(1) на агента против O(n log n) для A*.

// Unity: базовый Flow Field запрос для тайловой карты
public class FlowField {
    private Vector2[,] directions;
    private int width, height;

    public void Calculate(Vector2Int target, bool[,] obstacles) {
        // BFS от цели, рассчитываем стоимость и направление для каждой клетки
        var costField = new int[width, height];
        var queue = new Queue<Vector2Int>();
        queue.Enqueue(target);
        costField[target.x, target.y] = 0;

        while (queue.Count > 0) {
            var current = queue.Dequeue();
            foreach (var neighbor in GetNeighbors(current)) {
                if (!obstacles[neighbor.x, neighbor.y] &&
                    costField[neighbor.x, neighbor.y] == int.MaxValue) {
                    costField[neighbor.x, neighbor.y] = costField[current.x, current.y] + 1;
                    queue.Enqueue(neighbor);
                }
            }
        }
        // Заполняем directions на основе costField...
    }

    public Vector2 GetDirection(Vector2Int position) => directions[position.x, position.y];
}

Steering behaviours: плавное движение

Pathfinding даёт маршрут — список точек. Steering behaviours превращают это в плавное движение:

• Seek / Arrive: движение к цели с замедлением при приближении
• Obstacle Avoidance: обход динамических препятствий через Raycast
• Separation: агенты не накапливаются в одной точке
• Cohesion: группа держится вместе (для стайного поведения)

NavMeshAgent в Unity включает базовые steering behaviours. Для более тонкой настройки — RVOSimulator из пакета com.unity.ai.navigation (ORCA алгоритм для reciprocal velocity obstacles).

Производительность на мобильных устройствах

Не пересчитывай путь каждый кадр. NavMeshAgent.SetDestination() при каждом вызове запускает новый pathfinding запрос. Для преследования игрока достаточно пересчитывать каждые 0.3–0.5 секунды:

private float pathUpdateTimer = 0f;
private const float PATH_UPDATE_INTERVAL = 0.3f;

void Update() {
    pathUpdateTimer += Time.deltaTime;
    if (pathUpdateTimer >= PATH_UPDATE_INTERVAL) {
        agent.SetDestination(player.position);
        pathUpdateTimer = 0f;
    }
}

LOD для навигации. Агенты за пределами камеры отключают NavMeshAgent, используют упрощённую телепортацию к waypoints. Включаем полный pathfinding только при попадании в frustum.

Unity Job System для A.* Если нужен кастомный pathfinding на большой карте — IJob + NativeArray<> выносит вычисления с main thread. Burst Compiler даёт ~10x ускорение для числодробилок pathfinding.

Отладка и визуализация

Pathfinding сложно дебажить без визуализации. В Editor режиме рисуем NavMesh path:

void OnDrawGizmos() {
    if (agent != null && agent.hasPath) {
        Gizmos.color = Color.yellow;
        var corners = agent.path.corners;
        for (int i = 0; i < corners.Length - 1; i++) {
            Gizmos.DrawLine(corners[i], corners[i + 1]);
        }
    }
}

Процесс работы

Анализ уровня: статическая геометрия, динамические препятствия, число агентов.

Выбор алгоритма: NavMesh + A* для типовых сценариев, Flow Field для массовых агентов.

Настройка параметров NavMesh, интеграция с игровой геометрией.

Реализация steering behaviours, настройка плавности движения.

Оптимизация: LOD навигации, интервалы обновления, Job System для кастомного pathfinding.

Тестирование на целевых устройствах с профилировщиком Unity Profiler.

Ориентиры по срокам

Базовая навигация через NavMeshAgent для 5–10 типов агентов — 3–5 дней. Кастомная система с Flow Field, динамическими препятствиями и LOD оптимизацией — 2–4 недели.