A Complete Subgoal Graph Method for Ultra-Fast Pathfinding

Abstract

I introduce a new method for ultra-fast pathfinding on octile grids, called the Complete Subgoal Graph algorithm (CSG). This algorithm has much faster preprocessing times than similar algorithms, and also slightly faster online runtimes. The biggest drawback is that it requires a relatively large amount of memory, although this memory requirement is comparable to that used by certain other algorithms, such as Topping. I propose some ideas for future improvement in terms of reducing this memory requirement. CSG is specifically designed for pathfinding on octile grids, although extensions to other graphs may be possible in the future. Octile grids are essentially a discretisation of 2-D Euclidean space, and are commonly used as an approximation to 2-D Euclidean space, because they are more convenient to work with. In addition, CSG is mainly focused on applications to the kinds of maps found in video games, as this is a common application for pathfinding algorithms. The main pieces of work that CSG builds upon are Subgoal Graph algorithms and Compressed Path Databases (CPDs). CSG can essentially be viewed as building a CPD on top of a subgoal graph, in order to remove search from the subgoal graph. In order to ensure that the online runtime of CSG is competitive with existing algorithms, I needed to make certain improvements. One of the improvements involves taking into account the fact that passing through a subgoal will only be optimal if you are entering from certain directions and leaving in certain directions. I also borrow the idea of bounding boxes and apply them to my algorithm.