Hierarchical Clearance-based Pathfinding

In my last article I discussed Annotated A*, a search algorithm able to solve pathfinding problems for variable-sized agents with heterogeneous terrain traversal capabilities. Such problems are encountered in many modern video games which often feature different classes of units, each with distinct physical characteristics and navigational capabilities.

The story so far

Annotated A* operates on a grid map which is annotated with clearance values. A clearance value is simply a distance-to-obstacle metric that provides us with a useful indicator of how much traversable space there is at a given location. We can use clearances to quickly work out which parts of a map are traversable for an arbitrary agent by simply comparing the agent’s size with the clearance value associated with a particular location. Figures 1-3 show the associated clearance value annotations for 3 capabilities  on a small map with 2 traversable terrains: Ground (white tiles) and Water (blue tiles). A capability is defined as a set of terrains used to specify which parts of the environment are traversable for an agent.

Figure 1. Clearance value annotations for the {Ground} capability (only white tiles are traversable).

Figure 2. Clearance value annotations for the {Water} capability (only blue tiles are traversable).

Figure 3. Clearance value annotations for the {Ground, Water} capability (both white and blue tiles are traversable).

The problem at hand

In this second piece I want to discuss how to take this simple pathfinding system and speed it up significantly through the use of hierarchical abstraction. The main problem here is that a multi-terrain map annotated with clearance values contains lots of topographical information but abstraction methods can only hope to approximate the original. Thus, the goal is to build an abstraction which is representationally complete i.e. if a path between two points can be found on the original annotated map, we should be able to also find it using only the abstract map. To achieve this we’re going to attack the problem in 3 steps:

1. First, we divide our annotated map into a set of adjacent Clusters connected by Entrances. We will show that the resultant graph produced by this process is infact representationally complete but contains redundant and duplicated information.
2. Second, we compact the graph produced in the previous step using dominance techniques which identify and prune unnecessary nodes and edges. The resultant abstraction is shown to contain a minimal set of nodes and edges yet still retains the representational completeness properties of the original map.
3. Third, we describe the Hierarchical Annotated A* algorithm (HAA*) which we use to efficiently answer queries for a wide variety of agents with different sizes and terrain traversal capabilities. HAA* is shown to produce very high quality (i.e. near optimal) paths with comparatively little search effort vs. Annotated A*.

Clusters and Entrances

In order to create an an abstract representation of an annotated map we follow Botea et al and divide the environment into a series of discrete square-sized areas called clusters. Figure 4 shows the result of this step on our running example using clusters of size 5×5.

Figure 4. The map is divided into four 5x5 clusters.

Figure 5. (a) Three entrances are identified between clusters C1 and C3, one for each possible capability. (b) Each transition point (denoted by a strong dark line) maximises clearance for a particular capability.

Next, we identify entrances between each pair of adjacent clusters. An entrance is defined as an obstacle-free area of maximal size that exists along the border between two clusters (Figure 5a). Each entrance has associated with it a transition point which reflects the fact that an agent can traverse from one cluster to the other. To this end we select from each entrance a pair of adjacent tiles, one from each cluster, which maximise clearance (Figure 5b). Each transition point is represented in the abstract graph by two nodes connected with a single inter-edge of weight 1.0.  The inter-edge is also annotated with the corresponding capability and clearance value that reflect the traversability requirements of the transition point.

Figure 6. A complete initial abstraction.

Finally, we complete the abstraction by finding all possible ways to traverse each cluster. We achieve this by running Annotated A*  (AA*) between each pair of abstract nodes inside a cluster; one search for each combination of possible agent sizes and capabilities. Every time AA* successfully finds a path we add a new intra-edge between the start and goal nodes. The weight of the edge is equal to the length of the path and we further annotate it with the size and capability parameters used by AA* to reflect the traversability requirements of the path. This approach is highly effective at capturing all pertinent topographical details of the original map. Infact,  it is easy to see that the resultant graph (which is termed an initial abstraction) is representationally complete since we’ve identified all possible transitions between each pair of adjacent clusters and all possible ways to traverse each cluster (Figure 6).

Compacting the abstract graph

An interesting observation made during the abstraction-building process was that on many maps the same path was often returned by AA* when searching between the same pair of points with different sizes and capability parameters. This indicates that our abstract graph actually contains unnecessary or duplicated information (and is also needlessly large as a result). To solve this problem we’re going to apply two edge dominance approaches to prune unnecessary nodes an edges. I want to avoid describing these ideas formally (the details are in the paper) and instead focus on the intuition behind each one.

The first, termed strong dominance, states that if two edges, both of identical length,  connect the same pair of nodes and both are traversable by the same capability then we need only retain the one with the largest clearance. Figure 1 illustrates this idea. It is easy to see that using this approach preserves representational completeness; any agent able to traverse the edge with smaller clearance is also able to traverse the one with larger clearance. The resultant graph is termed a high-quality abstraction because we discard only duplicate information fromt the graph.

Figure 7. (a) Part of the initial abstraction for cluster C1. (b) Strong dominance removes edges E5 (dominated by E3) and E6 (dominated by E4).

Figure 8. (a) A graph with two inter-edges, E2 and E5. An agent traveling from "u" to "x" via E2 must both swim and walk whereas traveling via E5 only requires walking. (b) The dominated inter-edge, E2, and its endpoints, are removed.

The second approach, termed weak dominance, is focused on minimising the number of transitions between clusters. To achieve this the algorithm analyses pairs of inter-edges that connect the same two clusters and attempts to prove that if one is removed the representational completeness of the graph is maintained. The effect is that only transitions which are traversable by the largest number of agents are retained. This is similar to the way motorists frequently prefer to travel between locations via freeways, which are traversable by many kinds of vehicles, instead of opting for more direct offroad travel. Figure 8 illustrates this idea; again, it is easy to see that the application of weak dominance also preserves representational completeness. The resultant graph is termed a low-quality abstraction, to reflect the fact that some connectivity information is lost in the process.

Figure 9. The abstract graph after weak dominance is applied. Note that the graph is almost half the size compared to Figure 6.

Choosing which dominance technique to use will depend on the exact requirements of the target application. Empirical results have shown that in both cases the amount of memory required to store the abstract graph can be a small fraction of that required by the original map. (though the exact number depends on a range of factors which are discussed in the paper). Comparatively speaking, low quality abstractions can be more than 50% smaller than their high quality counterparts but there is a small tradeoff. In particular, high quality abstractions produce, on average, paths with lengths 3-5% longer than optimal while low quality abstractions are in the 6-10% range.

Hierarchical Annotated A*

The process of finding a path using an abstract graph is a straightforward one that will be familiar to anyone who has come across the HPA* algorithm:

1. Insert two temporary nodes into the abstract graph to represent the start and goal locations.  Connect these nodes to the rest of the graph by attempting to find a path to from the start/goal positions to every transition point in the local cluster.
2. Using A*, find a shortest path from the start to the goal in the abstract graph. At the end of the search, remove the two temporary nodes.

As with Annotated A*, the search algorithm from Step 2 is modified slightly to accept two extra parameters: the agent’s size and capability. In addition, the search function is also also augmented so that before a node is added to A*’s open list we first verify that it is infact reachable. In this case, a node is reachable only if the edge connecting it to the current node is traversable for the given size and capability parameters. The resultant algorithm is termed Hierarchical Annotated A* (HAA* for short).

As with other hierarchical planners, HAA* is shown to be very fast. I analysed its performance on a large set of problems (over 140K) using both small and large maps from Bioware’s popular RPG Baldur’s Gate. Since there are no similar pathfinding algorithms to measure against, it was  contrasted with Annotated A*. In short, HAA* is an order of magnitude faster and, even with my naive, non-optimised implementation, it was able to find solutions to most problems in ~6ms on average (tested on my Core2 Duo 2.16GHz MacBook, running OSX 10.5.2 with 2GB of memory).

Questions, source code etc.

So that about wraps things up. If you have any questions or comments on anything described in this or the previous article, please feel free to contact me. I also suggest checking out the original HAA* paper and associated presentation slides which contain more indepth discussion of these ideas. If you’d like to play with a working implementation, you can download the source code I wrote to evaluate the algorithm. It’s written in C++ and based on the University of Alberta’s freely available pathfinding library, Hierarchical Open Graph (or HOG). HOG compiles on most platforms; I’ve personally tested it on both OSX and Linux and I’m told it works on Windows too. The classes most relevant to this article are probably AnnotatedCluster.cpp and AnnotatedClusterAbstraction.cpp which together are responsible for generating the abstract graph. Meanwhile, AnnotatedHierarchicalAStar.cpp provides a reference implementation of the HAA* algorithm.

Advertisement