Пытаюсь написать свой игровой AI для Top-down шутера.
Есть задача, поиск пути из точки А в точку B.
Совсем чуть-чуть погуглив, остановился на
алгоритме Дейкстры.
Т.е. берем все коллизии (в моем случае это обычные Rectangle)
И от каждого угла, отступаем 16 пикселей. Заносим их в вертексы (вейпоинты). После чего делаем trace-line из каждой точки ко всем точкам, если на пути нет коллизий - соединяем вейпоинты.
Все бы ничего, но поиск пути, в данном случае составляет около 151ms, что для реалтайма не есть круто.
Как вариант допускается использование как A* алгоритмов, так и потенциальных шагов
*. Необходимо обеспечить выполнение функции не более 3-5 ms.
Что посоветуете?
* Потенциальные шаги, в моем понимании, поиск пути на ходу. Т.е. он может его искать, даже если такого пути не существует.