Today I will talk a bit about a pathfinding algorithm I researched during my internship at Gray Lake Studios. My original plan was to use A* in one of the generators for ProDnD but the algorithm was too slow for our use case. This triggered me to look into different pathfinding algorithms. I quickly bumped into JPS, an improved A* algorithm that at the expense of cost, increases performance by jumping over open areas.
JPS is actually an algorithm based on the widely known A* algorithm. It uses heuristic calculations to find the shortest path but is not able to jump through nodes with different costs so it only moves through valid types that all have the same cost. A* basically adds all node neighbors to an open list and pick the next node based on their current cost plus the heuristic calculation, JPS does the same thing but has to check fewer nodes because of a specific set of rules which I will explain now.
To successfully do jump in the Jump Point Search algorithm we apply 2 simple pruning rules that we check recursively during the search. One rule for straight and one for diagonal movement. When you check for a node on the right of the current node (like in the image above), you should only add the node immediately to the right of the current node. This always happens unless the node is unavailable or if bumps into a situation like in the image below. In this case it will also add node 3 that is right behind the forbidden node type, this is caused by the 2 rules that apply forced neighbors. If we didn’t add these forced node we could have the possibility that we never reach our destination node and if we do, that it’s probably not the “optimal” path. If horizontal searches fail we’ll continue searching diagonally. For diagonal movement we basically use the same rules as for horizontal movement, only when we move diagonal, we also check the nodes horizontally and vertically so we are able to find a corner situation where then again a forced neighbor will be added to the open list or if we find our destination node.
If you add up all these pruning and forced neighbor rules you’ll successfully do a jump with the algorithm like in the situations below.
To improve the speed of this algorithm even more in ProDnD, I make a world node for all the nodes in the final path. These world nodes describe the connections that are already existing between different parts of the map, so if you connect 2 parts of the map that are far away from each other there’s an algorithm that checks for pre-existing paths and connects to these. I use this algorithm in ProDnD to connect houses on a map because the only thing the algorithm needs to do when connecting 2 houses is to make sure that the path doesn’t go trough other houses. Because we don’t need cost in this case, it’s way cheaper to use JPS than it is to use A*. This way of connecting houses together with the node based pathfinding makes it a lot faster than regular A* pathfinding.
Hope you have learned a bit about Jump Point Search and how it works in general. For questions, please leave a comment or send me an e-mail!
Harabor, D., & Grastien, A. (n.d.). Improving Jump Point Search. NICTA and The Australian National University.
Xu, X. (n.d.). PathFinding.js. Retrieved November 20, 2015, from https://qiao.github.io/PathFinding.js/visual/