Game AI Pro 3

23

Faster Dijkstra Search on Uniform Cost Grids

Nathan R. Sturtevant and Steve Rabin

23.1    Introduction

23.2    Decomposing Jump Point Search

23.3    Canonical Dijkstra

23.4    Conclusion

References

23.1  Introduction

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 (Rabin and Sturtevant 2013), influence maps, or other analysis. In this chapter, we describe how we borrowed recent ideas from Jump Point Search (JPS) (Harabor and Grastien 2011) to significantly speed up Dijkstra search on uniform cost grids. We call this new algorithm Canonical Dijkstra. Although the algorithm has been described before ...