ABSTRACT
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. This chapter borrows the recent ideas from Jump Point Search (JPS) to significantly speed up Dijkstra search on uniform cost grids. This new algorith is called as Canonical Dijkstra. One of the problems with search on grids is that there are many duplicate paths between states. The basic version of JPS does no pre-processing on the map before search. At runtime, it starts at the start state and generates a basic canonical ordering. JPS can be seen as searching on an abstract graph defined by the jump points and the goal in the graph. Canonical Dijkstra is, in many ways, similar to JPS. It uses the canonical ordering to generate states and searches over jump points.
