What to know before readingThis article assumes you know what pathfinding is. As the article builds on A* knowledge, you should also know the A* algorithm, including its details around traveled and estimated distances, and open and closed lists. The References section lists a few resources you could study.
The A* algorithmThe A* algorithm aims to find a path from a single start to a single destination node. The algorithm cleverly exploits the single destination by computing an estimate how far you still have to go. By adding the already traveled and the estimated distances together, it expands the most promising paths first. If your estimate is never smaller than the real length of the remaining path, the algorithm guarantees that the returned path is optimal.
Jump point search algorithmThe JPS algorithm improves on the A* algorithm by exploiting the regularity of the grid. You don't need to search every possible path, since all paths are known to have equal costs. Similarly, most nodes in the grid are not interesting enough to store in an open or closed list. As a result, the algorithm spends much less time on updating the open and closed lists. It potentially searches larger areas, but the authors claim the overall gain is still much better better due to spending less time updating the open and closed lists.
The algorithmThe JPS algorithm builds on the A* algorithm, which means you still have an estimate function, and open and closed lists. You also get the same optimality properties of the result under the same conditions. It differs in the data in the open and closed lists, and how a node gets expanded. The paper discussed here finds paths in 2D grids with grid cells that are either passable or non-passable. Since this is a common and easy to explain setup, this article limits itself to that as well. The authors have published other work since 2011 with extensions which may be interesting to study if your problem is different from the setup used here. Having a regular grid means you don't need to track precise costs every step of the way. It is easy enough to compute it when needed afterwards. Also, by exploiting the regularity, there is no need to expand in every direction from every cell, and have expensive lookups and updates in the open and closed lists with every cell like A* does. It is sufficient to only scan the cells to check if there is anything 'interesting' nearby (a so-called jump point). Below, a more detailed explanation is given of the scanning process, starting with the horizontal and vertical scan. The diagonal scan is built on top of the former scans.
Horizontal and vertical scanHorizontal (and vertical) scanning is the simplest to explain. The discussion below only covers horizontal scanning from left to right, but the other three directions are easy to derive by changing scanning direction, and/or substituting left/right for up/down.
def search_hor(self, pos, hor_dir, dist): """ Search in horizontal direction, return the newly added open nodes @param pos: Start position of the horizontal scan. @param hor_dir: Horizontal direction (+1 or -1). @param dist: Distance traveled so far. @return: New jump point nodes (which need a parent). """ x0, y0 = pos while True: x1 = x0 + hor_dir if not self.on_map(x1, y0): return  # Off-map, done. g = grid[x1][y0] if g == OBSTACLE: return  # Done. if (x1, y0) == self.dest: return [self.add_node(x1, y0, None, dist + HORVERT_COST)] # Open space at (x1, y0). dist = dist + HORVERT_COST x2 = x1 + hor_dir nodes =  if self.obstacle(x1, y0 - 1) and not self.obstacle(x2, y0 - 1): nodes.append(self.add_node(x1, y0, (hor_dir, -1), dist)) if self.obstacle(x1, y0 + 1) and not self.obstacle(x2, y0 + 1): nodes.append(self.add_node(x1, y0, (hor_dir, 1), dist)) if len(nodes) > 0: nodes.append(self.add_node(x1, y0, (hor_dir, 0), dist)) return nodes # Process next tile. x0 = x1Coordinate (x0, y0) is at the parent position, x1 is next to the parent, and x2 is two tiles from the parent in the scan direction. The code is quite straightforward. After checking for the off-map and obstacle cases at x1, the non-passable and passable checks are done, first above the y0 row, then below it. If either case adds a node to the nodes result, the continuing horizontal scan is also added, all nodes are returned. The code of the vertical scan works similarly.
Diagonal scanThe diagonal scan uses the horizontal and vertical scan as building blocks, otherwise, the basic idea is the same. Scan the area in the given direction from an already covered starting point, until the entire area is done or until new jump points are found.
def search_diagonal(self, pos, hor_dir, vert_dir, dist): """ Search diagonally, spawning horizontal and vertical searches. Returns newly added open nodes. @param pos: Start position. @param hor_dir: Horizontal search direction (+1 or -1). @param vert_dir: Vertical search direction (+1 or -1). @param dist: Distance traveled so far. @return: Jump points created during this scan (which need to get a parent jump point). """ x0, y0 = pos while True: x1, y1 = x0 + hor_dir, y0 + vert_dir if not self.on_map(x1, y1): return  # Off-map, done. g = grid[x1][y1] if g == OBSTACLE: return  if (x1, y1) == self.dest: return [self.add_node(x1, y1, None, dist + DIAGONAL_COST)] # Open space at (x1, y1) dist = dist + DIAGONAL_COST x2, y2 = x1 + hor_dir, y1 + vert_dir nodes =  if self.obstacle(x0, y1) and not self.obstacle(x0, y2): nodes.append(self.add_node(x1, y1, (-hor_dir, vert_dir), dist)) if self.obstacle(x1, y0) and not self.obstacle(x2, y0): nodes.append(self.add_node(x1, y1, (hor_dir, -vert_dir), dist)) hor_done, vert_done = False, False if len(nodes) == 0: sub_nodes = self.search_hor((x1, y1), hor_dir, dist) hor_done = True if len(sub_nodes) > 0: # Horizontal search ended with a jump point. pd = self.get_closed_node(x1, y1, (hor_dir, 0), dist) for sub in sub_nodes: sub.set_parent(pd) nodes.append(pd) if len(nodes) == 0: sub_nodes = self.search_vert((x1, y1), vert_dir, dist) vert_done = True if len(sub_nodes) > 0: # Vertical search ended with a jump point. pd = self.get_closed_node(x1, y1, (0, vert_dir), dist) for sub in sub_nodes: sub.set_parent(pd) nodes.append(pd) if len(nodes) > 0: if not hor_done: nodes.append(self.add_node(x1, y1, (hor_dir, 0), dist)) if not vert_done: nodes.append(self.add_node(x1, y1, (0, vert_dir), dist)) nodes.append(self.add_node(x1, y1, (hor_dir, vert_dir), dist)) return nodes # Tile done, move to next tile. x0, y0 = x1, y1The same coordinate system as with the horizontal scan is used here as well. (x0, y0) is the parent position, (x1, y1) is one diagonal step further, and (x2, y2) is two diagonal steps. After map boundaries, obstacle, and destination-reached checking, first checks are done if (x1, y1) itself should be a jump point due to obstacles. Then it performs a horizontal scan, followed by a vertical scan. Most of the code is detection that a new point was created, skipping the remaining actions, and then creating new jump points for the skipped actions. Also, if jump points got added in the horizontal or vertical search, their parent reference is set to the intermediate point. This is discussed further in the next section.
Creating jump pointsCreating jump points at an intermediate position, such as at b2 when the horizontal or vertical scan results in new points has a second use. It's a record of how you get back to the starting point. Consider the following situation
Starting pointFinally, a small note about the starting point. In all the discussion before, the parent was at a position which was already done. In addition, scan directions make assumptions about other scans covering the other parts. To handle all these requirements, you first need to check the starting point is not the destination. Secondly, make eight new jump points, all starting from the starting position but in a different direction. Finally pick the first point from the open list to kick off the search.
PerformanceI haven't done real performance tests. There is however an elaborate discussion about it in the original paper. However, the test program prints some statistics about the lists
Dijkstra: open queue = 147 Dijkstra: all_length = 449 A*: open queue = 91 A*: all_length = 129 JPS: open queue = 18 JPS: all_length = 55The open/closed list implementation is a little different. Rather than moving an entry from the open to the closed list when picking it from the open list, it gets added to an overall list immediately. This list also knows the best found distance for each point, which is used in the decision whether a new point should also be added to the open list as well. The all_length list is thus open + closed together. To get the length of the closed list, subtract the length of the open list. For the JPS search, a path back to the originating node is stored in the all_length list as well (by means of the get_closed_node). This costs 7 nodes. As you can see, the Dijkstra algorithm uses a lot of nodes in the lists. Keep in mind however that it determines the distance from the starting point to each node it vists. It thus generates a lot more information than either A* or JPS. Comparing A* and JPS, even in the twisty small area of the example search, JPS uses less than half as many nodes in total. This difference increases if the open space gets bigger, as A* adds a node for each explored point while JPS only add new nodes if it finds new areas behind a corner.
ReferencesThe Python3 code is attached to the article. Its aim is to show all the missing pieces of support code from the examples I gave here. It does not produce nifty looking pictures. Dijkstra algorithm Not discussed but a worthy read.
- (Article at Gamedev) http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/dijkstras-algorithm-shortest-path-r3872
- (Article at Gamedev) http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003
- (Wikipedia on JPS) http://en.wikipedia.org/wiki/Jump_point_search
- (Published article) http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf
- 20151024 First release