Feb

A* Pathfinding Algorithm

Written by Neil Galloway

I have been messing around with my Nintendo DS again and trying to write some simple programs. Hello World that can be dragged and dropped on the screen somewhere is as far as I have advanced.

I have been learning the A* algorithm however. I have implemented it in Java and now I am working on C/C++ versions. I think I will also try to do a demo version in javascript to what how it works visually.

What Is A*

It is a shortest path algorithm. It tries to find the shortest path it will take for something to go from point A to point B while taking into consideration obstacles and such.

It takes a little bit to wrap your head around the first time and then it makes perfect sense how it is working.

I won't try to explain it myself, since there are a few sites that already do it well enough. My main reference was A* Pathfinding for Beginners. I read on another site that they criticize this tutorial because it says you have to use a closed list and you don't. I still found it to be one of the easier descriptions though.

I recommend implementing it in the language of your choice once and then tweaking it after that. I also recommend reading the A* Search Algorithm Wikipedia article.

I hope to post some more examples in the near future.

If you enjoyed this post, then make sure you subscribe to my RSS feed or subscribe for email updates. Only one email a day and only if there was a new post.

Email this article

Category: Computers

Original Post: Tuesday, February 26th, 2008

2 Comments

James Says:
2008-02-27 18:44:53
Mmmmmm. A*...

You might want to consider two additional improvements to the algorithm, that make for smoother, more efficient paths.

1) Consider calculating more then 1 step at a time. A* is notorious for doing poorly in "traps": areas where the game state forms a "U".

2) Consider a "breadth first search" of all the available nodes, traversing down the entirety of the list and "pre-planning" your route. That way, you get a "path plan" for the unit, and then can forget about calculating a new path from then on out. You then store the "plan" as a property of the unit. The biggest downside to this approach comes when the unit encounters a transient (but impassable) area. We used to call this the "orienteering algorithm" because the trick is then to have the unit recalculate the path from its current position to the destination and cache that.

James Says:
2008-02-27 18:50:49
Ah #!@%*#e. I was remembering A* as being calculated one step per game tick. In that case it degenerates into greedy-A which isn't as good as A* proper for exactly the reason I posted.

*sigh*

I should have read the articles before I posted the comment.