In part one I introduced the notion of path symmetry: a property of uniform-cost grid maps which can significantly slow down optimal search. In this article I discuss Rectangular Symmetry Reduction (RSR for short): a new pre-processing algorithm that explicitly identifies and eliminates symmetries from uniform cost grid maps. RSR [1] [2] is simple to understand, quick to apply and has low memory overheads. When combined with a standard search algorithm, such as A*, RSR can speed up optimal pathfinding by anywhere from several factors to an order of magnitude. These characteristics make RSR highly competitive with, and in many cases better than, competing state-of-the-art search space reduction techniques.

Please note: this work was developed in conjunction with Adi Botea and Philip Kilby. It forms part of my doctoral research into pathfinding at NICTA and The Australian National University. Electronic copies of the papers in which these ideas were first described are available from my homepage.

## The Algorithm

(This remainder of this section, and the next, give a mechanical overview of the algorithm and its properties. If you’re impatient, or don’t care about such things, you can skip ahead and check out some screenshots.)

RSR can be described in 3 simple steps. Steps 1 and 2 are applied offline; their objective is to identify and prune symmetry from the original grid map. The third step is an online node insertion procedure; its objective is to preserve optimality when searching for paths in the symmetry-reduced grid map.

**RSR Step 1: Grid Decomposition**

**RSR Step 2: Addition of Macro Edges**

*macro edges*that connect each node on the perimeter of a rectangle with other nodes from the perimeter. In a 4-connected map (shown here for simplicity) a single macro edge between nodes on opposite sides of each rectangle will suffice. If diagonal moves are allowed, a set of macro edges (as described in [1]) will be needed instead.

**RSR Step 3: Online Insertion**

## Properties and Performance

- It preserves optimality.
- It has a small memory overhead in practice.
- Node insertion (Step 3) can be performed in constant time.
- It can speed up A* search by anywhere from several factors to an order of magnitude.

I will focus on points 2 and 4 in the remainder of this section. A thorough discussion of points 1 and 3 (including proofs) can be found in [1].

**Memory Requirements:**

In the most straightforward implement of RSR we need to store the id of the parent rectangle for each of the *n* traversable nodes in the original grid. We also need to store the origin and dimensions of each rectangle (macro edges can be identified on-the-fly and do not need to be stored explicitly). This means that, in the worst case, we might need to store up to *5n* integers. In practice however we can usually do much better. For example: there is little benefit in storing or assigning nodes to rectangles with few or no interior nodes (1×1, 2×1, 2×2, 3×2, 3×3 etc.). We can also avoid the parent id overhead altogether and only store the set of identified rectangles. The only downside is that, during insertion (Step 3 above), we now need to search for the parent rectangle of the start and goal — instead of being able to identify it in constant time.

**Performance:**

We evaluated RSR on a number of benchmark grid map sets taken from Nathan Sturtevant’s freely available pathfinding library, Hierarchical Open Graph. One of the map sets is from the game Baldur’s Gate II: Shadows of Amn. The other two map sets (Rooms and Adaptive Depth) are both synthetic, though the latter could be described as semi-realistic. I will give only a short summary of our findings; full results and discussion is available in the following papers: [1] [2].

In short: we observed that in most cases RSR can consistently speed up A* search by a factor of between 2-3 times (Baldur’s Gate), 2-5 times (Adaptive Depth) and 5-9 times (Rooms). In some cases the gain can be much higher: up to 30 times.

We found that the extent of the speed gains will be dependent on the topography of the underlying grid map. On maps that feature large open areas or which can be naturally decomposed into rectangular regions, RSR is highly effective. When these conditions do not exist, the observed speed gains are more modest. This performance is competitive with, and often better than, Swamps [4]; another state-of-the-art search space reduction technique. We did not identify a clear winner (each algorithm has different strengths) but did notice that the two methods are orthogonal and could be easily combined.

## Screenshots

**Figure 2: Search Effort.**

Comparative pathfinding examples from our experimental results. Images (a) to (c) are total nodes expanded by A* in order to find the optimal path to the goal (marked blue). Images (d) to (f) are total nodes expanded by A* + RSR. The respective domains are (from left to right): Baldur’s Gate, Adaptive Depth and Rooms. Notice that A* + RSR ignores many symmetric path segments and typically reaches the goal with much less effort.

## Next Time

## References

**[1]**D. Harabor, A. Botea, and P. Kilby.

*Path Symmetries in Uniform-cost Grid Maps.*In Symposium on Abstraction Reformulation and Approximation (SARA), 2011.

**[2]** D. Harabor and A. Botea. *Breaking Path Symmetries in 4-connected Grid Maps.* In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2010.

**[3]** D. Harabor and A. Grastien. *Online Graph Pruning for Pathfinding on Grid Maps.* In National Conference on Artificial Intelligence (AAAI), 2011.

**[4]** N. Pochter, A. Zohar, J. S. Rosenschein and A. Felner. *Search Space Reduction Using Swamp Hierarchies.* In National Conference on Artificial Intelligence (AAAI), 2010.

This is awesome stuff.

You can accelerate pathfinding on maps that contain open axis-aligned-rectangles – but what if a game has a similarly exploitable, but different pattern, diagonal rectangles, or trapezoids. If you simply apply the rectangle-based acceleration, you’ll get something (because the diagonal rectangles or trapezoids or whatever will contain rectangles), but not everything that you might get, with a customized heuristic.

Can you take a description of a pattern – for example, a set of Wang tiles – and precompute a pathfinding algorithm that will be fast if the input matches those tiles?

Comment by johnicholas — September 3, 2011 @ 00:52

Hi! Thanks for posting.

You make a good observation: sometimes rectangles are not the best choice for decomposing a map. The good news is that you could, in principle, apply any shape provided it is convex. Convexity is important as otherwise identifying symmetries becomes more difficult. The trick is finding a nice algorithm to identify maximally sized convex regions on the map. There are methods to do this from the computational geometry community but I never got around to playing with them.

Comment by dharabor — September 5, 2011 @ 17:43

People are suggesting adding this to Dwarf Fortress here: http://www.bay12forums.com/smf/index.php?topic=92732.0

Feel free to do tests on DF maps, which are 3D grids. You can find lots of interesting player-made maps there if you want more test data: http://mkv25.net/dfma/

I’m not sure, but I don’t see any reason why your technique wouldn’t generalize to 3D.

Comment by DF Player — September 12, 2011 @ 15:31

Hi DF Player,

Thank you for pointing out that thread. Very interesting! I’ll take a closer look at both it, and the maps you suggest, as soon as I get a chance.

Also, you’re right: the method should be straightforward to generalise to 3D environments; you just need to a slightly different set of natural and forced neighbours.

Comment by dharabor — September 12, 2011 @ 16:51