Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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*?

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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.
share|improve this answer
    
+1 for the comment on specific scenarios. Different branching factors, memory allocation costs, heuristic qualities, and other factors will all affect how well it runs. –  Kylotan Jan 1 '12 at 22:12
    
Went ahead and added a bit more information now since I recall a few of these optimizations from the books. –  David Gouveia Jan 1 '12 at 22:23
1  
+1 for 'close enough'. People get too paranoid about getting the absolute perfect path. In fact, using a less-than-perfect path makes AI (especially) unpredictable. OT: You have been posting some really awesome answers! Keep it up! –  Jonathan Dickinson Jan 1 '12 at 23:01
    
@JonathanDickinson OT: Thanks a lot! :) –  David Gouveia Jan 1 '12 at 23:05
add comment

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").

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.