• Advertisement

Archived

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

simple AI searching (A* and Breadth First)

This topic is 5618 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

hi, As part of a rather trivial game (a simple desktop puzzle) I''ve been prototyping a few searching algorithms - for performance and efficiency... and I''ve come up with a strange little problem: A Breadth-First-Search (BFS) finds an optimal path everytime, but is very very slow. I implemented A* with 2 heuristics (manhatten being one), yet they never seem to find the same (or comparable) optimal solution. ie, my BFS gets the solution in 24 steps, and the A* either manages 26 steps or 30 steps (depending on the heuristic). is there any generic reason why this might happen? - because I''ve been debugging, profiling etc... my code for over a week now, and I cant see any obvious logic errors in the code. it doesn''t "miss" solutions, it just seems to find a solution at depth-30 before it''ll find one at depth-24... It''s driving me up the wall... anyone who can spare me a few minutes to work it out would be a real star I cant offer much of a reward (I''m only an overdrawn student!). I can present source code (Java) if anyone cares, but Its a little lengthy and I''d rather be able to solve it myself... thanks! Jack DirectX 4 VB: All you need for multimedia programming in Visual Basic Formula 1 Championship Manager, My Game Project.

Share this post


Link to post
Share on other sites
Advertisement
Make sure that your heuristics are not overestimating the distance remaining. If they do, then A* won''t necessarily give you the optimal solution, which appears to be what is happening in your case.

Mike

Share this post


Link to post
Share on other sites

  • Advertisement