Я не знаю, пробовали ли вы этот вариант, основанный на утверждениях:
1. полностью вся карта игрового мира изменяется не сильно
2. обычно карту можно попытаться поделить на зоны или в тупом варианте ячейки (или точнее варианты перемещения между ними), которые так же меняются очень редко и не сильно
Простейший пример: пусть зоны — просто квадратные ячейки внутри простой сетки, размер ячейки сравним со средним размером препятствия на карте.
Более сложный пример: многоугольная область поделена на зоны по границам больших препятствий, и перпендикулярно пересекающие типичные пути движения юнитов (грубо говоря магистрали их движения), такую статистику в процессе игры собрать не сложно, сложнее выбрать размер зоны, как враиант — фиксировать количество таких зон от среднего количества юнитов в игре…
Тогда из соседних ячеек пути перемещения обычно либо в обход через соседние ячейки либо через соединяющую грань между этими двумя.
Размеры ячеек должны быть подобраны таковыми, чтобы вмещать некоторое (не сильно большое) количество препятствий… десятки или сотни.
Заранее просчитываем (и постепенно обновляем по мере изменения мира, это не обязательно делать в реальном времени, хотя тогда будут возможны забавные артефакты в движениях) возможные пути перемещения между такими зонами (каждая грань — список пересекаемых зон возможными путями), а в момент, когда необходим точный путь, просчитываем его только в пределах этих ячеек, добавив в алгоритм поиск точки на грани между ячейками, ближайшей к пути (та еще задачка).
Весь путь считать не актуально, достаточно рассчитывать в пределах 1-2 ячеек вперед (по уже известным вам алгоритмам) и получать ответ, есть ли вообще возможность попасть к цели. Добавить к алгоритму пересчет пути в зависимости от игровых объектов актуальных для расчета коллизий (тут проблема — возможны ли заторы).
Такие ячейки — это аналог памяти юнитов о том, как можно было бы примерно пройти в соответствующую зону.
Добавит даже больше реализма, например поведение при заторах, юнит как бы еще не видит что путь впереди закрыт, но послушно топает, пока не попадет в ячейку с этим затором… тогда возникнет событие что путь достигнуть нельзя… так как меду ячейками вариантов перемещения всегда несколько, это создает не один путь перемещения по ячейкам несколько, соответственно временно помечаем что путь закрыт и выбираем следующий.
