Central64 is a C++ library for approximating shortest paths through 2D grid-based environments. The library supports all combinations of the following options:
- Grids may have 4, 8, 16, 32, or 64 neighbors.
- Grids may use center or corner cell alignment.
- Grid paths may be regular or central.
- Grid paths may be found using A* Search, Jump Point Search, Bounded Jump Point Search, Mixed A*, or Mixed Jump Point Search.
- Grid paths may be post-processed using No Smoothing, Greedy Smoothing, or Tentpole Smoothing.
The Central64 library focuses on relatively basic grid-based navigation techniques in which a shortest grid path search is initiated from a source vertex and terminated (a) shortly after reaching a goal vertex or (b) after visiting all reachable nodes. The library does not include methods that require sophisticated precomputations to be performed on the environment. In other words, the library is dedicated to "online" path planning methods. The project also excludes "any-angle" path planning approaches that perform line-of-sight checks or travel cost interpolations during the search procedure. All paths produced by Central64 are generated by conducting a grid path search and then, if desired, smoothing the result.
One of the main purposes of the Central64 library is to analyze the performance of the central grid path planning approach, in which a path counting operation is used to select highly direct grid paths. Central grid path planning was introduced by Goldstein et al. (2022), who also presented an experiment focused primarily on the 8-neighborhood, the A* Search method, and the Greedy Smoothing algorithm. Central64 is a completely separate implementation of the central path approach. The Central64 library (1) supports all standard rectangular neighborhoods up to 64 neighbors, (2) applies path counting to alternative search algorithms including variations of Jump Point Search and two "mixed" search methods, and (3) introduces a more effective smoothing algorithm called Tentpole Smoothing.
This report explains the various path planning options supported by the Central64 library, and presents an experiment in which a total of 200 distinct variations of path planning methods are tested on the Dragon Age: Origins benchmark set. A number of findings and recommendations are put forward based on the results of the experiment as well as informal observations made during the development of the library.