A* Search Algorithm

Summary

In the article Introduction to A*, Amit goes over two graph traversal algorithms: Dijkstra’s Algorithm and Greedy Best-First-Search Algorithm, providing a great visualization of how these algorithms work as well as cases in which they excel and in which they struggle. A summary of his description of these algorithms are as follows:

  • Dijkstra’s Algorithm – guaranteed to find the shortest path from the starting point to the goal, longer run-time because it visits vertices continuously expanding outward from the starting point until it reaches the goal.
  • Greedy Best-First-Search Algorithm – works with an estimate (heuristic) of how far from the goal any vertex is, selecting the vertex closest to the goal. Not guaranteed to find the shortest path, but runs much quicker than Dijkstra’s Algorithm.

He then explains what the A* Algorithm is, taking advantage of the best of both of these algorithms. This is done by combining the pieces of information that Dijkstra’s Algorithm uses (favoring vertices that are close to the starting point) and information that Greedy Best-First-Search uses (favoring vertices that are close to the goal).

Reaction to Content

This article is the first part of a larger series by Amit about pathfinding, however I believe that reading this article alone is good enough for a quick overview about what the A* algorithm is as well as providing excellent visualizations for the three mentioned algorithms. These visualizations are definitely helpful for understanding how these algorithms work as well as what their potential advantages and downfalls are.

I chose this topic in particular because it’s an interesting part of a subject area that I have interest in (game programming) and also is an important topic in CS in general (graphs and graph traversal algorithms). It’s a useful refresher for some of the topics that I learned in my algorithms course. Also, seeing how a potential algorithm in a game could decide how to best traverse towards a goal taking into account any obstacles in the way is interesting think about.

I think the rest of the series would likely be a good read to get a deeper insight into the A* algorithm.

 

Source: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: