Pathfinding Algorithm Efficiency Analysis in 2D Grid
DOI:
https://doi.org/10.17770/etr2013vol2.868Keywords:
A*, BFS, Dijkstra's algorithm, HPA*, LPA*, shortest path problemAbstract
The main goal of this paper is to collect information about pathfinding algorithms A*, BFS, Dijkstra's algorithm, HPA* and LPA*, and compare them on different criteria, including execution time and memory requirements. Work has two parts, the first being theoretical and the second practical. The theoretical part details the comparison of pathfinding algorithms. The practical part includes implementation of specific algorithms and series of experiments using algorithms implemented. Such factors as various size two dimensional grids and choice of heuristics were taken into account while conducting experiments.Downloads
References
T. H. Cormen, C. E. Leiserson, R. L. Rivest and S. Clifford, Introduction to Algorithms (3rd ed.). MIT Press and McGrawHill, 2009. pp. 658.
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, 1959, pp. 269-271.
P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” in IEEE Transactions of Systems Science and Cybernetics, vol. 4, 1968, pp. 100-107.
D. Wagner, T. Willhalm, "Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs". 2003.
S. Koenig, M. Likhachev, D. Furcy. "Lifelong Planning A*". Artificial Intelligence, Vol. 155 Issue 1-2, 2004, pp. 93 - 146.
L. Sangeorzan, K. Kiss-Iakab, M. Sirbu, "Comparison of 3 implementations of the A* algorithm". North University of Baia Mare. 2007.
A. Botea, M. Muller, J. Schaeffer, "Near, Optimal Hierarchical Path-Finding," Journal of Game Development, 1(1): 2004, pp. 7-28.
M. R. Jansen, M. Buro, HPA* Enhancements. Proceedings of the Third Artificial Intelligence and Interactive Digital Entertainment Conference, Stanford, California, USA. 2007.
N. Sturtevant, M. Buro, Partial Pathfinding Using Map Abstraction and Refinement. AAAI 05 Proceedings of the 20th national conference on Artificial intelligence, vol. 3. 2005. pp. 1392 – 1397.
R. C. Holte, M. B. Holte, R. M. Zimmer, A. J. MacDonald, Hierarchical A*: Searching Abstraction Hierarchies Efficiently. AAAI 96 Proceedings of the thirteenth national conference on Artificial intelligence, vol. 1, 1996. pp. 530 – 1 535.
