Graphics, Imaging, and Games Lab

  • Home
  • About Us
  • Contact
  • Login
Home

From the Lab

  • Benchmark
  • Projects
  • Publications
  • Image Galleries
  • Blogs
  • Lab Members
  • Prospective Students
  • Search

An Hierarchical Terrain Representation for Approximately Shortest Paths

David Mould
Michael C. Horsch
An Hierarchical Terrain Representation for Approximately Shortest Paths. Pacific Rim Conference on Artificial Intelligence, 2004.
Conference Paper

Related Projects
Natural Phenomena Modeling

Download the PDF

Abstract

We propose a fast algorithm for on-line path search in grid-like undirected planar graphs with real edge costs (aka terrains). Our algorithm depends on an off-line analysis of the graph, requiring poly-logarithmic time and space. The off-line preprocessing constructs a hierarchical representation which allows detection of features specific to the terrain. While our algorithm is not guaranteed in general to find an optimal path, we demonstrate empirically that it is very fast, and that the difference from optimal is almost always small.


BibTeX

@inproceedings{Mould:04:AHTR,
  author = {Mould, David and Horsch, Michael C.},
  booktitle = {Pacific Rim Conference on Artificial Intelligence},
  isbn = {3-540-22817-9},
  pages = {104-113},
  publisher = {Springer},
  title = {An Hierarchical Terrain Representation for Approximately Shortest Paths},
  year = {2004},
}

  • Home
  • About Us
  • Contact
  • Login