bei Google ScholarTitelangaben
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
(Hrsg.):
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
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.
Weitere Angaben
| Publikationsform: | Aufsatz in einem Buch |
|---|---|
| Begutachteter Beitrag: | Ja |
| Institutionen der Universität: | Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik > Professur Angewandte Informatik V > Professur Angewandte Informatik V - Univ.-Prof. Dr. Michael Guthe Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik > Professur Angewandte Informatik VI > Professur Angewandte Informatik VI - Univ.-Prof. Dr. Christian Knauer |
| Titel an der UBT entstanden: | Ja |
| Themengebiete aus DDC: | 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik |
| Eingestellt am: | 07 Mai 2024 10:24 |
| Letzte Änderung: | 07 Mai 2024 10:24 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/89501 |