Jump Point Search for Hexagons

(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)

While A* is excellent at finding an optimal path, it has a problem with symmetry. Particularly that for any given path from point A to B, there are often multiple paths that are equivalent lengths.

Hex AStar

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.

rooms

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.

JPS Expansion

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.

Square Straight DiagonalFor the basic square type coordinates, diagonals are intuitive. Up-left, up-right, down-left, down-right are our diagonals.

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.

 

Hex Cardinal StraightGiven that the diagonals are arbitrary, I picked right, up-left, down-left as the diagonals, and left, down-right, and up-right as the “cardinal” directions.

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.

Hex Straight 1The start block (green) expands once in the desired direction.

 

 

 

 

Hex Straight 2v1 (2)Once we have moved, we notice that moving from the current block (yellow) left, or the current block down-right takes two moves from the start, and you can move to either one directly from Start.

Therefore, neither of those blocks (gray) can be our next optimal path move.

 

 

Hex Straight 3v1Next we can check up-left and right. These blocks are on a symmetrically optimal path from start.

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.

 

Hex Straight 4v1The last direction is up-right. Moving from start -> current -> up-right costs two moves, while any other move set costs at least three moves.

This means that continuing along in the same cardinal direction gives the optimal path.

 

 

This continues until we have a blockage:

Hex Straight blockedThe block in the up-right direction (black) is impassible.

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):

Hex Cardinal ForcedThe impassible block on the left means that two things:

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:

Hex Cardinal MultiBlockAlthough the path directly forward is blocked, there are two corners with paths next to them.

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.

 

 

Expanding Diagonally

Hex Diagonal 1We will start this example by moving right, a diagonal direction.

 

 

 

 

Hex Diagonal 2  First we check the rear two blocks, both are 1 move away from start, two moves if you go through the current block, therefore those paths are not optimal.

 

 

 

 

Hex Diagonal 3 This is where the diagonal expansion is different. Both top right and bottom right are two moves through the current block, and two moves otherwise.

However, the preference is for diagonal moves first (rule 2), so the current block is preferred as the optimal path.

 

Hex Diagonal 4 Now we check the final block on the right, and two moves through the current block is less than the three moves any other way, so we need to expand in that direction as well.

 

 

 

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.

Hex Cardinal Corner

2. While expanding along a diagonal direction, it is (sort of) composed of cardinal checks:

Hex Diagonal ChecksAs you can see, for each move diagonally, you do a check in each cardinal direction first before moving diagonally.

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.

 

Hex Diagonal ChecksThen restart by moving the current diagonal block from the open list to the closed 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.

 

Hex Diagonal 6Continue in this method until you reach the goal.

 

 

 

 

 

Hex Diagonal 7 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.

Hex AStar

Demo

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#.

Controls:

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*.

Notes:

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.

JPS Glossary

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.

Leave a Reply

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