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.

Pseudocode

From the book Artificial Intelligence: A New Synthesis by Nils Nilsson.
  1. Create a search graph G, consisting solely of the start node, no. Put no on a list called OPEN.
  2. Create a list called CLOSED that is initially empty.
  3. If OPEN is empty, exit with failure.
  4. Select the first node on OPEN, remove it from OPEN, and put it on CLOSED. Called this node n.
  5. If n is a goal node, exit successfully with the solution obtained by tracing a path along the pointers from n to no in G. (The pointers define a search tree and are established in Step 7.)
  6. 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.
  7. 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.
  8. 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.)
  9. Go to Step 3.
LISP code of the A* algorithm: a-star.l
References
Page created: 26. December 2002
Last modified: 14 July 2011