Jump Point Search, Faster Than A*

The A* search algorithm has long been a computer science industry benchmark for pathfinding, especially in games. This is because it is both very fast, and it returns optimal paths. Games often rely on less computationally expensive algorithms which return slightly suboptimal paths such as Hierarchical Pathfinding A*, or HPA*. However, recent work in the pathfinding field has produced an algorithm which returns optimal paths and is faster than conventional A*. This new method is called Jump Point Search, or JPS.

JPS was introduced by Daniel Harabor and Alban Grastien in their paper “Online Graph Pruning for Pathfinding on Grid Maps” in 2011 at the 25th National Conference on Artificial Intelligence. As outlined in their paper, JPS is a fast, grid specific algorithm which returns best paths, and requires no memory overhead. It figures out positions in the grid found in straight lines to “jump” to within a map so that it only has to “expand” certain nodes. These nodes are call jump points, the namesake of the algorithm. (1)

The key goal of JPS is to reduce the number of node operations needed to find an optimal path. It does so by taking advantage of path symmetry and using a technique called node pruning. Path symmetry refers to the fact that in grid based movement, many paths are often equal in cost, despite visiting different grid spaces, or nodes. (2)

path-symmetry

The importance of this symmetry is it means that not every ideal path needs to be explored to find one optimal path. This allows the JPS algorithm to remove, or prune, nodes which do not need to be visited, because it can be assumed that pathing to them from one node is just as efficient as another. (1) The diagram below shows how nodes are ignored. While traveling in a given direction, nodes on either side of the current node can be ignored, because it would be just as or more efficient to reach them from the parent as the current node. (2)

node-pruning

Now, this works well as long as there are no obstacles. However, as soon as their is an obstacle in front of the current path, we can ignore it entirely because we know a path above or below it will be at least as optimal instead. (2) The other very important factor is determining what Harabor and Grastien call forced neighbors. Any neighbor that is not pruned is a natural neighbor, because it makes sense to travel to it when going a given direction. Forced neighbors occur whenever there is an obstacle beside the current path which means nodes past it could not be reached without visiting the current node. The current node is then added as a new jump point, because it will need to be further explored. (1)

forced-neighbor

The above pruning rules apply when traveling in one of the four cardinal directions. Pruning behaves a bit differently when traveling diagonally. While nodes directly beside the current node closer to its origin can be ignored, and the neighbors touching the outer corners of the current node can be ignored, the direct neighbors in the direction of motion will be reached more quickly from the current node than the nodes to be pruned and should therefore be explored. (2)

diagonal-pruning

Additionally, forced neighbors are also slightly different when travelling diagonally, though they work much the same overall. Any time an obstacle is beside the current node, the nodes past said obstacle can only be reached through the current node, so it must now be marked for expansion. (2)

diagonal-forced-neighbor

The last key to understanding the algorithm is that when traversing diagonally it should jump in the horizontal and vertical directions closest to the current direction of the search. (1) In this way, any new jump points with forced neighbors will be discovered. This is necessary for the algorithm to find the optimal path. Below is a full diagram of what a search looks like with all jumps. (2)

full-jumps-path

To summarize why JPS is faster than A* and the key mechanics, it is primarily because it places so many fewer nodes on to the list of nodes to be expaneded, commonly referred to as the open list, during its search. By only adding jump points along the optimal path to the open list rather than every node in between and most neighbors, the time savings can be an order of magnitude or better. (3)

As to where JPS is useful in gaming, the answer is quite simple. Pathfinding is so ubiquitous in gaming the examples are innumerable. Any time an optimal pathfinding algorithm is needed for grid based searching, JPS is simply a faster alternative to A*, and therefore could be used in many gaming implementations. The original authors of the algorithm tested it using Baldur’s Gate and Dragon Age, as well as multiple map generating benchmarks. They discovered that JPS could easily be an order of magnitude faster than A*, and was even generally faster than HPA*, a suboptimal technique, as mentioned earlier. Below is an example of the same problem solved with A* on the left and JPS on the right. (1)

Further testing, especially with modified versions of JPS, have also tested in StarCraft, Dragon Age Origins, and Warcraft III. In every instance the algorithm was found to be many times faster than A* and most other algorithms which do not require precomputing time. Below is another example of A* against JPS. (4)

astar-jps-example

While JPS has a big speed advantage over A* and some other competitive algorithms, it definitely shows the most benefits in large open world scenarios, especially with few obstacles. It also tends to outperform other algorithms by a much higher factor in longer pathing problems. Due to the efficiency of the algorithm stemming from the straight line jumps, both of these points are logical, but worth noting. (3)

It is also worth noting again that JPS is really only meant to work in even cost grid based movement. It can be adapted to work with varied cost terrain by treating terrain cost changes as obstacles creating forced neighbors, but this has not been thoroughly explored. Additionally, JPS cannot be used with most nav meshes, or with irregular polygon maps. (4) However, a version has been developed for hexagonal pathing. (5) Work is also being done to discover other possible uses for JPS. (3)

Finally, while JPS is a fast algorithm, it is more difficult to implement than many others and may be overkill for many types of games. As with A*, if perfect pathing isn’t necessary and computational power is low, it may not be an ideal fit. The primary limitations of JPS are going to be runtime power and what type of space it is used in. Generally though, if optimal pathing is desired and a developer is looking for speed in a grid based game, JPS could be an ideal fit. A pathing technique which could actually usurp A* as the new gold standard in fast and optimal pathfinding.

large-path

Sources:

  1. http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3761/4007
  2. http://zerowidth.com/2013/05/05/jump-point-search-explained.html
  3. https://harablog.wordpress.com/2011/09/07/jump-point-search/
  4. http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than%20jps+%20goal%20bounding
  5. http://adityasubramanian.weebly.com/jump-point-search-on-hexagonal-grids.html

Additional Resources:

  1. https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm–gamedev-5818
  2. https://y4pp.wordpress.com/2014/06/04/pathfinding-a-jump-point-search/
  3. http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/
  4. http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220

Live Demos:

  1. http://zerowidth.com/2013/05/05/jump-point-search-explained.html
  2. http://qiao.github.io/PathFinding.js/visual/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s