Also see Amit’s introduction to A*[1]. The following was posted to Usenet in 2000:
Article 13518 of comp.games.development.programming.algorithms:
Path: nntp.stanford.edu!newsfeed.stanford.edu!logbridge.uoregon.edu
!cyclone-west.rr.com!news.rr.com|news-west.rr.com
!newsfeed2.earthlink.net!newsfeed.earthlink.net
!newsmaster1.prod.itd.earthlink.net
!newsread2.prod.itd.earthlink.net.POSTED!not-for-mail
From: "Tom Hatfield" <rskorpion@NOSPAMearthlink.net>
Newsgroups: comp.games.development.programming.algorithms
References: <8bvf90$rto$1@duke.telepac.pt>
Subject: Re: Path-finding algorithm
Lines: 97
Message-ID: <mXDF4.13013$64.467989@newsread2.prod.itd.earthlink.net>
Date: Sun, 02 Apr 2000 08:56:50 GMT
NNTP-Posting-Host: 63.27.26.87
Organization: EarthLink Inc. -- http://www.EarthLink.net
> Hi,
> I'm looking for a path-finding algorithm (I think this is how it is
> called).
> I'm writing a tile-based game, and I need to find an algorithm that
can
> make something go round obstacles (tiles which can not be crossed) and
reach
> it's destination tile.
Since you didn't give a particular language, I'll just post a description
for you. The following is a semi-coded description of the A* (a-star)
algorithm, which is both fast and efficient for finding your way through
(not overly complex) tile regions. You can use it for a multitude of
things, but it works fine with tiles.
Basically, A* functions on three things: the Open list (nodes that need to
be tested), the Closed list (nodes that do not need to be tested), and the
heuristic. In this definition, a "node" is simply information on a
particular tile. Each tile can have its own node, but it's highly unlikely
that you'll end up testing all tiles on the map; in fact, with luck you'll
only be testing very few.
The heuristic is the key to making A* efficient. It is the estimated
distance from any given tile to the destination (which we'll call the "goal
node"). The closer your heuristic is to the actual distance, the better
your path will be. The best distance you can use is probably a straight X,Y
differential between goal and start:
d = |gx-sx| + |gy - sy|
For the code to function, you'll need an array of nodes for the Open list,
and another array for the Closed list. To be safe, the Closed array should
be as big as your map size (x * y), and the Open list about half that. This
is approximately what your node structure should look like:
structure Node(n)
.XCoord
.YCoord
.Cost
.XParent
.YParent
Coords are the (X,Y) coordinates of the tile. Cost is the movement cost to
reach that tile, which is accumulated while you search the map. Parents are
the coordinates of the tile from which you enter this one (needed to recurse
the final path).
Now for the algorithm itself, in detail. I cannot guarantee this is the
best version of A*, because this is one I made specifically for Visual Basic
(it's impossible to find a path-finding algo for VB on the web, believe me).
It does have at least one major short-coming that I've already encountered,
but hopefully you can tweak it to suit your needs. Here it is:
Add start node to Open list
Do:
Search for node on Open that has best estimate (cost + heuristic)
Move that node to Closed list
If node is goal, break with success
Else, test all neighboring nodes that can be reached from there
Calculate estimate (cost + heuristic) for each node
If node is already on Open
If estimate is better than current, keep it on Open
Else, move it to Closed (it's worse, so we can ignore it)
If node is already on Closed
If estimate is better than current, move it back to Open
Else, keep it on Closed
If node is not on either list, put it on Open
Loop while Open has nodes on it
When done, recurse path back to start using Parent coords
And that's it. If you have trouble understanding it , I suggest trying it
out with a simple map on graph paper, keeping track of where you put your
nodes while running through the map. This will also give you an excellent
look at what kind of path the algorithm follows. (I did this myself.)
Like I said, this is only one version of many. There are lots of variations
on A*, and depending on your needs, you might be better checking them out as
well:
http://theory.stanford.edu/~amitp/GameProgramming/
I've asked some other people about it but haven't gotten any response yet.
Here is a quick change to the algorithm that might yield better results:
If node is already on Closed
If estimate is better than current, keep it on Closed
Else, remove it from Closed (so it's not on either list)
I don't know what effect this will have during execution, because it didn't
make sense to just remove a node from the Closed list after testing it.
Anyway, give it a shot if you have problems. This algorithm should work in
most cases. Good luck to you.
- Tom -