Diverse Shortest Paths in Game Maps: A Comparative User Study and Experiments

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Computing diverse shortest paths 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 diverse shortest paths (also called 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, we design a web-based system that allows the users to visualise the alternative paths generated by these existing approaches in different maps. Finally, we use this web-based system to conduct a user study that shows that the existing road network approaches generate high-quality alternative paths when adapted for the game maps. Furthermore, we also evaluate the quality of alternative paths returned by existing approaches using some well-known quantitative measures on a widely used game maps benchmark.

Original languageEnglish
Title of host publicationDatabases Theory and Applications - 33rd Australasian Database Conference, ADC 2022, Proceedings
EditorsWen Hua, Hua Wang, Lei Li
Number of pages13
PublisherSpringer
Publication date2022
Pages76-88
ISBN (Print)9783031155116
DOIs
Publication statusPublished - 2022
Event33rd Australasian Database Conference, ADC 2022 - Sidney, Australia
Duration: 2 Sept 20224 Sept 2022

Conference

Conference33rd Australasian Database Conference, ADC 2022
Country/TerritoryAustralia
CitySidney
Period02/09/202204/09/2022
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13459 LNCS
ISSN0302-9743

Keywords

  • Alternative pathfinding
  • Diverse shortest paths
  • Game maps

Cite this