Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU
Loading...
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
We present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm tries to find the shortest path. As we show, this approach scales very well for different topologies, hardware and graph sizes and has a mean length error below 1% while using reasonable amounts of memory. By keeping a simple structure and minimal backtracking, we are able to use the same approach on the massively parallel GPU, reducing the run time even further.
Description
@inproceedings{10.2312:pg.20201228,
booktitle = {Pacific Graphics Short Papers, Posters, and Work-in-Progress Papers},
editor = {Lee, Sung-hee and Zollmann, Stefanie and Okabe, Makoto and Wuensche, Burkhard},
title = {{Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU}},
author = {Reischl, Maximilian and Knauer, Christian and Guthe, Michael},
year = {2020},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-120-5},
DOI = {10.2312/pg.20201228}
}