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

[forhaxed]

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

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

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

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

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

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

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

[semenyakinVS]

Используй А*.

http://en.wikipedia.org/wiki/A*_search_algorithm

Там есть эвристика - она быстрая! Используй ту, которая диагонально-прямая, не помню как она называется - самая хорошая.

А чтобы всё было ещё быстрее - попробуй использовать порталы в помещения. Т. е., если есть дверь, можно улучшить поиск кэшируя прошлые результаты.

[GBee]

http://habrahabr.ru/blogs/algorithm/115689/#habracut правда для 6-угольников.

[Warlockus]

Используй A* с оптимизацией по Binary Heap и кешированием путей.