Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

DefCom

A* Is this normal

This topic is 5734 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Yes more A* problems/queries. As some of you know i have been doing a pathfinding algorithm comparison project. In nearly all cases the A* work as expected accept this one:

Compared with the breadth-first

Clearly the A* is not finding the shortest path If i reverse the Start and Goal, it does find the shortest path.

If anyone has any ideas on why it may be doing this i would appriciate hearing them, thanks. [edited by - Defcom on April 1, 2003 7:18:23 AM]

Share this post


Link to post
Share on other sites
Advertisement
uhm well..
its part of a*: you begin with the end and work to the start.
if you *understand* the workings of a*, this is just a logical step.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Except. Not accept.

Share this post


Link to post
Share on other sites
What is the distance function you are using between squares (note that the diagonal distance should be longer than the distance straight up, down, to the left or to the right)?

Ummmm, never mind. You clearly aren't using diagnoal paths between squares. Possibly you aren't keeping track of the total cost correctly or your heuristic (estimate to goal) is being calculated wrong.

botman

[edited by - botman on April 1, 2003 8:59:09 AM]

Share this post


Link to post
Share on other sites
"uhm well..
its part of a*: you begin with the end and work to the start.
if you *understand* the workings of a*, this is just a logical step. "


You can start from either end. It makes no difference. What you have just stated is the same as saying a piece of string has a start end and a stop end.




ai-junkie.com

Share this post


Link to post
Share on other sites
I completely forgot about the heuristic! A bit of tinkering with it has given me different results, Allthough i can now get the shortest path it does take as long the breadth-search.

Thanks AP for pointing out my life threatening context error.

As always, thanks for responces.

Share this post


Link to post
Share on other sites
quote:
Original post by DefCom
I completely forgot about the heuristic! A bit of tinkering with it has given me different results, Allthough i can now get the shortest path it does take as long the breadth-search.



Then your heuristic is probably not admissible. The heuristic must be less than the actual cost to reach the goal (that is what is meant by an admissible heuristic), yet as close as possible to the actual cost. If the heuristic is too small, then A* functions poorly. Most folks use the Manhatten Distance Formula to calculate a distance to the goal.

FWIW, A* is mathmatically proven to find the shortest path, in the fewest node expansions (cells looked at in your case) when it has an admissible heuristic that approaches actual cost to goal.

Eric

Share this post


Link to post
Share on other sites
Geta beat me to the punch. Almost without exception situations like this are caused by an inadmissable heuristic. An admissible heuristic must a) underestimate the actual cost of getting from a node to the goal; and b) be a monotonic function. In your domain there are two commonly used choices: Manhattan Distance (also known as City Block Distance) and Straight Line Distance. The latter is obvious, the former is the sum of axial distances from the node to the goal. FYI: These measures are the first two Euclidean norms.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
I did start with Manhattan, but changed to straight line as at the time it gave me better performance.
I have run hundreds of different paths and in most cases it does perform perfectly, shortest path in the quickest time (When compared with Breadth-First, Depth-First and Dijkstra). It only doesn''t find the shortest path when it starts in a open area, but now i am aware of the Heuristic making a difference I can take that into account in my project.

Share this post


Link to post
Share on other sites
I apologize but I must correct Geta and Timkin on this one.

Geta, I agree that an admissible heuristic will find the optimal path every time but it does not guarantee that A* will "visit" the least amount of nodes. This is like saying that every admissible heuristic for A* "visits" the same amount of nodes which is simply not true.

Timkin, an admissible heuristic must never overestimate the cost of a node to the goal.

You said: h* < h
Correct: h* <= h

DefCom, just to add to your project, you might want to also look into comparing with the recursive best-first search (RBFS) algorithm as well. Iterative deepening, too.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!