An optimal pathfinder for vehicles in real-world digital terrain maps


by

F. Markus Jönsson


The Department of Numerical Analysis and Computing Science,
The Royal Institute of Science, Stockholm, Sweden, (p)1997

Abstract (på svenska)

This paper describes an algorithm for approximately finding the fastest route for a vehicle to travel between two points in a digital terrain map, avoiding obstacles along the way. There can optionally be one or more ‘enemies’ located in the terrain which should, whenever possible, be avoided. Specifically, the terrain map model consists of a 2D height raster and a terrain class raster. There are also roads, in the form of vector data. The vehicle speed is a function of the terrain or road class as well as constrained by a maximum allowed slope. The enemies are avoided by staying out of their line of sight. However, the general results of this paper should be feasible for a much wider range of applications ranging from complex GIS systems to home computer games.

The approach taken in this work is to translate the problem into a ‘least cost path’ graph problem with an associated cost function on the graph edges. Standard graph algorithms can then be used to solve the graph problem exactly. In order to be feasible for use on standard personal computers, a simple progressive scheme is needed for very large graphs (containing many millions of nodes) giving approximate solutions in reasonable time and memory space.

 

Next section...