ABSTRACT
This chapter covers the techniques for improving the speed of A* implementation. All game developers understand that A* is the pathfinding search algorithm of choice, but surprisingly, or not so surprisingly, it is not a panacea. The full Roy–Floyd–Warshall data results in very fast pathfinding queries, at the cost of memory overhead. Hierarchical pathfinding is the concept that the search space can be subdivided into at least two levels: a high-level zone-to-zone representation and a low-level step-by-step representation. Two concrete examples of hierarchical pathfinding in shipped games include Dragon Age: Origins and Company of Heroes. With bidirectional pathfinding, the search starts at both ends, the island side quickly runs out of nodes, and the search concludes that there is no path. When many pathfinding search requests are required all at once, an architectural decision must be made as to how many simultaneous search requests should be processed at the same time.
