Efficiently computing alternative paths in game maps

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

In modern gaming, finding the single shortest path between two points is a solved problem. However, for real-time strategy (RTS) or role-playing games (RPGs), having every unit follow the exact same trajectory leads to predictable, unnatural behavior. This paper, published in the World Wide Web journal (2023), introduces a high-performance framework for generating diverse, high-quality alternative paths in real-time.

The Challenge of Alternative Pathfinding

While road-network algorithms for alternative paths exist, they do not translate well to the Euclidean planes and polygonal obstacles found in game maps. An effective alternative path must satisfy three often-conflicting criteria:

  1. Dissimilarity: It must be visually distinct from the shortest path.
  2. Quality: It must avoid unnecessary loops or significant detours.
  3. Efficiency: It must be computed in milliseconds to support real-time gameplay.

Methodology: The CVPD+DL Framework

The researchers developed the Compressed Via-Path Database (CVPD) combined with Distance Labels (DL). Unlike traditional databases that store the next move, CVPD stores the "highest-ranked via-node" on a path.

Nodes are ranked using betweenness centrality, identifying the "bottlenecks" or "main highways" of a map. By storing the $i$-th longest "plateau"—segments common to multiple shortest path trees—the algorithm can quickly identify promising branching points for alternative routes. This structure is symmetric, significantly reducing the storage footprint compared to asymmetric road-network databases.

Experimental Evaluation

The authors evaluated their framework using the Moving AI Lab benchmarks, including maps from Dragon Age and Baldur’s Gate II.

Alternative paths generated on Warcraft III and Baldur's Gate II maps demonstrate high quality and dissimilarity.

Key Results

  • Performance: The CVPD algorithm is over an order of magnitude faster than adapted road-network methods like Penalty or Plateaus. Its runtime is comparable to Polyanya, the state-of-the-art for finding just a single shortest path.
  • Path Quality: A user study with 472 responses confirmed that the generated paths feel "natural." The paths maintained low bounded stretch and high local optimality.
  • Scalability: The system handles complex maps with thousands of convex vertices while maintaining real-time performance.

Conclusion and Future Work

The CVPD+DL framework makes real-time alternative pathfinding feasible for complex game environments. While the current approach requires offline preprocessing for static maps, it sets a new standard for speed and quality. Future research may focus on dynamic environments with moving obstacles and optimizing memory overhead for mobile platforms.

Summary updated

Abstract

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.
BibTeX
@article{li2023efficiently,
  author = {Lingxiao Li and Muhammad Aamir Cheema and Mohammed Eunus Ali and Hua Lu and Huan Li},
  title = {{Efficiently computing alternative paths in game maps}},
  journal = {WWW},
  year = {2023},
  doi = {10.1007/s11280-023-01188-6},
}
Figure