PathFinder : Benchmark
После внесения серьезных изменений в алгоритм «А» звезда (удалось отказаться полностью от списков, и тем самым операций splice), решил сделать тест производительности алгоритмов.
На время влияет расстояние между начальной и конечной точками(длина пути).
P.S.
На практике, нерационально использовать алгоритм Дейкстры, где граф имеет вид сетки.
На длинные расстояния требуется другой алгоритм.
Для ускорения алгоритм A* приходиться модифицировать согласно туториалу: http://www.policyalmanac.org/games/twoTiered.htm. Там вылезает много проблем. Такой алгоритм самый быстрый, однако требует предварительного расчёта карты.
На практике удобнее работать с байтмассивом, и путь выискивать градиентной “заливкой”, по которой можно восстановить путь.