Поля потока: общая цель без единственного жёсткого маршрута

Разделяйте дорогостоящий поиск к цели

Когда у многих юнитов одна цель, поле потока позволяет заменить повторные индивидуальные поиски маршрутов общими указаниями. Каждый юнит считывает направление около своей текущей позиции, поэтому смещение не обязательно требует построения нового полного пути. Повторно используемый результат всё равно относится к определённой цели и модели движения. Эмерсон описывает реализацию с тайлами; Патель объясняет лежащий в основе поиск от всех стартовых точек к одной цели. [1][2]

Разделяйте стоимость прохода, интеграцию и направление

Отделяйте стоимость входа на участок или его пересечения от интегрированной стоимости достижения цели. В дискретной графовой модели задайте D(goal) = 0 и решите D(x) = min(c(x,y) + D(y)) по допустимым исходящим рёбрам. При неотрицательных весах эти расстояния можно построить обратным поиском Дейкстры. Обходите обращённые рёбра, сохраняя их исходные стоимости в прямом направлении.

Явно храните признак недостижимости. Выбирайте допустимое исходящее направление по той же модели стоимости; простого следования к соседу с наименьшим сохранённым расстоянием недостаточно, когда веса рёбер различаются.

Расчётный пример: кратчайший остаток пути не всегда дешевле

На развилке маршрут A сначала стоит 8, после чего остаётся стоимость 1. Маршрут B сначала стоит 1, после чего остаётся стоимость 4. Итоги равны 8 + 1 = 9 и 1 + 4 = 5. Поле должно направить юнита к B, хотя оставшееся расстояние у A меньше.

Предположим, 200 юнитов имеют эту цель и один класс движения. Они могут использовать одно завершённое поле; это не означает, что разрешение столкновений или локальное управление тоже становится общим либо бесплатным. Условные стоимости и количество юнитов описывают проект, а не измеренное ускорение.

Постройте поле, которое можно проверить

Начните с небольшой карты со стеной, дорогой полосой местности и недоступным участком. Отдельно показывайте стоимости прохода, интегрированные значения и выбранные направления. Следуйте по стрелкам из каждой достижимой клетки и проверяйте прибытие без циклов. Убедитесь, что диагональные указания соблюдают те же правила углов, что и расчёт расстояний.

Связывайте кэшированные поля с целью, классом движения и соответствующей версией местности. Перестраивайте затронутые данные при исчезновении моста или изменении разрешения на проход. Публикуйте завершённые поколения поля целиком, чтобы юниты не считывали частично обновлённые расстояния и направления. Проверяйте переходы между тайлами и вход юнитов из неожиданных позиций.

Отдельно оценивайте повторное использование и физическое движение

Множество разных целей или классов движения уменьшает повторное использование и увеличивает объём кэша. Крупные клетки могут скрывать узкие проходы, а интерполированные векторы около стен — указывать сквозь препятствия. Поле задаёт направление маршрута; зазор для тела, разделение юнитов, движение через узкие места и занятость цели по-прежнему требуют явной обработки. Отдельно измеряйте построение поля, смену содержимого кэша, выборки и локальное движение, прежде чем оценивать реальную экономию от общего поля.

Источники

• [1] Crowd Pathfinding and Steering Using Flow Field Tiles — Elijah Emerson, Game AI Pro.
• [2] Flow Field Pathfinding for Tower Defense — Amit Patel, Red Blob Games.