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

Question

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 1

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.

Answer 2

A* is the basic, most widely used, most general purpose graph traversal algorithm. Given a set of nodes, edges, and weights for those edges, a starting node, and an ending node, A* will find the shortest path between the 2 points.

As you must know, many variants on A* exist.

Some of these variants do things like allow for edge weights to change (dynamically "updateable" solution) (D*: The name D* comes from the term "Dynamic A*", because the algorithm behaves like A* except that the arc costs can change as the algorithm runs.).

Algorithms such as LRTA* (learning real time A*) will modify the graph as it explores it, increasing costs of edges that lead to dead ends and the like (hence "learning").