Is there a known most efficient version of A* search algorithm?

Is there a known 'most efficient' version of the A* search algorithm? I know some people write papers on the most efficient way to compute common operations, has this been done for A*?

Answer

If you don't mind bibliography, take this list as a starting point. It's a series of articles from the Game Programming Gems and the AI Game Programming Wisdom series, with the most relevant ones being:

• Beyond A* - Game Programming Gems 5


• Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*) - Game Programming Gems 5


• How to Achieve Lightning Fast A* - AI Game Programming Wisdom


• Practical Optimizations for A* Path Generation - AI Game Programming Wisdom


• A* Aesthetic Optimizations - Game Programming Gems


• A* Speed Optimizations - Game Programming Gems

If I remember correctly from what I've read, there's no ultimate version of A* being presented, but rather a series of optimization and improvements you can make to increase its performance or memory usage in specific scenarios.

---

I wanted to add a bit more detail since I own these books, but I won't have access to them until the end of the month. Here's what I can somewhat recall from memory though. First, there are several optimization you can apply while using a regular A* implementation.

The most significant change you can make is simplifying the search space. There are many different ways to represent your search space, each with pros and cons, and choosing the correct one for the job is pretty much the most deciding factor in A* performance. The most common space representations are using a grid, a navigation mesh or a visibility graph.

Tweaking the heuristic can also affect the speed of your pathfinding. For instance, they say that the heuristic has to be admissible (i.e. it never overestimates the actual cost) for A* to find you the best path. But sometimes if you overestimate the heuristic a little it will speed up the search and the paths returned will be similar enough (maybe not perfect every time, but significantly close).

Finally, there are many variations on the algorithm itself to make it work under different circunstances, for instance, just to name a few:

• D* (Dynamic) - Dynamic in the sense that it works under the assumption that the terrain can change even while you're still looking for the path.


• HPA* (Hierarchical) - Uses several layers at different abstraction levels to speed up the search. For instance, an higher level layer may simply connect rooms, while a lower level layer takes care of avoiding obstacles.



• IDA* (Iterative Deepening) - Reduces memory usage in comparison with regular A* by using iterative deepening.