Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: Choosing a heuristic for A*
发信站: 哈工大紫丁香 (2002年08月29日00:53:53 星期四), 站内信件

发信人: jamguo (卜卜熊的耙耙兔), 信区: Algorithm
标  题: Choosing a heuristic for A*(转载)
发信站: 日月光华 (2002年08月03日07:55:02 星期六), 站内信件

【 以下文字转载自 AI 讨论区 】
【 原文由 jamguo 所发表 】

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


--
独处 图 寞之花，
    交往品清香之茶。
※ 来源:·日月光华 bbs.fudan.edu.cn·[FROM: 10.100.174.74] --

--
    ... 这一阵歌声传入湖边一个道姑耳中。她在一排柳树下悄立已久，

  晚风拂动她杏黄色道袍的下摆，拂动她颈中所插拂尘的万缕柔丝，心

  头思潮起伏，当真亦是「芳心只共丝争乱」 ...

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]