Jump Point Search (JPS) Pathfinding Algorithm

Jump Point Search (JPS) Pathfinding Algorithm

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.

JPS neighbour pruning

Pruned neighbors of node x

 

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.

Forced neighbours

forced neighbors of node x

 

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.

Successful JPS jump

Successful straight and diagonal jumps with the JPS algorithm by applying pruning and forced neighbor rules.

 

Successful pathfinding with A*, checked nodes indicated

Successful pathfinding with A*, checked nodes indicated

Successful pathfinding with JPS, jump nodes indicated

Successful pathfinding with JPS, jump nodes indicated

 

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.

Castle JPS

Use of JPS for connecting houses within a castle

 

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!

References:

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/

Leave a Reply

Your email address will not be published. Required fields are marked *