Also see Amit’s introduction to A*[1]. 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 | +=============================================================================+