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.
I offer a: Simple path finding algorithm
Obviously.
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.
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 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: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.
Oh so its an actual documented algoritm. Yeah I never ended up using it in a game, because of its speed, I got fed up with my other attempts getting stuck in closed off coridors :) so I used that as an excuse of completing my goal of creating a pathfinding algo :)
Also I should mention that the A* algorithm is halfway between the algorithm you described and what's known as a "greedy search".
Quote:That's equivalent to what's known as the "depth-first" search
Actually, that would be a breadth first search, as the water floods out in a "wave". The depth first search would try one path until that path got stuck, then backtrack until it could get un-stuck, and try something slightly different, ...
Breadth first is easy to implement with queues/FIFOs; depth first is easy to implement with recursion.
As Sneftel observed, A* is a fairly typical breadth first with a priority queue instead of a simple FIFO.
Man, I can't believe I didn't notice that. Yeah. Breadth first. Talking about flooding with water got me thinking about depth. Sorry.
Actually, with the water flooding and constantly checking to see if the water hits the target, wouldn't it be iteratively deepening depth first search?
Heheheh... good point. The two share strong similarities, of course. The points that have already been visited aren't dried and re-wetted, though, so it's closer to breadth-first.
Oooh, there's a fun idea for a graph algorithm: Iterative breadth-first. I think that'd be O(n^3). [grin]
Oooh, there's a fun idea for a graph algorithm: Iterative breadth-first. I think that'd be O(n^3). [grin]
What johnnyBravo is describing is just breadth-first. Iterative-deepening search iteratively increases the depth of a depth-limited search until it finds the solution or an increase in depth does not yeild more searched nodes. A depth-limited search is just a depth-first search that is limited at a certain depth. Iterative-deepening is usually used over breadth-first, depth-first, and depth-limited searches.
As for the original poster, I would suggest learning the various graph searching methods that have been discussed so far. A* is both complete and optimal, so it is certainly a good one to know.
As for the original poster, I would suggest learning the various graph searching methods that have been discussed so far. A* is both complete and optimal, so it is certainly a good one to know.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
