As you may already know if you follow me on Twitter (why not?), I often work with pathfinding. This thing started as a small side quest during my Ph.D. and then grew up to become the main topic of my future Ph.D. thesis. I’m still quite sure that this is not what I chose back in the day but, well, now that I’m on the dancefloor I have to keep dancing.

Returning to the subject, my work is totally focused on pathfinding with cognitive capabilities. This means that I try to embed pathfinding into a more high-level reasoning pattern or, if you prefer, to push high level elements - such as reasoning with keys and equipment - down into the pathfinding level. As a consequence I use hierarchical abstraction of the map space a lot and for “a lot” I mean that in the last year and half I’ve implemented Hierarchical Pathfinding (HPA*) at least 4-5 times in different context and languages.

The concept behind HPA* is quite simple. Suppose to have an NPC who have to navigate in a building. You can for sure just find a path tile by tile, but you can also think to perform first an high-level search on the rooms. In order to reach the destination I have to pass by “room A”, “room C” and finally “room D”. Then you can just get a path from this high-level markers that is a much simpler task. Obviously the resulting path is not the shorter one but who cares? In games we want believable paths, not the perfect shortest paths.

Therefore, the basic idea is to do a first preprocessing on the map in order to extract a high-level graph representation of the map and then use this graph to search for a first approximation of the real path. If the map never change during the game (and this is widely common in games) this abstraction graph is always the same and we can compute it offline (for instance, before shipping the game to the users). You can read more one HPA* here.

That’s cool! It seems so elegant too! Well, it surely is, but you have to note several points when you try to implement HPA or other hierarchical pathfinding approaches. The thing that nobody will tell you when they explain HPA is: how to search in the high level graph?

There is several complications but the main one is: how to handle the starting and destination point? Unless you are extremely lucky sooner or later you will receive a starting and a destination point that are not on the high level. The solution on the paper is simple: add start and target to the vertices in the abstract high-level graph and search on it as usual! That’s right! But here I’ve seen and made a lot of design errors. Changing the graph can be done in several way and only one can be considered correct. But first, let’s see the two main wrong ones.

The Side-Effect Way

The first bad way to solve this problem is to modify the high-level graph we had. We put in it the two nodes we need, we search on it and then we will remove them. This can seem reasonable but it is not. That is the worst thing you can do.

First, you don’t know how the graph data structure is implemented (and if you know you should act as if you didn’t). Perhaps, adding or removing vertices can be extremely time consuming. Who knows? Second, you are performing side-effect on something that should be immutable. And performing side-effect exposes you to bugs. And because you are introducing possible bugs in something that is immutable you are introducing nasty time-consuming bugs that can appear anytime in the future. Lie silent for months and then explode in the face of your consumer.

Please, don’t do it.

The Clone Way

The second approach is much safer. You simply create a copy of the original graph, you add the vertices and the edges to the copy and then you discard everything. This is better, because in this way you can guarantee that the original graph is preserved. If you do a mistake, the mistake lifespan is confined in the query lifespan. This is very good. However, you are creating a full new graph for each pathfinding query. You are doubling the memory overhead for the map and you are adding the performance issues of creating and destroying a full graph. For each character. Potentially several times per seconds.

That’s not good. It is nice, but we can do much better.

The Extension Way

The third approach is the one I’m actually using and I’ve found that this can simplify a lot the structure of HPA* search. The idea is to create a class (we can call it ExtendedGraph ) who **wrap around **the original graph. This class is not a subclass of your generic Graph data structure, it is just another “thing” who share with the Graph  class the same interface. This class contains a reference to the original graph, for instance the graph with the original map abstraction, and just the two vertices you want (and their edges). So when you want to perform an HPA* search on your map abstraction you just have to pay the cost of creating and destroying the exact number of vertices you need: two. Moreover, because ExtendedGraph  and Graph  share the same interface you can do this without changing anything in your other classes! And everything should work flawlessly.

The specific implementation of the ExtendedGraph depends obviously on the original graph but the key points are:

1. It has to contain a reference/pointer to the original. Not the copy, just a pointer.
2. A list of vertices and edges of the extensions (the starting node, its edges and so on).
3. Every operation you have to perform on the graph (for instance, get the neighbours of a vertex, get the edge label and all the rest) must take into account the extension. That is, if the target node is interested by the extension (example: you are searching for the neighbours of “start”) that you have to compute the answer using your information, otherwise you can just propagate the operation to the corresponding operation of the original graph.

To be more clear, here it is the neighbours  operator of my ExtendedGraph  class in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def neighbours(self, node):
    if node in self.ext_vertices:
        # If the target node is in the extension...
        return self.extension[node]
    original_neighbours = self._original_graph.neighbours(node)
    if node in self.boundary_vertices:
        # If the target node is a neighbour of an extension node...
        extended_adjacent = set([x for x in self.ext_vertices if node in self.extension[x]])
        return extended_adjacent.union(original_neighbours)
    else:
        # Otherwise just return the neighbours of the original graph.
        return original_neighbours

Obviously, because the extended graph keep a reference to the original graph you should not perform operation who change the original graph. If you do that, you are changing the graph in every extended graph out of there! If you need to perform this operations, than you need a mutable map abstraction and this is a totally different problem.

This is not amazing programming techniques, is just a small tip that some new programmers don’t see when they implement HPA* and other hierarchical pathfinding approaches. I hope that at least one of you can find this interesting. :)