Notes of Grid-based PathFinding Algorithms
HPA* : Hiearchical Path Finding
- Article : "Near-Optimal Hierarchical Pathfinding (HPA*)" Alex J. Champandard. 2007
- Paper : "Near-Optimal Hierarchical Pathfinding" Adi Botea, Martin Muller, Jonathan Schaeffer. 2004
- Article : "Beyond A*: Speeding Up Pathfinding Through Hierarchical Abstraction"
- Paper, Memory : "Memory-Efficient Abstractions for Pathfinding" Nathan Sturtevant. 2007
- Slide, Memory : "Minimal Memory Abstractions" 2007
- Slide, Sims : "Artificial Intelligence in The Sims series" Yoann Bourse.
DHPA*, SHPA*
- Article : "Pathfinding in Static and Dynamic Environments and the Future of Multi-core HPA*" Alex J. Champandard. 2010
- Article : "SHPA*: Improving Hierarchical Pathfinding Performance by Maintaining A Static Hierarchy with HPA*" Alex Kring. 2010
- Paper : "DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds" 2010
JPS (Jump Point Search)
- Paper/Article : "Fast Pathfinding via Symmetry Breaking" 2012
- Paper : "Online Graph Pruning for Pathfinding on Grid Maps" 2011
- Article/Source : "How to Speed Up A* Pathfinding With the Jump Point Search Algorithm"
JPS+ : JPS with precompute
- Paper : "Improving Jump Point Search" 2014
- Slide/Source : "JPS+: Over 100x Faster than A*" GDC2015
Path LUT : Memory size O(N^2)
- "Proprocessed Solution for Open Terrain Navigation"AI Game Programming Wisdom
CPD (Path LUT) : Merge similar direction areas with rectangles
- "Ultra-Fast Optimal Pathfinding without Runtime Search" 2011
D*-Lite
- Slide : "Inside GlassBox" GDC2012
- Slide : "D* Lite and Dynamic PathFinding" 2009
PRA*
- Paper : "Partial Pathfinding Using Map Abstraction and Refinement"
HAA*
- Article : "Clearance-based Pathfinding and Hierarchical Annotated A* Search" 2009
Theta*
- Article : "Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments" Alex. 2010
- Paper : "Theta*: Any-Angle Path Planning on Grids" 2007