4.5 Article

Efficiently computing alternative paths in game maps

出版社

SPRINGER
DOI: 10.1007/s11280-023-01188-6

关键词

Diverse shortest paths; Alternative pathfinding; Game maps

向作者/读者索取更多资源

This study focuses on the problem of alternative pathfinding in game maps. Firstly, we adapt existing techniques for road networks to find alternative paths in game maps. Then, we propose novel data structures and develop an efficient algorithm to compute high-quality alternative paths. Experimental results demonstrate that our algorithm is more than an order of magnitude faster than existing approaches and returns alternative paths of comparable quality.
Alternative pathfinding requires finding a set of k alternative paths (including the shortest path) between a given source s and a target t. Intuitively, these paths should be significantly different from each other and meaningful/natural (e.g., must not contain loops or unnecessary detours). While finding alternative paths in road networks has been extensively studied, to the best of our knowledge, we are the first to formally study alternative pathfinding in game maps which are typically represented as Euclidean planes containing polygonal obstacles. First, we adapt the existing techniques designed for road networks to find alternative paths in the game maps. Then, based on our web-based system that visualises alternative paths generated by different approaches, we conduct a user study that shows that the existing road network approaches generate high-quality alternative paths when adapted for the game maps. However, these existing approaches are computationally inefficient especially when compared to the state-of-the-art shortest path algorithms. Motivated by this, we propose novel data structures and exploit these to develop an efficient algorithm to compute high-quality alternative paths. that shows that the existing road network approaches generate high-quality alternative paths in game maps. Our extensive experimental study demonstrates that our proposed algorithm is more than an order of magnitude faster than the existing approaches and returns alternative paths of comparable quality. Furthermore, our algorithm is comparable to a state-of-the-art shortest path algorithm in terms of running time.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据