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:
- Dissimilarity: It must be visually distinct from the shortest path.
- Quality: It must avoid unnecessary loops or significant detours.
- 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.
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