Экономный алгоритм поиска пути.

[forhaxed]

Пытаюсь написать свой игровой AI для Top-down шутера.
Есть задача, поиск пути из точки А в точку B.
Совсем чуть-чуть погуглив, остановился на алгоритме Дейкстры.

Т.е. берем все коллизии (в моем случае это обычные Rectangle)

И от каждого угла, отступаем 16 пикселей. Заносим их в вертексы (вейпоинты). После чего делаем trace-line из каждой точки ко всем точкам, если на пути нет коллизий - соединяем вейпоинты.

Все бы ничего, но поиск пути, в данном случае составляет около 151ms, что для реалтайма не есть круто.

Как вариант допускается использование как A* алгоритмов, так и потенциальных шагов*. Необходимо обеспечить выполнение функции не более 3-5 ms.

Что посоветуете?

* Потенциальные шаги, в моем понимании, поиск пути на ходу. Т.е. он может его искать, даже если такого пути не существует.