I’ve posted in the past about work done by Autodesk Research – in particular by Rhys Goldstein – to implement a more natural-seeming (but still direct and efficient) pathfinding algorithm. This is the algorithm at the heart of our Space Analysis package, and you can find details on how it works in these previous posts:
- A paper on our space analysis algorithm in the Journal of Artificial Intelligence Research
- Explaining how path counting helps simulate natural navigation
- Visibility in space analysis: an explainer
The above posts reference these articles/papers that have been published elsewhere:
- Path Counting for Grid-Based Navigation
- A short and direct walk with Pascal's Triangle
- A quick and clear look at grid-based visibility
While these are great (even if I do say so myself), Rhys really wanted to put something out there that helps people try this mechanism for themselves, and potentially evolve it and contribute to this area of research.
We’ve been working together to get a project called Central64 published as open source. Aliza Carpio has kindly published a blog post where Rhys and I talk with her about the Central64 project. You can find out about this and our other open source efforts at opensource.autodesk.com, by the way.
The source code for this project consists of a set of C++ headers that implement a variety of pathfinding algorithms (A*, Jump Point Search, Bounded Jump Point Search, Mixed A*, Mixed Jump Point Search, Dijkstra, Bounded Canonical Dijkstra, Mixed Dijkstra and Mixed Canonical Dijkstra) and allow you to explore the effect central pathfinding has on each of them.
If you want to jump ahead and see the results of running the code without actually doing so yourself, there’s a detailed technical report that includes awesome images and graphs such as these:
If you want to cut to the chase and find out which method is “best”, here’s the main recommendation:
Overall, 16-Neighbor Central Bounded Jump Point Search with Tentpole Smoothing is recommended as the investigated method that provides the best tradeoff between quality and speed.
If this reads like gibberish to you (and I really do sympathise if that’s the case) but you’re intrigued enough to try to unpack it, sections 2.1, 3.1-2 and 4.3 of the technical report should help.
Many thank to Rhys for putting together this valuable resource. It makes this interesting technique much more accessible, whether from an academic perspective or for developers to integrate into their own projects.