Jump Point Search: Fast A* Pathfinding for Uniform Cost Grids

In 2011, at the 25th National Conference on Artificial Intelligence. AAAI, Daniel Harabor and Alban Grastien presented their paper “Online Graph Pruning for Pathfinding on Grid Maps”.This article explains the Jump Point Search algorithm they presented, a pathfinding algorithm that is faster than A* for uniform cost grids that occur often in games.What to know before readingThis article assumes you know what pathfinding is. As the article builds on A* knowledge, you should also know the A* algorithm, including its details around traveled and estimated distances, and open and closed lists. The References section lists a few resources you could study. The A* algorithm aims to find a path from a single start to a single destination node. The algorithm cleverly exploits the single destination by computing an estimate how…


Link to Full Article: Jump Point Search: Fast A* Pathfinding for Uniform Cost Grids