Efficiently computing alternative paths in game maps

Sie sind hier: Homepage > Suche

Efficiently computing alternative paths in game maps

Freier Zugriff

Li, Lingxiao / Cheema, Muhammad Aamir / Ali, Mohammed Eunus / Lu, Hua / Li, Huan

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.

Zugriff

Download

Exportieren, teilen und zitieren

Dokumentinformationen

Titel :

Efficiently computing alternative paths in game maps

Beteiligte:

Li, Lingxiao (Autor:in) / Cheema, Muhammad Aamir (Autor:in) / Ali, Mohammed Eunus (Autor:in) / Lu, Hua (Autor:in) / Li, Huan (Autor:in)

Erscheinungsdatum :

2023-09-01

Anmerkungen:

Li , L , Cheema , M A , Ali , M E , Lu , H & Li , H 2023 , ' Efficiently computing alternative paths in game maps ' , World Wide Web , vol. 26 , no. 5 , pp. 3321-3345 . https://doi.org/10.1007/s11280-023-01188-6

DOI :

https://doi.org/10.1007/s11280-023-01188-6

Medientyp :

Aufsatz (Zeitschrift)

Format :

Elektronische Ressource

Sprache :

Englisch

Schlagwörter :

Alternative pathfinding , Diverse shortest paths , Game maps

Klassifikation :

DDC: