Precomputed-Direction Heuristics for Suboptimal Grid-Based Path-finding

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Grid-Based Path Planning Competition

This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

10.1609/socs.v3i1.18252