A* Discussion

Also see Amit’s introduction to A*. The following were posted to Usenet in 1996:

From: tim_hardy@nt.com (Tim Hardy)
Newsgroups: comp.ai.games
Subject: Best Path Algorithm
Date: Mon, 25 Mar 96 20:59:41 GMT

I posted a request here a short time ago for a best path algorithm.  I 
appreciate the responses I received.  I ended up trying an algorithm 
called A*, but I have the following problems.
  I've used the algorithm (A*), but I find it to be either correct and 
terribly slow or fast and stupid on large (100x80) maps with varying 
terrain.  I like the algorithm, but I need it to be much faster (it takes 
15+ seconds on a pentium-100 to get from one corner to the other on a 
100x80 map).  If I leave the heuristic most commonly mentioned in the 
algorithm (dx^2+dy^2), the algorithm will not find the best path (it 
plows through mountains it could easily have gone around) but it is very 
fast.  If I lower the value of the heuristic (abs(dx)+abs(dy)) and raise 
the weight of the terrain cost (most common - plains = 2 instead of one), 
the algorithm now finds the true shortest path (it obviously considers 
more alternate routes), but now takes 15+ seconds to do it.  In general, 
if the heuristic is a large value and the terrain cost small, the 
intelligence of the algorithm goes way down.  If I raise the value of the 
terrain cost (I've tried everything from 1 to 1000 for the cost of the 
most common terrain) and lower the value of the heuristic, the 
intelligence goes way up.  I've seen this slgorithm demonstrated (sample 
code and apps) as being very fast, but they always use "can go here" or 
"can't go here" instead of varying terrain cost, and the maps are very 
small.  I wonder if anyone besides me has actually pushed this thing in a 
real app.  I know it can be done because games like Warlords 2 do a good 
job with my exact problem.  If I'm doing something wrong please let me 
know.  I just changed the cost of going into a square from 1 to my 
terrain cost.  Any help will be appreciated.

Tim
From: "Randolph M. Jones" <rjones@eecs.umich.edu>
Newsgroups: comp.ai.games
Subject: Re: Best Path Algorithm
Date: Tue, 26 Mar 1996 10:09:42 -0500

Tim,
   It sounds like you may be violating one of the rules of A* search.
A* should always be finding the best path as long as your heuristic is
admissible.  "Admissible" means that the heuristic evaluation of a path's
cost is *always* less than or equal to the true cost of taking the path.
Your comment "if the heuristic is a large value and the terrain cost small,
the intelligence of the algorithm goes way down" makes it sound like you
have rediscovered this principle.  A* will not give you the best path
if the heuristic value is actually larger than the terrain cost.  Given
this, I don't know why your heuristic of (dx^2+dy^2) isn't working.  The
only thing I can figure is that some of your terrain costs are less than
one (assuming dx and dy are counting unit grid squares).

I would expect that (dx^2+dy^2) is going to be about the fastest heuristic
you can come up with for general path-finding (because it is a "perfect"
heuristic when all terrain costs are 1), but you have to make sure the
formula is admissible for it to find the best path.  This means you should
change your terrain costs so none of them are less than one, or change
dx and dy to count in units of the smallest terrain cost you use.  No
matter what you do, you must make sure that the heurstic equation gives
you a value that is never greater than the actual terrain cost along any
particular path.

Hope this helps...I also hope I am not misunderstanding your problem,
   Randy Jones
From: crpalmer@solo.uwaterloo.ca (Chris Palmer)
Subject: Re: Best Path Algorithm
Sender: news@undergrad.math.uwaterloo.ca (news spool owner)
Date: Tue, 26 Mar 1996 16:50:23 GMT

In article <315808B6.167E@eecs.umich.edu>,
Randolph M. Jones <rjones@eecs.umich.edu> wrote:
>Tim,
>   It sounds like you may be violating one of the rules of A* search.
>A* should always be finding the best path as long as your heuristic is
>admissible.  "Admissible" means that the heuristic evaluation of a path's
>cost is *always* less than or equal to the true cost of taking the path.
>Your comment "if the heuristic is a large value and the terrain cost small,
>the intelligence of the algorithm goes way down" makes it sound like you
>have rediscovered this principle.  A* will not give you the best path
>if the heuristic value is actually larger than the terrain cost.  Given
>this, I don't know why your heuristic of (dx^2+dy^2) isn't working.  The
>only thing I can figure is that some of your terrain costs are less than
>one (assuming dx and dy are counting unit grid squares).

Although, I suspect that you were actually thinking about sqrt(dx^2+dy^2) ?

The original poster is actually looking at a grid map and in such
a case probably wants the heuristic max(dx, dy).  This gives the closest
heuristic guaranteed (if all costs are at least 1) to return a shortest
path when diagonal movement costs the same as horizontal and vertical
(the typical case for grid maps).

Even if diagonals have "correct" movement costs, the max() heuristic
isn't too bad and keeps you using integers instead of floating point
operations....

Cheers,
Chris.
-- 
Mail: crpalmer@undergrad.uwaterloo.ca
Homepage: http://www.undergrad.math.uwaterloo.ca/~crpalmer/
From: "Randolph M. Jones" <rjones@eecs.umich.edu>
Newsgroups: comp.ai.games
Subject: Re: Best Path Algorithm
Date: Tue, 26 Mar 1996 14:21:37 -0500

Chris Palmer wrote:
> 
> In article <315808B6.167E@eecs.umich.edu>,
> Randolph M. Jones <rjones@eecs.umich.edu> wrote:
> >Tim,
> >   It sounds like you may be violating one of the rules of A* search.
> >A* should always be finding the best path as long as your heuristic is
> >admissible.  "Admissible" means that the heuristic evaluation of a path's
> >cost is *always* less than or equal to the true cost of taking the path.
> >Your comment "if the heuristic is a large value and the terrain cost small,
> >the intelligence of the algorithm goes way down" makes it sound like you
> >have rediscovered this principle.  A* will not give you the best path
> >if the heuristic value is actually larger than the terrain cost.  Given
> >this, I don't know why your heuristic of (dx^2+dy^2) isn't working.  The
> >only thing I can figure is that some of your terrain costs are less than
> >one (assuming dx and dy are counting unit grid squares).
> 
> Although, I suspect that you were actually thinking about sqrt(dx^2+dy^2) ?

Of course you are right.  I didn't even notice (duh).

The original poster mentioned (dx^2+dy^2) (rather
than the square root).  If he is not using the square root of this, then
that explains his problem.  This is always going to be larger than the
true distance, which makes it an inadmissible heuristic.
From: cd000450@interramp.com (Bryan Stout)
Newsgroups: comp.ai.games
Subject: Re: Best Path Algorithm
Date: 26 Mar 1996 16:24:19 GMT

In article <4j71hq$klr@crchh327.rich.bnr.ca>, tim_hardy@nt.com says...
[original posting]
>Tim

First, about the function.  It is normally f(n) = g(n) + h(n), where g() is the 
actual cost from the origin to the current node n, and h() is the estimate of 
the ramaining cost to the goal.  If h() is guaranteed to be an underestimate, 
then A* will find the shortest route.  That one heuristic, (dx^2 + dy^2), is 
not an underestimate.  You should try (distance from n to goal) * (smallest 
terrain cost).  If the only moves are orthogonal, then the distance is the 
"Manhattan" distance, |dx| + |dy|; if diagonal moves are allowed, it is 
diagdistance*min(|dx|,|dy|) + orthodistance*||dx|-|dy||.  (E.g., if dx=8 and 
dy=5, you will take 5 diagonal steps and 3 orthogonal ones.)  

However, if the terrain cost varies widely (say, roads are cheap but most other 
terrain is costly), A* won't be efficient if you use the cheapest terrain cost 
for the heuristic.  Because then, the heuristic cost is far below the true 
cost, and the search becomes closer to a breadth-first search.  Try using a 
typical terrain cost rather than the cheapest; you may not find the best path, 
but may have a good tradeoff between the quality of the path and the time to 
find it.

*Most important*, I think you need to look at how you are implementing the Open 
and Closed lists.  Having it take 15 seconds to do the search means there's a 
lot of waste somewhere.  [Are you doing this in Windows, and having new search 
records dynamically allocated and freed on the fly?  That could use up a lot of 
time there.]  With large grids to search, the efficiency of Open and Closed 
becomes very important.  Look up Sedgewick's _Algorithms in C++_: it has a good 
discussion of different ways of implementing Priority Queues -- which is what 
the Open list is -- with their pros and cons.  The trickiest thing is that you 
have to search Open for the next node to pop, having the cheapest f() cost; and 
you also have to search both Open and Closed to make sure a new square's state 
has not already been visited (and if so, re-do it if the new value is better). 
 That makes two different search keys -- f() score, and coordinates -- so use 
your ingenuity to find the best way to implement the structures to search 
through them.

I'm giving a technical presentation at the Computer Game Developers' Conference 
this Sunday on this very topic.

Bryan Stout
bstout@interramp.com
From: Swoodcoc@cris.com (Steven Woodcock)
Newsgroups: comp.ai.games
Subject: Re: Best Path Algorithm
Date: 27 Mar 1996 23:33:50 GMT

Tim Hardy (tim_hardy@nt.com) opined thusly:
: I posted a request here a short time ago for a best path algorithm.  I 
: appreciate the responses I received.  I ended up trying an algorithm 
: called A*, but I have the following problems.
:
: <problems with A* algorithm deleted>
:
Hello Tim:


   At the risk of souding mean, I'd wager that you either implemented
it inefficiently or (if you got code from someplace) got a poorly-done
code example.  A* isn't *that* bad.

   A variant of A* that might work better for you is Djisktra's
Algorithm.  Some folks find it slower, but I find it faster and
think that it generally produces nicer looking paths.

   How are you storing your intermediate nodes in your A* algorithm?
If you're using a linked list, are you preallocating memory up front or
allocating/deallocating memory as you go?  That could be very slow.
Another issue might be the "flatness" of the terrain.  All of these
pathing algorithms work worst when the map is relatively flat, so if
that is the case you may be better off doing a sub-optimal quick
solution (maybe a straight line even) to get across the plains, then
at some distance that's "close enough" invoke the pathfinder to find
a route over/through the mountains.

:  I wonder if anyone besides me has actually pushed this thing in a 
: real app.  I know it can be done because games like Warlords 2 do a good 
: job with my exact problem.  If I'm doing something wrong please let me 
: know.  I just changed the cost of going into a square from 1 to my 
: terrain cost.  Any help will be appreciated.


  I'm using Djiskstra's in my current project, and I know of several
uses of A* in realtime strategy games like Warcraft II.  (By the way,
I don't think WCII does that good a job; the planning distance
seems incredibly short since I get units stuck in cubbyholes all the
time.)


Steve
+=============================================================================+
|                                                           _                 |
| Steven Woodcock                                     _____C .._.             |
| Senior Software Engineer, Gameware             ____/     \___/              |
| Lockheed Martin Information Systems Group     <____/\_---\_\    "Ferretman" |
| Phone:      719-597-5413                                                    |
| E-mail:     woodcock@escmail.orl.mmc.com (Work), swoodcoc@cris.com (Home)   |
| Web:        http://www.cris.com/~swoodcoc/wyrdhaven.html   (Top level page) |
|             http://www.cris.com/~swoodcoc/ai.html          (Game AI page)   |
| Disclaimer: My opinions in NO way reflect the opinions of                   |
|             the Lockheed Martin Information Systems Group                   |
+=============================================================================+
Email me at redblobgames@gmail.com, or tweet to @redblobgames, or post a public comment: