Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU

Title data

Reischl, Maximilian ; Knauer, Christian ; Guthe, Michael:
Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU.
In: Lee, Sung-hee ; Zollmann, Stefanie ; Okabe, Makoto ; Wuensche, Burkhard (ed.): Pacific Graphics 2020 : Short Papers, Posters, and Work-in-Progress Papers. - Wellington : The Eurographics Association , 2020
ISBN 978-3-03868-120-5
DOI: https://doi.org/10.2312/pg.20201228

Abstract in another language

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.

Further data

Item Type: Article in a book
Refereed: Yes
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professor Applied Computer Science V > Professor Applied Computer Science V - Univ.-Prof. Dr. Michael Guthe
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professor Applied Computer Science VI > Professor Applied Computer Science VI - Univ.-Prof. Dr. Christian Knauer
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
Date Deposited: 07 May 2024 10:24
Last Modified: 07 May 2024 10:24
URI: https://eref.uni-bayreuth.de/id/eprint/89501