期刊
COMPUTERS & GRAPHICS-UK
卷 102, 期 -, 页码 1-8出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cag.2021.11.007
关键词
Computer science; Computing methodologies and applications; Computer graphics; Computational geometry
The new approach proposed in this study utilizes pre-computed minimal distance fields for path finding in weighted graphs, aiming to find the shortest path by selecting the most promising minimal distance field at each node and switching between them. This method scales excellently for various topologies, graph sizes, and hardware specifications, maintaining a mean length error below 1% and reasonable memory consumption. By simplifying the structure and minimizing backtracking, the approach can be applied on massively parallel GPUs and other shared memory parallel architectures, further reducing the run time.
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 aims to find the shortest path possible. As we show, this approach scales excellently for various topologies, graph sizes and hardware specifications while maintaining a mean length error below 1% and reasonable memory consumption. By utilizing a simplified structure and keeping backtracking to a minimum, we are able to leverage the same approach on the massively parallel GPUs or any other shared memory parallel architecture, reducing the run time even further. (C) 2021 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据