As you watch the video, you can have a look at the slides as PDF: download slides in a new tab here.
What is the Jump Point Search Algorithm?
The jump point search algorithm — or shorter JPS — is a variant of the A* search algorithm, optimized for pathfinding on grid maps, i.e., in computer games.
The jump point search algorithm is invented and published by Daniel Harabor and Alban Grastien in 2011.
It exploits path symmetry which is manifested as a path (or path segments) which share the same start and goal vertex, have the same length, and are otherwise identical, but differ in the scan order.
In the authors’ words, the algorithm is fast, optimal, and requires no memory overhead.
It identifies and selectively expands only vertices of interest, which are called jump points. This means that vertices between any two jump points are not expanded, or in our familiar terms, they remain unexplored.
This is a property that enables much faster algorithm operation by reducing the number of vertices that would otherwise have to be processed, e.g., by applying the original A* algorithm.
- Related Article: The A* Algorithm in Python
What is Its Purpose?
A common application of the jump point search algorithm is pathfinding, such as in computer games or possibly in navigation systems.
In general, whenever there is a search space that can be generalized to a uniform cost grid (all the paths to the neighbouring vertices are of equal cost), the jump point search algorithm is highly applicable.
How Does It Work?
The jump point search algorithm builds on the A* algorithm, which means that we still have a heuristic estimation function, and visited (open) and explored (closed) lists. We also get the same optimality properties of the result under the same conditions.
The algorithm operation differs in the data, specifically, in the visited and explored lists, and how a vertex gets expanded.
A* does not perform very well with big open fields, i.e. uniform cost grids, because it takes most of the time to process updates of the visited vertices.
On the other hand, the jump point search algorithm improves on the A* algorithm by exploiting the regularity of the grid, i.e., it does not need to search every possible path, since all paths are known to have equal costs.
???? In other words, most nodes in the grid are not interesting enough to be processed.
As a result, the jump point search algorithm spends much less time updating the visited and explored lists. It is sufficient to only scan the cells to check if there is a jump point nearby.
Instead of checking every neighbor from every possible vertex, the goal of each step in the scan is to decide whether the next point is interesting enough to create a new entry in the visited list.
If it is not, the algorithm continues the scanning iteration.
If a position is interesting enough, new jump points are recorded in the visited list, and the current scan iteration ends.
There are two cases of scan directions: horizontal/vertical and diagonal. Both cases are terminated when the scan runs into an obstacle (a non-passable vertex) or reaches the end of the search space.
Similarly, the scans yield a jump point if its search path passes beside an obstacle (black), as shown in the second and fourth pictures:
White numerated vertices represent valid neighbors of x, while grey vertices represent invalid neighbors of x.
We are simulating undirected uniform-cost grid maps by having each pair of vertices connected by the two edges of opposite directions. Each vertex has up to 8 neighbors and is either traversable or not.
Each horizontal or vertical scan, from a traversable vertex to one of its neighbors, has a cost of 1 and diagonal moves cost of √2.
To make it easier on the algorithm, we will use 10x whole numbers as a measure of distance. Therefore, instead of the cost √2 = 1.41421… we will use the cost of 14/2 = 7, and instead of the cost 1, we will use the cost of 10/2 = 5.
Moves involving obstacles (non-traversable) vertices are not allowed. Each direction is defined by a number from 0 to 7:
- Each double arrow represents two edges in opposite directions.
- The numbers are indicating the direction each edge is oriented in.
- The edge numeration enables us to use the
prune()function for neighbours pruning and forced neighbours detection, regardless of the movement direction.
What Are Its Properties?
As the jump point search algorithm builds on the A* algorithm, it also uses the exact information represented by the successive edges’ weights connecting the jump points and a heuristic function for distance estimation between the goal vertex and the jump points in a graph.
⭐ As the initial costs for all the jump points are set to infinity, the algorithm successively decreases jump points’ costs until they reach their minimum.
(1) Optimal: This behavior leads to a property of being optimal: minimal costs assigned to jump points enable the jump point search algorithm to always find the shortest path between the starting vertex and any jump point in the graph.
As the shortest paths always start from the starting vertex, the algorithm also belongs to the “single-source” algorithm.
(2) Complete: Besides being optimal, the algorithm is also complete, i.e. it will always take a finite time to find a solution.
(3) Optimal Efficiency: The third important property is the optimal efficiency, reflected in the fact that jump points positioned further from the goal vertex may not be explored at all, as their heuristic function distinguishes and delays the exploration of such jump points among those with equally weighted paths.
The heuristic functions used in the jump point search algorithm also inherit two notable properties from the A* algorithm: admissibility and consistency.
- Admissibility implies that the heuristic function cost estimation is at most as high as the lowest possible cost from the current point in a path towards the goal vertex.
- The consistent or monotone heuristic function is constrained by a requirement that its cost estimation is always less than or equal to the estimated distance from any adjoining, successor vertex to the goal, plus the cost of reaching that vertex.
How Is It Implemented?
The implementation of the jump point search algorithm is achieved by the function jps() and a modification of the underlying class Graph.
The jps() function takes three parameters:
- The
graphparameter as an initializedGraphobject (see the blog on the A* search algorithm, the section on graphs). - The
start_vertexparameter takes the starting vertex, which we choose freely (remember, a graph is not a tree, there is no absolute root). - The
goal_vertexparameter is the entity we want to find in the graph, enclosed in a vertex.
For a better understanding of the algorithm and its implementation, each step is precisely described in the code below.
There have been some further upgrades on the Graph class, in terms of the obstacle and direction properties, so its entire listing follows:
class Graph:
def __init__(self, directed=False):
self._outgoing = {}
# If the graph is undirected, 'self._outgoing'
# is the universal storage.
self._incoming = {} if directed else self._outgoing
# If the graph is directed, the 'self._incoming'
# dictionary differs from the 'self._outgoing'.
def is_directed(self):
return self._incoming is not self._outgoing
# The function returns a generator of incoming
# or outgoing (default) edges of a vertex.
def adjacent_edges(self, vertex, outgoing=True):
# References the corresponding outer dictionary
# (dictionary of dictionaries)
adj_edges = self._outgoing if outgoing else self._incoming
# Access each of the edges for this endpoint vertex.
for edge in adj_edges[vertex].values():
yield edge
def add_vertex(self, entity=None, h=None, cost=None):
# Constructs a new vertex from the entity.
vertex = self.Vertex(entity, h, cost)
# The vertex becomes a key in the outer dictionary,
# but the value is an internal dictionary (as we model
# both dimensions for each edge: origin and destination).
# e.g. {vertex_1a:{vertex_b:edge_a_b}, vertex_b:{vertex_c:edge_b_c}}.
self._outgoing[vertex] = {}
if self.is_directed():
self._incoming[vertex] = {}
def add_edge(self, origin, destination, weight=None, direction=None):
# Constr