PIGE Home .plan FAQ .log Compiling Linux/UNIX Mac OS 8 & 9 Mac OS X Windows Downloads Source Code Executable Demos Thesis Screenshots Crate Room Tutorials Collision Detection Creating Icons OpenAL A* Resources OpenGL OpenAL Game Dev Books |

Path Finding - A^{*}
Algorithm
This page was originally used to record my research about the A* algorithm, which is used in finding a shortest path. For some good reading on the topic, read Chapter 13 of the 2002 publication, Mac Game Programming (Mark Szymczyk and Andre LaMothe).
Even if you aren't into the Mac side of programming, it does have some
good pointers and tips about other elements of game programming and the
gaming industry.
One important element in computer games is finding the shortest path between two points. The easiest implementation is to just have the character walk in a straight line. This will work as long as there are no obstacles or distractions along the way. If there is a chasm or a large rock in the way, then the character needs to figure out a way to move around and still reach the goal. Below is the classic representation of the A ^{*} algorithm.
f'(n) = g(n) + h'(n)
g(n) is the total distance it has taken to get from the starting
position to the current location.
h'(n) is the estimated distance from the current position to the
goal destination/state. A heuristic function is used to create this estimate
on how far away it will take to reach the goal state.
f'(n) is the sum of g(n) and h'(n). This is the
current estimated shortest path. f(n) is the true shortest path
which is not discovered until the A* algorithm is finished.
Here is another way to think about things. Consider a family vacation where the Dad, the Mom, the two kids and the family goat are all crammed into a car. After about 5 minutes, the kids start the fidget and start asking annoying questions. One of the questions (or a varient, thereof) is "How much farther 'til we get there?" To sate the children's curiosity for a few minutes, the Dad will make a rough guess. "Another 300 miles. It will be awhile, so why don't you take a nap?" If the family had already driven 100 miles at that point, that would represent g(n),
the total distance traveled so far. The estimate of 300 miles would be
h'(n), the guess on how much farther it would be. So the
f'(n) would be 100 + 300 = 400 miles.
One of the more difficult parts in solving A* is creating a good heuristic function to determine h'(n). A heuristic function differs from an algorithm in that a heuristic is more of an estimate and is not necessarily provably correct. An algorithm is a set of steps which can be proven to halt on a particular given set of input. The heuristic function in A* is arbitrary, however the better your heuristic is, the faster and more accurate your solution will become. However, therein lies the problem -- deciding a good heuristic. Even with a shortest path example, the heuristic can change, depending on the implementation of the search, and how easy or complicated the heuristic function is going to be. ## PseudocodeFrom the bookArtificial Intelligence: A New Synthesis by Nils
Nilsson.
- Create a search graph G, consisting solely of the start node,
n
_{o}. Put n_{o}on a list called OPEN. - Create a list called CLOSED that is initially empty.
- If OPEN is empty, exit with failure.
- Select the first node on OPEN, remove it from OPEN, and put it on CLOSED. Called this node n.
- If n is a goal node, exit successfully with the solution
obtained by tracing a path along the pointers from n to n
_{o}in G. (The pointers define a search tree and are established in Step 7.) - Expand node n, generating the set M, of its successors that are not already ancestors of n in G. Install these members of M as successors of n in G.
- Establish a pointer to n from each of those members of M that were not already in G (i.e., not already on either OPEN or CLOSED). Add these members of M to OPEN. For each member, m, of M that was already on OPEN or CLOSED, redirect its pointer to n if the best path to m found so far is through n. For each member of M already on CLOSED, redirect the pointers of each of its descendants in G so that they point backward along the best paths found so far to these descendants.
- Reorder the list OPEN in order of increasting f values. (Ties among minimal f values are resolved in favor of the deepest node in the search tree.)
- Go to Step 3.
^{*} algorithm: a-star.l
References
- A* Pathfinding for Beginners
- http://theory.stanford.edu/~amitp/GameProgramming/
- Amit's collection of Shortest Paths info
- A* Java Applet
__Mac Game Programming__, Mark Szymczyk, Andre LaMothe, 2002__Artificial Intelligence: A New Synthesis__, Nils J. Nilsson, 1998
Page created: 26. December 2002 Last modified: 14 July 2011 |