Also see Amit’s introduction to A*[1]. The following was posted to Usenet in 1996:
From: amitp@Xenon.Stanford.EDU (Amit Patel) Newsgroups: rec.games.programmer Subject: Re: Shortest path algorithm? Date: 28 Feb 1996 02:10:31 GMT
kathi@lightside.com wrote:
Many times I have seen people ask here about a shortest path algorithm... the answer is almost always “Look in a good algorithm’s book.” Can anyone recommend such a book?
My problem is that I am trying to find paths on a 640x480 grid... with any of the algorithms I’ve seen so far, the worst-case scenarios would take tremendous amount of memory to store the tree...
The problem is that finding the “best path” is by its nature .. very expensive.
If you’re willing to settle for an approximation, there are very fast algorithms out there that use heuristics or additional information about your map to determine a “pretty good” path.
My current favorite is A*, which requires a distance function from any point to your goal. It doesn’t need an exact distance -- just an estimate of how long it would take to get from that point to the goal, in the best case.
If your grid has few obstacles, A* acts like a line-drawing algorithm. Unlike Dijkstra’s algorithm or the wavefront (breadth-first search) algorithms, A* does not search the rest of the map unless it needs to.
If your grid has a lot of obstacles, it’s going to be hard to find a path. One solution is to use “regions”. If you can group areas of your map into regions, then you can use path-finding from region to region instead of from pixel to pixel. This will greatly reduce the number of “nodes” in your path-searching algorithm. At the two ends, you need to find a path from your pixel to the closest region on the path.
Regions are a lot like what we do in real life. We have “rooms”, “floors”, “buildings”, “cities”, etc. If you want to get from your room to another room in another city, you first find a path from your room to your door (pixel by pixel?), then from your door to the stairs (your room region to the Stairs room region), then from there to the first floor (floor region to floor region path), then to the car (building region to parking lot region), then to the highway (street level regions), then to another city (highway regions). Then you’ll reverse the process to go down to the appropriate level of detail.
Unfortunately, it may be hard to find regions automatically. It’s much easier if your map is already composed of regions.
I have saved a few resources to path-finding on my Games Programming web page[2].
- Amit