ABSTRACT
In this chapter, the authors describe how they borrowed ideas from Jump Point Search (JPS) to significantly speed up E. Dijkstra search on uniform cost grids. They show that JPS is using a canonical ordering to avoid duplicates during search. Dijkstra search is commonly used for single-source shortest path computations, which can provide valuable information about distances between states for many purposes in games, such as heuristics, influence maps, or other analysis. One of the problems with search on grids is that there are many duplicate paths between states. Canonical Dijkstra is, in many ways, similar to JPS. The authors discuss the canonical ordering to generate states and searches over jump points. JPS can be seen as searching on an abstract graph defined by the jump points and the goal in the graph.
