Как работает поиск пути в видеоиграх RTS?

В таких играх, как Warcraft 3 или Age of Empires, возможности ИИ-противника передвигаться по карте кажутся почти безграничными. Карты огромны, и позиции других игроков постоянно меняются.

Как работает поиск путей ИИ в подобных играх? Стандартные методы поиска по графу (такие как DFS, BFS или A *) кажутся невозможными в такой настройке.