In parts two and three I will give a technical overview of both RSR and JPS, discussing their strengths, weaknesses and observed performance on two popular videogame benchmarks kindly made available by Nathan Sturtevant and BioWare: Baldur’s Gate II and Dragon Age: Origins.
Please note: this work was developed in conjunction with my coauthors: Adi Botea, Alban Grastien and Philip Kilby. It forms part of my doctoral research into pathfinding at NICTA and The Australian National University. Electronic copies of the papers mentioned in this article are available from my homepage.
Path Symmetries
A simple gridbased pathfinding problem. For simplicity (but not in general) we allow only straight moves and not diagonal. Many optimal length paths could be returned as the solution; we highlight only a few. Notice that each one is a permutation of all the others. In such cases we say that a symmetry exists between the paths.
Before proceeding further it is necessary to establish some precise terminology. For example: what exactly is a path? Traditionally, Computer Scientists define paths as ordered sequences of connected edges. The conjunction of these edges represents a walk in the search graph from some arbitrary start location to some arbitrary goal location. However this definition is too general to capture the idea of symmetry in grid maps. For that, we need a slightly different notion of a path:
A path in a grid map is an ordered sequence of vectors, where each vector represents a single step from one node on the grid to an adjacent neighbouring node.
The distinction between edges and vectors is an important one as it allows us to distinguish between paths that are merely equivalent (i.e. of the same length) and those which are symmetric. But what, exactly, does it mean to have a symmetric relationship between paths?
Two grid paths are symmetric if they share the same start and end point and one can be derived from the other by swapping the order of the constituent vectors.
As a clarifying example, consider the problem instance in Figure 1. Each highlighted path is symmetric to the others since they all have the same length and they all involve some permutation of 9 steps up and 9 steps right.
In the presence of symmetry a search algorithm such as A* is forced to explore virtually every location along each optimal path. In Figure 1, depending on how we break ties, A* might expand every node on the entire map before reaching the goal. Further, A* will usually consider many other nodes that appear promising but that are not on any optimal path. For example, each time A* expands a node from the fringe of the search, it has already likely found almost every symmetric shortest path leading to that node (again, depending on how we break ties when two nodes appear equally good). But this effort is in vain if these expansions do not lead the search closer to the goal and instead into a deadend. Thus arises the question which I will attempt to answer in this article: how do we deal with symmetry when pathfinding on grid maps?
Existing Methods For Speeding Up Search
A large number of techniques have been proposed to speed up pathfinding. Most can be classified as variations on three themes:

Reducing the size of the search space through abstraction.
Algorithms of this type are fast and use little memory but compute paths which are usually not optimal and must be refined via further search. Typical examples: HPA* [2], MMAbstraction [9].
 Improving the accurary of heuristic functions that guide search.
Algorithms of this type usually precompute and store distances between key pairs of locations in the environment. Though fast and optimal, such methods can incur signficant memory overheads which is often undesirable. Typical examples: Landmarks [6], True Distance Heuristics [10].

Deadend detection and other statespace pruning methods.
Algorithms of this type usually aim to identify areas on the map that do not need to be explored in order to reach the goal optimally. Though not as fast as abstraction or memory heuristics, such methods usually have low memory requirements and can improve pathfinding performance by several factors. Typical examples: Deadend Heuristic [1], Swamps [8], Portal Heuristic [7].
My work in this area can be broadly classified as a search space pruning technique. Where it differs from existing efforts is that, instead of trying to identify areas that do not have to be crossed during search, I aim to identify and prune symmetric nodes that prevent the fast exploration of an area. This idea nicely complements existing searchspace reduction techniques and, as it turns out, also complements most gridbased abstraction methods and memory heuristic approaches.
Rectangular Symmetry Reduction and Jump Point Search
My coauthors and I have developed two distinct approaches for explicltly identifying and eliminating path symmetries on grid maps. I outline them here very briefly and in more detail in an upcoming post:

Rectangular Symmetry Reduction (RSR).
RSR [4][5] can be described as a preprocessing algorithm which identifies symmetries by decomposing the grid map into empty rectangular regions. The central idea, then, is to avoid symmetries by only ever expanding nodes from the perimeter of each rectangle and never from the interior.

Jump Point Search (JPS).
JPS [3] consists of two simple neighbour pruning rules that are applied recursively during search. Each rule considers the direction of travel to a given node from its parent (either a straight step or a diagonal step) in order to prune the set of local neighbours (tiles) around that node. The central idea is to avoid any neighbours that could be reached optimally from the parent of any given node. In this way we are able to identify and avoid, onthefly, large sets of symmetric path segments; such as those in Figure 1.
RSR can preprocess most maps in under a second and has a very small memory overhead: we need to keep only the id of the parent rectangle each node is associated with (and the origin and dimensions of each such rectangle). By comparison, JPS has no preprocessing requirements and no memory overheads. Both algorithms are optimal and both can speed up A* by an order of magnitude and more. Figure 2 shows a typical example; For reference, I also include a screenshot for vanilla A*. You can click on each image to make it larger.
All nodes marked red must be expanded before the optimal path to the goal (marked in blue) is found. Notice that, in the case of A*, many nodes on the fringe of the search (i.e. on the edge of the red area) can only be reached by paths that cross large regions of empty space. These paths usually have many symmetric alternatives and considering them all can require a substantial number of node expansion operations. RSR and JPS can detect and eliminate such symmetries and both reach the goal much sooner.
Next time I will explain, in more depth, the mechanical details of both RSR and JPS. In the meantime, electronic copies of the research papers in which RSR [4][5] and JPS [3] were originally described are available from my homepage.
If you have any questions or comments on this work, I’d be glad to hear from you. Please leave a message below or, if you prefer, drop me an email instead (my contact details are on the About page).
Continue to Part 2.
Continue to Part 3.
References
[1] Y. Björnsson and K Halldörsson Improved Heuristics for Optimal Pathfinding on Game Maps. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2006.
[2] A. Botea, M. Müller, and J. Schaeffer. Near Optimal Hierarchical Pathfinding. In Journal of Game Development (Issue 1, Volume 1), 2004.
[3] D. Harabor and A. Grastien. Online Graph Pruning for Pathfinding on Grid Maps. In National Conference on Artificial Intelligence (AAAI), 2011.
[4] D. Harabor, A. Botea, and P. Kilby. Path Symmetries in Uniformcost Grid Maps. In Symposium on Abstraction Reformulation and Approximation (SARA), 2011.
[5] D. Harabor and A. Botea. Breaking Path Symmetries in 4connected Grid Maps. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2010.
[6] A. V. Goldberg and C. Harrelson. Computing The Shortest Path: A* Search Meets Graph Theory. In SIAM Symposium on Discrete Algorithms (SODA), 2005.
[7] M. Goldenberg, A. Felner, N. Sturtevant and J. Schaeffer. PortalBased TrueDistance Heuristics for Path Finding. In Symposium on Combinatorial Search (SoCS), 2010.
[8] N. Pochter, A. Zohar, J. S. Rosenschein and A. Felner.
Search Space Reduction Using Swamp Hierarchies. In National Conference on Artificial Intelligence (AAAI), 2010.
[9] N. R. Sturtevant. MemoryEfficient Abstractions for Pathfinding. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2007.
[10] N. R. Sturtevant, A. Felner, M. Barrer, J. Schaeffer and N. Burch. MemoryBased Heuristics for Explicit State Spaces. In International Joint Conference on Artificial Intelligence (IJCAI), 2009.
Thank you for this excellent work. I am currently finishing up the path finding system for my game.
I use an approach similar to “Hierarchical Path Planning for MultiSize Agents in Heterogeneous Environments.”
Expect I have
1: extended the abstraction part to multiple levels.
2: used a version of bush fire that expands in multiple directions.
3: Each node has a terrain cost for different terrain types
4: nodes with low clearance values are more expensive.
Grid maps are from a game development standpoint very important and often over looked. They are one of the best ways to convey different terrain types and for some game types particularly role playing games and real time strategy games the best option in my option.
I am honestly loathed to go back and change my system. However I think these are very interesting and important papers. In a year or two when I plan to update / maintain my pathing system. I plan to read them rather intently.
The biggest problem I see if you only allow nodes with uniform cost. It seems like you are giving up the biggest advantage of grid maps. Namely, the ability to have verging terrain types effect path finding. You do not need a large difference in node cost 1.0 vs 1.05 to add up to a path with very different total cost.
It seems like you would be better served in uniform grid maps by preprocess the grid and eliminate open areas by reducing them to a single center node. You can do this in a way that is abstracted from the client program.
Comment by Guest — August 26, 2011 @ 18:53
Hi there! Thanks for posting.
It sounds like you’re doing some pretty interesting stuff; I wouldn’t mind hearing more about your game when you decide to make it public.
To answer your question: the current work is indeed specific to uniform cost maps. I chose to focus on this domain since it is simple to work with but also common enough that any results might be of interest to a reasonably large group of people. I agree however that a generalisation to weighted grids would make the current work more interesting. I hope to have some theoretical and empirical results on this very problem in the near future.
For the present, one simple suggestion is the following: divide your map into a set of connected components, each of which is uniformcost. For example: if you have a map involving plains, lakes and swamps, and each of these regions is uniform cost, you could simply apply either RSR or JPS to each region. In the case of JPS, simply stop the recursion when you find a tile that has a neighbour with a different terrain type. One small caveat: your speedup may not be very large if the size of each component is small. This is because both RSR and JPS exploit the fact that, when you cross a large uniformcost region, there are many symmetric path segments that each contains nodes with similar fcosts.
Regarding the centroid suggestion: that’s a nice idea. I believe Nathan Sturtevant implemented a similar system for the pathfinding system in Dragon Age: Origins. You can read about it in [9]. It is very fast and has low memory overheads but it is not, however, optimal. I think Nathan also needed to apply some clever refinement to the abstract path to prevent characters from navigating to the centre of large rooms before heading for the exit (this can look really weird if the movement introduces a large detour).
Comment by dharabor — August 27, 2011 @ 10:49
can i request for an algorithm or pseudocode for the dead end heuristic ?
Comment by Mark Catindig San Juan — September 4, 2011 @ 19:02
Hi Mark,
You can find a thorough description of that algorithm in the original paper (reference [1] at the end of this article). You can download an electronic version directly from the authors website here
Comment by dharabor — September 5, 2011 @ 17:46
[…] Fast Pathfinding via Symmetry Breaking (harablog.wordpress.com) […]
Pingback by A geek with a hat » Our intuitive understanding of distance fails us — September 7, 2011 @ 03:57
[…] Fast Pathfinding via Symmetry Breaking (harablog.wordpress.com) […]
Pingback by C++ Link: Astar Shortest Path Algorithm (C++ recipe) « Keith M. Programming — November 24, 2011 @ 11:28
[…] great pathfinding formula – to date I have find out about HPA* and A* with JPS, but to both I’ve not handled to locate an implementation, that is a problem since the […]
Pingback by Pathfinding for a lot of units, mostly random movement  Q&A System — July 1, 2012 @ 21:15