Quote:Original post by StevoHolmes
A* doesn't always guarentee finding the optimal path, it only guarentees this if h' never over estimates h. (f = g + h')
Obviously.
Quote:Original post by StevoHolmes
A* doesn't always guarentee finding the optimal path, it only guarentees this if h' never over estimates h. (f = g + h')
Quote:Original post by johnnyBravo
Could you give a basic explanation of your algorithm?
As a while ago I was interested in this maze path finding stuff, and I settled on filling the entire area up with 'pretend' water from the target pos, until the start pos got wet, and then I just traced the water back from the target pos to the start pos. And it gave nearly the most shortest path, depending on how I let the water spread out.
Quote:Original post by SneftelQuote:Original post by johnnyBravo
Could you give a basic explanation of your algorithm?
As a while ago I was interested in this maze path finding stuff, and I settled on filling the entire area up with 'pretend' water from the target pos, until the start pos got wet, and then I just traced the water back from the target pos to the start pos. And it gave nearly the most shortest path, depending on how I let the water spread out.
That's equivalent to what's known as the "depth-first" search, and properly implemented it will always return the shortest path. The problem, of course, is that it's very inefficient. For instance, generating a path between two nodes which are n steps apart in a fully-connected 2D state set will require visiting O(n^2) nodes.
Quote:That's equivalent to what's known as the "depth-first" search