Инди‑разработчик под ником NonPotato показал визуализацию и описал работу своего алгоритма тайлового обхода для генерации flow field (поля направлений для движения по сетке).
Алгоритм работает по тайлам и генерирует flow field, которое одновременно можно использовать как векторное поле. Для поддержки сложных уровней реализована мультикомнатная навигация: каждая четверть карты рассматривается как отдельная «комната», а тайлы каждой комнаты хранятся в отдельных массивах.
Система демонстрируется в замедленном виде, но, по словам автора, способна обрабатывать крупные раскладки (216 тайлов) примерно за 1 мс. Алгоритм имеет линейную временную сложность: производительность масштабируется прямо пропорционально количеству исследуемых тайлов.
Ключевая особенность — разбиение карты на секции с возможностью переиспользовать данные по комнатам. При пересчёте flow field обновляются только те комнаты, в которых реально изменился путь. Это снижает объём перерасчётов и делает систему особенно подходящей для динамически меняющихся карт.
Выводы
- Алгоритм генерирует flow field по тайлам и может использоваться как векторное поле для навигации.
- Карта делится на комнаты (квадранты), данные по тайлам хранятся в отдельных массивах.
- Линейная сложность: время работы растёт пропорционально числу тайлов.
- Пересчёт затрагивает только комнаты с изменившимся путём, что повышает эффективность.
