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 [i]jump point[/i]). 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.
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.
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 [code] Dijkstra: open queue = 147 Dijkstra: all_length = 449 A*: open queue = 91 A*: all_length = 129 JPS: open queue = 18 JPS: all_length = 55 [/code] The 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 [tt]all_length[/tt] 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 [tt]all_length[/tt] list as well (by means of the [tt]get_closed_node[/tt]). 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