Fringe Search: Beating A* at Pathfinding on Game Maps.

Abstract

Abstract- 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. 1