(If you aren’t familiar with A*, check out this post first. JPS is a modification to A*, and just adds efficiency to the existing algorithm)
A* will add most/all of the steps along these paths to a list of usable steps, which takes a lot of computation on large searches. This is particularly true for large open spaces, where A* may add most of the map to the open/closed lists.
A* Node Pruning
There are several optimizations for A* that use node pruning methods, (i.e. lower the amount of steps added to the list) to make A* run more quickly. Jump Point Search (JPS), created by Daniel Harabor and Alban Grastien, is an excellent optimization for A*.
Jump Point Search avoids creating these large, computationally intensive lists by only adding to the lists when it detects a corner or the destination. It does (in general) evaluate more blocks than A*. For most cases, the extra evaluation in JPS is much faster than the extra list manipulation in A*.
This means that with the JPS worst case scenario you normally break even with A* in terms of processing time. For large open spaces, A* quickly becomes much slower than JPS to generate an optimal path.
The Jump Point Search Algorithm
If you think about leaving a room for another room in a house, the shortest path is from your start position, to the corner at the door, through the hall, to the corner at the target room’s door, to your end position.
With JPS, you can calculate an optimal path while adding only the places where you need to turn to the lists. Any straight path just runs from start, to each turn, to finish, disregarding all other intermediate steps.
The next step then, is how do we decide how to expand (look through) the search area and find corners to turn at?
The method by which JPS expands its search is luckily a fairly simple rule set:
Rule 1. Can I get to the desired block symmetrically from another path?
If yes proceed to rule 2.
If no this is an optimal path.
Rule 2. Does the path I am using go through a diagonal move before other paths do?
If yes, this is an optimal path.
If no, this is not an optimal path.
Cardinal and diagonal directions in a hexagonal coordinate system
Lets unpack these two a little with some examples.
This classification of diagonal is arbitrary. Why can’t diagonal be up, down, left, and right? Well it can, which makes deciding on a direction system for a hexagonal grid much easier.
Note: You cannot pick consecutive directions as diagonals, diagonal directions are made up of their two neighbor directions- i.e. you can make a move up-right with a move in both up-left and right in this example.
Expanding along a cardinal direction
Let’s start with expansion in a cardinal direction: up-right. All blocks can be walked on.
Therefore, neither of those blocks (gray) can be our next optimal path move.
That means that it takes the same number of moves to get there from a different block as it does through our current block. Also, if you take a path through the other block, there is a diagonal move first (rule 2), so those paths are preferred.
This means that continuing along in the same cardinal direction gives the optimal path.
This continues until we have a blockage:
Once we determine we can no longer keep going, this expansion is discarded and we start expanding the next block on the open list.
The other possible outcome is a “forced neighbor” (corner):
1. Up-left is a forced neighbor, therefore you are at a corner, and need to add the current block to the open list. It is a forced neighbor because the only optimal path lies through the current block due to the impassible block.
2. Once you add a block to the open list, end the expansion and start from the next block in the open list.
When we next expand, we need to check in the up-left direction and the up right direction.
You can even have this:
That means that moving through this block is optimal, so you add this to the open list, then later expand in the other two directions.
However, the preference is for diagonal moves first (rule 2), so the current block is preferred as the optimal path.
This boils down to a few observations:
1. Expanding along a cardinal direction, you proceed until you detect a blockage or a corner. If you detect a corner, add to the open list. Remember that you need to know the corner block’s “parent”, in this case Start.
2. While expanding along a diagonal direction, it is (sort of) composed of cardinal checks:
Also, when a corner is detected along a cardinal in this way, you add the current block along the diagonal line to the open list.
Expand from there by checking the two cardinals (one of which will yield the corner to add to the open list) and moving diagonally until you detect another corner.
Once you have added the destination to the open list, move it to the closed list and access its parent (previous diagonal block). Repeat checking the parent for each block to build the list for the optimal path.
As you can see, with small areas, or areas with lots of corners, JPS still adds many of the blocks to the closed/open lists. In areas with more open space, the performance advantage of JPS quickly pulls ahead.
As you can see, compared to the first figure that shows the A* pathfinding method, JPS has 3 points in the list- Start, the turn point, and finish; while the A* version has 12. Over long paths this can very quickly turn into a substantial time savings, allowing your program to run much faster.
Here is a working demo, so you can see the effects of the different search types in action. It is made in Unity3D with C#.
WASD: Move forward,backward, left, right; use mouse to aim
E is designate movement target
Q is replay block selection (shows the order in which blocks are picked)
Spacebar removes a block
A*/JPS toggle: calculates the path with the basic A* algorithm or with JPS optimization added
Location/Score toggle: Shows the (x,y) coordinate system, or the F,G,H scores used to calculated block selection
Block Changes/Calc Time toggle: Shows highlighted blocks to give a visual sense of how the path is determined, or pops up a window that gives the time required to calculate a path in both basic A* and JPS versions.
The code is could probably use a bit more optimization, but it is a decent example of the speed differences possible. Try having the character move to an opposite corner to see the increased performance of JPS vs A*.
Code for terrain generation is a modification of AlexSTV’s voxel generator tutorial
Most of my implementation of the Hexagon JPS algorithm is based off of Nathan Witmer’s explanation of the square version.
All of this is of course based off Daniel Harabor and Alban Grastien’s work on pathfinding optimizations. They do actually have another even better optimization called JPS+, which I may or may not write up later.
Open List: List of all blocks to be considered for the optimal path
Closed List: List of all blocks that have been checked to see if they are on the optimal path.