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: July 04, 2007Submitted by Staurt H. Johnson
