Speeding up FastMap for Pathfinding on Grid Maps
Cong Hu, Quanjun Yin, Yue Hu, Junjie Zeng, Long Qin · 2019
FastMap algorithm can embed the nodes of a given edge-weighted undirected graph into a Euclidean space in near-linear time. And the Euclidean distance between two nodes in this space approximates the length of the shortest path between them in the given graph. We present a new variant of FastMap called FastMap with SPFA (FMS). FMS can be implemented in an easy way and its preprocessing time is less than the original version. Experimental results demonstrate that, although FMS has the same runtime performance with the former FastMap with Dijkstra's algorithm (FMD) when the generated heuristics are used in A*, FMS preprocesses much faster.