The euclidean distance not the best indicator the actual distance
242 



Indoor level  Outdoor level 
Figure 4.18  Euclidean distance fill characteristics 

The cluster heuristic works by grouping nodes together in clusters. The nodes in a cluster represent some region of the level that is highly interconnected. Clustering can be done automatically using graph clustering algorithms that are beyond the scope of this book. Often, clustering is manual, however, or a byproduct of the level design (portalbased game engines lend themselves well to having clusters for each room).
A lookup table is then prepared that gives the smallest path length between each pair of clusters. This is an offline processing step that requires running a lot of pathfinding trials between all pairs of clusters and accumulating their results. A sufficiently small set of clusters is selected so that this can be done in a reasonable time frame and stored in a reasonable amount of memory.
4.3 A*  


A  A  B  C  


B  
C  


Figure 4.19  The cluster heuristic 
Clustering is intimately related to hierarchical pathfinding, explained in Section 4.6, which also clusters sets of locations together. Some of the calculations we’ll meet there for distance between clusters can be adapted to calculate the heuristics between clusters.
Even without such optimizations, the cluster heuristic is worth trying for labyrinthine indoor levels.
This is a good example of the knowledge vs. search tradeoff we looked at in Chapter 2.
If the heuristic is more complex and more tailored to the specifics of the game level, then the A* algorithm needs to search less. It provides a good deal of knowledge about the problem. The ultimate extension of this is a heuristic with ultimate knowledge: completely accurate estimates. As we have seen, this would produce optimum A* performance with no search.
Null heuristic  

Figure 4.20 


Null heuristic  4.3 A* 


Figure 4.21  Fill patterns outdoors 

Quality of Heuristics
Producing a heuristic is far more of an art than a science. Its significance is massively underestimated by AI developers. In my experience, many developers drop in a simple Euclidean distance heuristic without thought and hope for the best.
Dijkstra Is A*
It is worth noticing that the Dijkstra algorithm is a subset of the A* algorithm. In A* we calculate the estimatedtotalcost of a node by adding the heuristic value to the costsofar. A* then chooses a node to process based on this value.
For each pathfinding world representation, we will divide the game level into linked regions that correspond to nodes and connections. The different ways this can be achieved are called division schemes. Each division scheme has three important properties we’ll consider in turn: quantization/localization, generation, and validity.
You might also be interested in Chapter 11, Tools and Content Creation, which looks at how the pathfinding data is created by the level designer or by an automatic process. In a complete game, the choice of world representation will have as much to do with your toolchain as technical implementation issues.