Speeding up FastMap for Pathfinding on Grid Maps

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.