Optimal Pathfinding on Weighted Grid Maps


  • Mark Carlson Monash University
  • Sajjad K. Moghadam University of Tehran
  • Daniel D. Harabor Monash University
  • Peter J. Stuckey Monash University
  • Morteza Ebrahimi University of Tehran




SO: Heuristic Search, ROB: Motion and Path Planning, PRS: Routing


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*.




How to Cite

Carlson, M., Moghadam, S. K., Harabor, D. D., Stuckey, P. J., & Ebrahimi, M. (2023). Optimal Pathfinding on Weighted Grid Maps. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12373-12380. https://doi.org/10.1609/aaai.v37i10.26458



AAAI Technical Track on Search and Optimization