Abstract | ||
---|---|---|
We present a fast and robust path planning algorithm for generic static terrains with polygonal obstacles. Our algorithm finds shorter, and therefore more intuitive paths than a traditional A* approach with a similar underlying graph. The presented algorithm is derived from A* and is modified to circumvent undecidable situations and unintuitive results. Additionally, we present two post-processing steps to enhance the quality and visual appearance of the resulting paths. The first method minimizes the number of waypoints in a path while the second method takes the slope of the terrain into account in order to generate visually more pleasing paths. We show that our algorithm is fast and, therefore, well suited for realtime applications, such as games or virtual environments |
Year | DOI | Venue |
---|---|---|
2004 | 10.1109/CGI.2004.1309225 | Computer Graphics International |
Keywords | Field | DocType |
data visualisation,path planning,terrain mapping,tree searching,A* algorithm,generic path planning,path planning algorithm,real-time application | Motion planning,Any-angle path planning,Mathematical optimization,Shortest path problem,Computer science,Terrain,Fast path,A* search algorithm,Undecidable problem,Visual appearance | Conference |
ISSN | ISBN | Citations |
1530-1052 | 0-7695-2171-1 | 7 |
PageRank | References | Authors |
0.62 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christoph Niederberger | 1 | 38 | 2.90 |
Dejan Radovic | 2 | 7 | 0.62 |
Markus H. Gross | 3 | 10154 | 549.95 |