В статье на Habr разбирается классическая проблема навигации NPC в стратегиях, когда алгоритм поиска пути работает корректно, но юниты всё равно скапливаются перед узкими местами вроде ворот. Автор напоминает, что игровой код часто должен не столько быть физически правильным, сколько совпадать с ожиданиями игрока — тот же принцип, что и с койоттаймом или подкручиванием стрельбы.

Проблема проявляется при масштабировании: пока по карте идёт один солдат, никаких сложностей нет, но стоит добавить десять, пятьдесят или двести юнитов и одни ворота, как поведение ломается. Через ворота физически могут протиснуться лишь несколько юнитов одновременно, и толпа начинает тупить на месте, хотя маршруты давно найдены.

Причина в том, что навмешовые агенты получают одну и ту же команду бежать к одним воротам и честно строят маршруты, но по мере приближения к узкому месту пространство для манёвра схлопывается. Алгоритм вроде A* формально отработал, однако он не рассчитан на задачу согласования сотен агентов в одной точке.

Автор подчёркивает, что навигацию приходится хачить не меньше, чем физику прыжков, и разбираться уже не с состоянием персонажа, а с полигонами, узлами, рёбрами и стоимостями. Ключевой ориентир — не корректность поведения NPC, а то, как его воспринимает игрок.

В стратегиях у ботов обычно простая задача: пройти через ворота, обойти стену, оказаться во дворе. Именно на таких узких местах и вылезает разрыв между формально верным поиском пути и ожидаемым от NPC поведением.

Дальше автор, судя по всему, будет разбирать конкретные приёмы обхода этой проблемы — сглаживание потоков, локальное расталкивание или резервирование слотов у прохода.