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.

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

it was a stupid logic error when calculating the heuristic :o

f(n) = h(n)

should have been:

f(n) = g(n) + h(n)

worked perfectly after that

Jack

DirectX 4 VB: All you need for multimedia programming in Visual Basic
Formula 1 Championship Manager, My Game Project.