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 book Artificial Intelligence: A New Synthesis by Nils Nilsson.
References
Page created: 26. December 2002 Last modified: 14 July 2011 |