Efficient Triangulation-Based Pathfinding

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Robotics and Computer Vision

In this paper we present a method for abstracting an environment represented using constrained Delaunay triangulations in a way that significantly reduces pathfinding search effort, as well as better representing the basic structure of the environment. 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 abstraction simplifies pathfinding to deciding to which side of each obstacle to go. This technique is suited to real-time computation 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 algorithms 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 using TA*, and more so using TRA*.