Efficient Triangulation-Based Pathfinding

Douglas Demyen, Michael Buro

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*.

Subjects: 15.7 Search; 17. Robotics

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.