Когда A* перестает быть удобным для толпы
Если на сцене одновременно движутся десятки или сотни юнитов, классический A* быстро упирается не в точность, а в стоимость повторного поиска. Один юнит строит маршрут относительно быстро, но сто агентов, каждый со своей целью, радиусом, препятствиями и частотой пересчета, начинают создавать заметную нагрузку на CPU. Ситуация становится еще хуже, если юниты должны не только добираться до цели, но и регулярно перестраивать путь из-за динамических объектов, дверей, потоков врагов или изменяющейся карты.
Flow Field решает именно эту задачу. Вместо того чтобы рассчитывать отдельный путь для каждого агента, система строит одно общее направление движения для всей зоны. Карта разбивается на ячейки, для которых вычисляются стоимость прохождения, накопленная дистанция до цели и итоговый вектор направления. После этого любой юнит, оказавшийся в пределах поля, просто смотрит на локальный вектор и движется по нему. Для толпы это намного дешевле, чем десятки и сотни независимых маршрутов.
Подход особенно хорош для RTS, tower defense, орд противников, эвакуации NPC, массового поиска пути на больших картах и сцен, где движения агентов похожи по целям. Именно поэтому Flow Field часто используют там, где A* остается полезным лишь на уровне разового построения глобальной навигации, а не на уровне каждого отдельного объекта.
Из чего состоит Flow Field
Flow Field обычно описывают через три связанных слоя. Первый слой хранит стоимость ячейки. Второй слой, интеграционное поле, показывает накопленную цену пути от любой ячейки до цели. Третий слой, векторное поле, превращает эту информацию в локальное направление движения. Если убрать хотя бы один слой, система либо теряет точность, либо перестает быть достаточно полезной для массовой навигации.
Поле стоимостей отвечает за то, насколько дорого проходить через конкретную ячейку. Это может быть обычная проходимость земли, а может быть более сложная метрика: вода дороже земли, болото дороже дороги, узкий проход дороже открытого пространства, клетка рядом с опасной зоной получает штраф. Именно здесь начинается гибкость подхода, потому что Flow Field не обязан видеть мир как бинарную сетку «можно» и «нельзя».
Интеграционное поле строится от цели наружу и хранит минимальную стоимость достижения цели из каждой ячейки. На практике это часто делается обратным распространением по сетке, похожим на Dijkstra с учетом веса клеток. После этого векторное поле смотрит на соседей каждой ячейки и выбирает направление к ячейке с меньшей интегральной стоимостью. В итоге юниту не нужно знать весь маршрут, ему достаточно текущего локального градиента.
Почему это работает для толпы
У A* каждый агент решает собственную задачу поиска пути. Даже если путь строится не каждый кадр, а раз в несколько секунд, суммарная нагрузка быстро растет. У Flow Field главный расчет выполняется один раз для зоны и одной цели, а затем переиспользуется всеми агентами внутри этой зоны. Это особенно выгодно, если 80 юнитов бегут к одной базе, защищают один объект или атакуют один центр карты.
Есть и еще один практический плюс: толпа ведет себя более согласованно. Когда у каждого агента свой A*-путь, они часто начинают расходиться по узким коридорам, толкаться в углах и образовывать неестественные «волны» движения. Flow Field задает общее поле направления, поэтому группа выглядит собраннее. Это не отменяет локального избегания столкновений, но снижает хаос на уровне глобальной навигации.
Поле стоимостей как основа навигации
Первая задача при реализации Flow Field в Unity состоит в том, чтобы превратить сцену в сетку и научиться назначать каждой ячейке стоимость. Размер сетки зависит от масштаба игры. Для RTS и tower defense часто используют клетки от 0,5 до 2 метров. Чем мельче клетка, тем точнее маршрут, но тем выше цена построения и хранения полей. Если карта 256 на 256 клеток, это уже 65 536 ячеек, и такие размеры нужно оценивать заранее.
Стоимость может быть дискретной или плавной. Самый простой вариант: проходимая клетка стоит 1, непроходимая получает бесконечность или специальный маркер блокировки. Более практичный вариант: разные типы поверхности дают разные веса. Например, дорога стоит 1, трава 2, грязь 4, опасная зона 8. При этом поток юнитов можно направлять так, чтобы они естественно предпочитали более быстрые и безопасные пути, не требуя отдельной логики выбора маршрута.
В Unity стоимость обычно хранится в массиве или плоском буфере, чтобы не распылять память на множество мелких объектов. Для прямоугольной сетки удобно использовать индекс index = x + y * width. Такой подход ускоряет доступ и упрощает последующие расчеты. Если нужна визуализация, значения можно отображать через Gizmos или отдельный debug overlay.
using UnityEngine;
public class FlowFieldGrid : MonoBehaviour
{
[SerializeField] private int width = 64;
[SerializeField] private int height = 64;
[SerializeField] private float cellSize = 1f;
[SerializeField] private LayerMask obstacleMask;
[SerializeField] private Vector3 origin;
private int[] costField;
private void Awake()
{
costField = new int[width * height];
BuildCostField();
}
private void BuildCostField()
{
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
int index = x + y * width;
Vector3 worldPos = GridToWorld(x, y);
// Базовая стоимость проходимой клетки.
int cost = 1;
// Если клетка перекрыта препятствием, помечаем ее как непроходимую.
if (Physics.CheckBox(worldPos, Vector3.one * (cellSize * 0.45f), Quaternion.identity, obstacleMask))
{
cost = int.MaxValue;
}
costField[index] = cost;
}
}
}
private Vector3 GridToWorld(int x, int y)
{
return origin + new Vector3((x + 0.5f) * cellSize, 0f, (y + 0.5f) * cellSize);
}
}
Код выше показывает минимальный каркас. В рабочем проекте его почти всегда расширяют: добавляют разные слои стоимости, кэширование, динамические изменения и отдельные правила для диагоналей. Однако базовая идея остается прежней: каждая ячейка должна иметь цену прохода, по которой затем строится общий маршрутный градиент.
Если карта меняется редко, поле стоимостей выгоднее пересчитывать по событию, а не в каждом кадре. Для массовой навигации это часто дает больший выигрыш, чем попытка оптимизировать сам цикл движения юнитов.
Интеграционное поле строится от цели
Интеграционное поле отвечает за вопрос не «какая эта клетка», а «сколько стоит добраться до цели из этой клетки». Для его построения часто используют алгоритм, похожий на волновое распространение Dijkstra. Стартом служит цель, а дальше по сетке распространяется накопленная стоимость с учетом стоимости переходов между ячейками. Если поле стоимостей меняется, интеграционное поле пересчитывается заново.
Практически это означает, что путь не строится один раз как длинная цепочка узлов. Вместо этого вся область получает числовой ландшафт: чем ближе к цели и чем дешевле путь, тем меньше значение. Юниту достаточно посмотреть на соседние клетки и пойти туда, где значение ниже. Этот принцип особенно хорошо работает в играх, где цель фиксирована или меняется не слишком часто.
using System.Collections.Generic;
using UnityEngine;
public class FlowFieldIntegration : MonoBehaviour
{
[SerializeField] private int width = 64;
[SerializeField] private int height = 64;
[SerializeField] private int[] costField;
private int[] integrationField;
private const int INF = int.MaxValue / 4;
private void Awake()
{
integrationField = new int[width * height];
}
public void BuildIntegrationField(int goalX, int goalY)
{
for (int i = 0; i < integrationField.Length; i++)
integrationField[i] = INF;
int goalIndex = goalX + goalY * width;
integrationField[goalIndex] = 0;
var queue = new Queue<int>();
queue.Enqueue(goalIndex);
while (queue.Count > 0)
{
int current = queue.Dequeue();
int cx = current % width;
int cy = current / width;
// Проверяем 4-связных соседей. Для 8-связности логика расширяется.
TryRelax(cx + 1, cy, current, queue);
TryRelax(cx - 1, cy, current, queue);
TryRelax(cx, cy + 1, current, queue);
TryRelax(cx, cy - 1, current, queue);
}
}
private void TryRelax(int x, int y, int fromIndex, Queue<int> queue)
{
if (x < 0 || y < 0 || x >= width || y >= height)
return;
int toIndex = x + y * width;
if (costField[toIndex] == int.MaxValue)
return;
int newCost = integrationField[fromIndex] + costField[toIndex];
if (newCost < integrationField[toIndex])
{
integrationField[toIndex] = newCost;
queue.Enqueue(toIndex);
}
}
}
Упрощенный пример выше использует очередь. В чистом виде это ближе к BFS, чем к полноценному Dijkstra, поэтому для клеток с разной ценой перехода в продакшене обычно применяют priority queue или bucket-based подход. Иначе маршрут может получиться неоптимальным. В Unity 2022 и 2023 можно легко написать собственную приоритетную очередь на массиве или использовать готовую структуру, если проект уже содержит свою коллекцию.
При равных ценах клеток BFS работает приемлемо, но как только появляются разные типы местности, точность начинает страдать. Для игр с дорогами, болотами, препятствиями и бонусными зонами лучше сразу строить полноценное поле накопленной стоимости. Это даст более предсказуемое поведение, особенно когда игрок пытается «сломать» навигацию узкими коридорами и искусственными ловушками.
Зачем нужен обратный расчет
Иногда кажется, что проще строить путь от каждого юнита к цели напрямую. На практике обратный расчет от цели дешевле и стабильнее, если цель общая. Система строит одно поле, а агенты лишь читают его локально. При 200 юнитах это означает не 200 построений пути, а одно пересчетное поле и 200 дешевых выборов направления. При 60 FPS разница становится особенно заметной на CPU, где основной поток и так занят анимацией, физикой, UI и игровыми системами.
Еще одна причина обратного подхода связана с динамикой боя. Когда цель обороняется, захватывается или перемещается, поле можно перестроить только после изменения состояния. Это дешевле, чем поддерживать сотни индивидуальных маршрутов, каждый из которых требует проверки на актуальность. Поэтому Flow Field часто применяют вместе с редкими, но крупными пересчетами, а не с частым локальным A*.
Векторное поле превращает числа в движение
Последний слой Flow Field, векторное поле, отвечает за фактическое движение агента. Оно смотрит на интеграционные значения соседних клеток и выбирает направление к наименьшему значению. Иначе говоря, это локальный градиент, который юнит использует как подсказку. Сам маршрут в памяти не хранится, но по полю можно пройти от любой точки к цели, если в каждой ячейке идти туда, где стоимость ниже.
Векторное поле обычно строят после интеграционного. Для каждой ячейки выбирается сосед с минимальной интегральной стоимостью, затем вычисляется нормализованный вектор. Если клетка находится рядом с препятствием, расчет можно уточнить, чтобы агент не цеплял углы. При 8-связной сетке это особенно полезно, потому что путь получается менее «квадратным» и визуально естественнее.
using UnityEngine;
public class FlowFieldVectors : MonoBehaviour
{
[SerializeField] private int width = 64;
[SerializeField] private int height = 64;
[SerializeField] private float cellSize = 1f;
[SerializeField] private int[] integrationField;
private Vector2[] vectorField;
private void Awake()
{
vectorField = new Vector2[width * height];
}
public void BuildVectorField()
{
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
int index = x + y * width;
int current = integrationField[index];
if (current == int.MaxValue / 4)
{
vectorField[index] = Vector2.zero;
continue;
}
Vector2 bestDir = Vector2.zero;
int bestValue = current;
EvaluateNeighbor(x + 1, y, ref bestValue, ref bestDir, x, y);
EvaluateNeighbor(x - 1, y, ref bestValue, ref bestDir, x, y);
EvaluateNeighbor(x, y + 1, ref bestValue, ref bestDir, x, y);
EvaluateNeighbor(x, y - 1, ref bestValue, ref bestDir, x, y);
vectorField[index] = bestDir.normalized;
}
}
}
private void EvaluateNeighbor(int x, int y, ref int bestValue, ref Vector2 bestDir, int fromX, int fromY)
{
if (x < 0 || y < 0 || x >= width || y >= height)
return;
int value = integrationField[x + y * width];
if (value < bestValue)
{
bestValue = value;
bestDir = new Vector2(x - fromX, y - fromY);
}
}
}
Полученный векторный массив затем читают все агенты. В движение его можно переводить через Rigidbody, CharacterController или собственную kinematic-логику. Для толпы обычно удобнее свой контроллер, потому что он дает больший контроль над скоростью, радиусом избегания и реакцией на локальные препятствия. В проектах, где уже используются готовые шаблоны управления, например Toon RTS Units - Demo или Low Poly Shooter Pack, Flow Field часто служит именно слоем глобального направления, а не заменой всей системы перемещения.
Как юнит читает поле и двигается по нему
Сам юнит не должен знать, как строилась карта стоимости. Он получает координаты на сетке, смотрит в векторное поле и двигается в указанном направлении. Это делает систему компактной: данные строятся централизованно, а агенты остаются легкими. Такой разрыв между расчетом и исполнением особенно полезен в Unity, где лишние вычисления в Update быстро множатся на количество объектов.
Типичная схема движения выглядит так: юнит переводит свою мировую позицию в координаты сетки, считывает вектор из массива, умножает его на скорость и передает результат в контроллер движения. Если агент находится между ячейками, можно использовать билинейную интерполяцию между соседними векторами. Тогда движение становится плавнее, особенно на сетках с крупными клетками. При небольших ячейках иногда достаточно брать ближайшую клетку, но это ухудшает стабильность на поворотах.
using UnityEngine;
public class FlowFieldAgent : MonoBehaviour
{
[SerializeField] private float speed = 3.5f;
[SerializeField] private float cellSize = 1f;
[SerializeField] private Vector3 origin;
[SerializeField] private Vector2[] vectorField;
[SerializeField] private int width = 64;
[SerializeField] private int height = 64;
private void Update()
{
Vector2 move = SampleFlowField(transform.position);
transform.position += new Vector3(move.x, 0f, move.y) * (speed * Time.deltaTime);
}
private Vector2 SampleFlowField(Vector3 worldPos)
{
Vector3 local = worldPos - origin;
int x = Mathf.FloorToInt(local.x / cellSize);
int y = Mathf.FloorToInt(local.z / cellSize);
if (x < 0 || y < 0 || x >= width || y >= height)
return Vector2.zero;
return vectorField[x + y * width];
}
}
На практике сюда почти всегда добавляют локальное избегание столкновений. Flow Field отвечает за глобальную цель, но не решает проблему того, как два агента расходятся в дверном проеме. Для этого применяют простую сепарацию, steering behaviors или небольшой локальный рейтрейс по ближайшим препятствиям. Если нужен более плавный слой поведения, полезно посмотреть на Steering Behaviors в Unity, потому что именно там удобно добирать недостающую микродинамику.
Как избежать дрожания и залипания
Одна из частых ошибок при работе с Flow Field в Unity связана с тем, что агент слишком буквально следует вектору ячейки. Если сетка грубая, движение получается рваным: юнит то идет вперед, то резко поворачивает. Чтобы этого не было, используют сглаживание направления, интерполяцию между соседями или отдельный коэффициент поворота. Также полезно не менять направление мгновенно, а постепенно приближать текущий вектор к целевому.
Залипание часто возникает у границ непроходимых клеток. Агент пытается пройти через угол, но локально не может получить корректный вектор. Здесь помогает либо более мелкая сетка, либо корректировка стоимостей вокруг препятствия, либо отдельный режим обхода узких мест. Если дверные проемы и коридоры в игре критичны, сетка не должна быть слишком крупной, иначе поле будет направлять толпу слишком грубо.
Сильные и слабые стороны по сравнению с A*
Flow Field почти всегда выигрывает там, где есть много агентов и общая цель. A* хорош, когда нужен точный индивидуальный маршрут, когда цель одна, но сцена маленькая, или когда путь строится редко. Стоимость A* растет с количеством запросов, а стоимость Flow Field растет в первую очередь с размером карты и числом пересчетов поля. Это два разных профиля нагрузки, и выбор зависит от формы задачи.
Если сравнивать по сценарию, то A* удобно использовать для одиночных персонажей, героев, редких NPC, транспорта с индивидуальной траекторией. Flow Field лучше показывает себя в атаках толпы, охране базы, ордах зомби, массовом построении, бегстве сотен существ и режимах, где агенты двигаются в одном направлении через одну и ту же территорию. Для проектов на основе RTS-подобной логики он часто становится базовым слоем навигации, а A* остается вспомогательным механизмом на уровне выборочных уточнений.
Есть и компромисс. Flow Field не так удобно использовать в сложной, сильно динамической сцене с множеством независимых целей. Если у каждого агента свой уникальный заказ, если карта часто меняется или если уровни состоят из мелких, узких и разнесенных участков, пересчет поля может стать дорогим. В таких случаях логичнее оставить A* для уникальных маршрутов, а Flow Field включать только для массовых групп.
Полезно смотреть и на память. Одно поле стоимостей, одно интеграционное поле и одно векторное поле для карты 128x128 в массиве int и Vector2 занимают немного: порядка сотен килобайт. Но при увеличении до 512x512 размер растет быстро, особенно если хранить дополнительные слои и данные для нескольких целей. Поэтому перед внедрением стоит оценить размеры зон, частоту пересчетов и число одновременно активных полей.
Практическая схема внедрения в Unity
Удобнее всего внедрять Flow Field по этапам. Сначала строится сетка и проверяется корректность разметки препятствий. Затем добавляется поле стоимостей. После этого включается интеграционное поле, и только потом векторное направление. Такой порядок упрощает отладку: если юниты не двигаются, можно понять, на каком слое ошибка. В сложной системе сразу собранный результат трудно диагностировать.
Для отладки полезно выводить каждое поле в gizmos или в текстуру. Стоимости можно красить в оттенки от зеленого к красному, интеграционное поле отображать по яркости, векторное поле рисовать стрелками. Даже в средних по размеру проектах это экономит часы, потому что визуальная карта ошибок сразу показывает непроходимые зоны, дыры в градиенте и неверные значения на границах.
Если проект использует системы вроде Job System и Burst Compiler, то вычисление полей можно вынести в jobs. Для больших карт и частых пересчетов это полезно, потому что построение стоимости и интеграции хорошо распараллеливается. При этом нужно аккуратно обращаться с доступом к памяти и исключить аллокации в горячем коде. Если же поле обновляется редко, обычный main thread-код может оказаться проще и дешевле по сопровождению.
Пошаговый рабочий план
На практике реализация обычно проходит через несколько последовательных шагов. Сначала задается размер клетки, границы карты и список коллайдеров, которые должны считаться препятствиями. Потом строится массив стоимости. Затем от цели запускается обратное распространение, вычисляющее интеграционную карту. После этого для каждой клетки выбирается направление к соседу с минимальным значением. В финале агенты начинают читать готовое поле и двигаться по нему, а локальное избегание столкновений добавляется отдельно.
- Определите размер сетки и клеток, исходя из масштаба уровня.
- Соберите поле стоимостей из геометрии и данных уровня.
- Постройте интеграционное поле от одной или нескольких целей.
- Сгенерируйте векторное поле и проверьте его в редакторе.
- Подключите читателя поля к юнитам и добавьте локальное избегание.
На этапе тестирования полезно сравнивать поведение толпы на ровной поверхности, в коридорах и возле больших препятствий. Если в одной из этих ситуаций появляются странные развороты, вероятнее всего, ошибка не в движении, а в дискретизации поля. Чем раньше такая проблема найдена, тем проще пересмотреть размеры ячеек и правила расчета соседей.
Частые ошибки при реализации Flow Field
Одна из типичных ошибок состоит в слишком крупной сетке. На бумаге 32x32 клетки выглядят дешево, но на практике в узких проходах такая сетка не способна корректно описать маршрут. В результате юниты видят один и тот же вектор на большой площади и начинают резать углы. Для толпы это может выглядеть приемлемо на дальних планах, но в тесных сценах быстро бросается в глаза.
Вторая ошибка связана с пересчетом поля каждый кадр без реальной необходимости. Если цель не изменилась и препятствия статичны, пересчитывать интеграцию в Update бессмысленно. Даже при небольших картах это превращается в лишнюю нагрузку. Лучше запускать пересчет по событию: изменился уровень, переместилась база, открылся проход, закрылся мост, появился новый барьер.
Третья проблема возникает, когда локальное избегание конфликтует с глобальным полем. Юнит хочет идти по вектору, но ближайший сосед смещает его в сторону, и агент начинает дрожать на месте. Чтобы этого не было, нужно развести зоны ответственности. Flow Field задает глобальную цель, а локальный steering регулирует короткие столкновения. Если обе системы пытаются полностью управлять позицией одновременно, результат становится нестабильным.
Наконец, нельзя забывать о границах карты. На внешних ячейках часто появляются неверные значения, если не проверить выход за пределы массива. Это банальная ошибка, но именно она чаще всего приводит к странным выбросам направления. Защита индексов должна быть такой же аккуратной, как и в любой другой сеточной системе.
Когда Flow Field лучше не использовать
Есть сценарии, где этот подход не оправдывает себя. Если в сцене движется один герой или несколько одиночных NPC, A* или навигационная сетка с локальным уточнением будут проще. Если маршрут постоянно меняется индивидуально для каждого агента, Flow Field быстро теряет смысл, потому что поле придется пересчитывать слишком часто или хранить много отдельных версий для разных целей. Если уровень построен из узких, сильно разветвленных коридоров с малым пространством для маневра, точность сеточного поля может оказаться недостаточной.
Еще один ограничивающий фактор связан с визуальной и дизайнерской составляющей. В играх, где движение должно быть максимально «ручным» и выразительным, например в тактических сценах с уникальными траекториями персонажей, потоковое поле может выглядеть слишком механически. В таких случаях его лучше применять только на фоне общей логики, а поведение отдельных персонажей строить другими средствами. Flow Field хорош там, где важны масштаб и согласованность, а не индивидуальная пластика каждого агента.
Что сделать в проекте, если нужна массовая навигация
Если на сцене уже есть сотни юнитов и они начинают перегружать A*, сначала переведите глобальную навигацию на сетку с полем стоимостей и интеграционным полем. Затем отделите вычисление полей от движения агентов и перестройте обновление только по событию. После этого добавьте локальное избегание столкновений и визуальную отладку полей. Такой порядок обычно дает быстрее ощутимый результат, чем попытка «оптимизировать A*» без смены архитектуры.
Для массовых RTS, орд и оборонительных волн Flow Field стоит рассматривать не как эксперимент, а как базовую схему поиска пути. Именно здесь он выигрывает по стоимости расчета, предсказуемости и удобству для толпы. Если проект уже использует готовые шаблоны юнитов, ассеты с RTS-контроллерами или мобильные экшн-системы, имеет смысл оценить, насколько легко в них встраивается общий поток навигации, а не отдельный путь для каждого NPC.
