Fringe Search: Beating A* at Pathfinding on Game Maps
- Yngvi Bjornsson, School of Computer Science, Reykjavik University, Iceland
- Markus Enzenberger, Department of Computing Science, University of Alberta
- Robert Holte, Department of Computing Science, University of Alberta
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
The A* algorithm is the de facto standard used for pathfinding search. IDA* is a space-efficient version of A*, but it suffers from cycles in the search space (the price for using no storage), repeated visits to states (the overhead of iterative deepening), and a simplistic leftto- right traversal of the search tree. In this paper, the Fringe Search algorithm is introduced, a new algorithm inspired by the problem of eliminating the inefficiencies with IDA*. At one extreme, the Fringe Search algorithm expands frontier nodes in the exact same order as IDA*. At the other extreme, it can be made to expand them in the exact same order as A*. Experimental results show that Fringe Search runs roughly 10-40% faster than highly-optimized A* in our application domain of pathfinding on a grid.
Citation
Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer. "Fringe Search: Beating A* at Pathfinding on Game Maps". IEEE, pp 125-132, January 2005.Keywords: | fringe, search, pathfinding, game, maps |
Category: | In Conference |
BibTeX
@incollection{Bjornsson+al:IEEE05, author = {Yngvi Bjornsson and Markus Enzenberger and Robert Holte and Jonathan Schaeffer}, title = {Fringe Search: Beating A* at Pathfinding on Game Maps}, Pages = {125-132}, booktitle = {}, year = 2005, }Last Updated: June 04, 2007
Submitted by Staurt H. Johnson