Flow fields: один расчёт вместо тысячи A*

Тысяча юнитов идёт к одной точке. Если для каждого считать A* — тысяча независимых поисков за кадр. Дороговато.

Как нам сделать меньше расчётов? По своей сути, идея проста. Можно сделать один расчёт вместо тысячи. Посчитали поле — все юниты просто читают из него «куда идти из своей клетки».

Разбиваем карту на сетку. От цели обратной волной (Dijkstra) в каждой клетке считаем дистанцию до цели и записываем вектор на соседа — это и есть flow field. Юниту достаточно прочитать вектор из своей клетки. O(1) на запрос, без зависимости от длины пути и количества юнитов.

«А если цель движется?» В RTS — почти никогда. Клик в точку, поход к зданию — цель статична, поле живёт минутами. При движущейся цели перерсчитать получается в любом случае не так дорого. Одну дейкстру пустить по карте не так долго, как для каждого юнита считать А*. Тем более с шумом от boids там не обязательно моментальная реакция на пользовательский ввод или триггеры.

Проблема возникает если много юнитов и у каждого своя цель — A* снова в выигрыше. Flow fields — это про движение толпы к общей цели. Канонический разбор — Elijah Emerson, AI Game Programming Wisdom 5 (2008).

#мат_геймдев #МатРазбор #algorithms #AI