Efficient Triangulation-Based Pathfinding

Abstract

In this paper we present a method for abstracting an environ-ment represented using constrained Delaunay triangulations in a way that significantly reduces pathfinding search effort, as well as better representing the basic structure of the envi-ronment. The techniques shown here are ideal for objects of varying sizes and environments that are not axis-aligned or that contain many dead-ends, long corridors, or jagged walls that complicate other search techniques. In fact, the abstrac-tion simplifies pathfinding to deciding to which side of each obstacle to go. This technique is suited to real-time computa-tion both because of its speed and because it lends itself to an anytime algorithm, allowing it to work when varying amounts of resources are assigned to pathfinding. We test search algo-rithms running on both the base triangulation (Triangulation A * – TA*) and our abstraction (Triangulation Reduction A* – TRA*) against A * and PRA * on grid-based maps from the commercial games Baldur’s Gate and WarCraft III. We find that in these cases almost all paths are found much faster us-ing TA*, and more so using TRA*.