Optimal Pathfinding on Weighted Grid Maps
Mark Carlson, Sajjad K. Moghadam, Daniel Damir Harabor, Peter J. Stuckey, Morteza Ebrahimi
Abstract
In many computer games up to hundreds of agents navigate in real-time across a dynamically changing weighted grid map. Pathfinding in these situations is challenging because the grids are large, traversal costs are not uniform, and because each shortest path has many symmetric permutations, all of which must be considered by an optimal online search. In this work we introduce Weighted Jump Point Search (JPSW), a new type of pathfinding algorithm which breaks weighted grid symmetries by introducing a tiebreaking policy that allows us to apply effective pruning rules in symmetric regions. We show that these pruning rules preserve at least one optimal path to every grid cell and that their application can yield large performance improvements for optimal pathfinding. We give a complete theoretical description of the new algorithm, including pseudo-code. We also conduct a wide-ranging experimental evaluation, including data from real games. Results indicate JPSW is up to orders of magnitude faster than the nearest baseline, online search using A*.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based SearchThayne T. Walker, Nathan R. Sturtevant, Ariel FelnerAAAI 2020 · 16 citations
- Suboptimal Search with Dynamic Distribution of SuboptimalityMohammadreza Hami, Nathan R. SturtevantAAAI 2025
- Effective Integration of Weighted Cost-to-Go and Conflict Heuristic within Suboptimal CBSRishi Veerapaneni, Tushar Kusnur, Maxim LikhachevAAAI 2023 · 5 citations
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous ActionsShuai Zhou, Shizhe Zhao, Zhongqiang RenAAAI 2025 · 10 citations
- Towards Computing a Near-Maximum Weighted Independent Set on Massive GraphsJiewei Gu, Weiguo Zheng, Yuzheng Cai, Peng PengKDD 2021 · 10 citations
