Open
Description
There has been some research on improving the general A* algorithm. We should see if any of these optimizations may be (optionally) applied.
- Extensions and Applications of the A* Algorithm - presents a method of dynamically improving a given heuristic so that no node is visited more than once.
- Optimizing the A* Algorithm - presents a couple high-level improvements: replace closed list with a boolean flag, conditional use of a priority queue, and early expansion of nodes
- Fast Pathfinding via Symmetry Breaking - may apply only to rectangular grid path finding, but can significantly reduce the search space
See also: http://theory.stanford.edu/~amitp/GameProgramming/