19 replies to this topic

[a_bertrand]

Hi, As the development of my own game is going on, I was looking for a small but yet working path finding code... which would need to be coded in javascript. So far I didn't found something existing, which was fitting the need, so I designed from scratch my own algorithm. As I think it's quiet fun, I share my results with you guys: http://www.nowhere-else.org/path_finding.php You will soon discover that the path is not well optimized (as well as the HTML page :-) ) but as a first trial it quiet fit the needs. Please feel free to comment it, or let me know if you find it useful. If you are interested I can explain how it works. In case you wonder what game could need it, you may visit the game web site: http://www.nowhere-else.org/ Cheers, Alain Bertrand

[Mushu]

It only took me a couple of tries to render it unable to find the target when there was a valid path to it. Lemmie upload a screenie or something.

EDIT: here we are:

[a_bertrand]

As I said it's by far not perfect and it still need tweaks and optimisations. But I think it can already give some ideas how the problem can be approched without have a too complex code.

[Mushu]

Yeah, any type of AI is fun like that. The last time I wrote something like this I pretty much bruteforced it. Talk about unoptimized [lol]

[xEricx]

You should give a try with A* :P

It does not require "tweaks", and results in clearer code than your implementation, and always works if there's a valid path :)

Hope this helps

Eric

[a_bertrand]

I checked A* but it seems much more complex to code, and I'm not sure that it's as doable in javascript.

[NQ]

Hm, I could mention that I also thought of A* as abit too complex for my little game, and also made my own invention.

This was for an RTS, and it worked quite well.

Good sides: really fast computation, really easy implementation, can handle quite complex obstacles and narrow passages.

Downsides: could not navigate a maze (but since such terrain wasn't present in my game this was no problem). Got every 100th unit stuck in a loop nearby the obstacle.

I believe this is the cost of any AI which does not use A*. Since they do not consider the entire way to the goal, rather just the way ahead, they can get stuck in loops. Because of the same reason, a maze would confuse the AI.

Wait! Oh...! I think i figured something out which would likely remove these flaws from my pathfinding... I'll come back if I can make it work! *runs off*

[a_bertrand]

Updated the path solving thing. The problem with the non working path reported was the "short" ahead view I gave to the code (in order to avoid too much CPU load in javascript). Now it also optimize a bit the solution :-)

[FlowingOoze]

Quote:

Original post by a_bertrand Updated the path solving thing.

I tried it too and a very simple maze made it fail. I'd suggest using A* too, as it quarantees finding a path if there is one, and not just any path, but the optimal one. It's not that much harder to code.

[StevoHolmes]

A* doesn't always guarentee finding the optimal path, it only guarentees this if h' never over estimates h. (f = g + h')

[FlowingOoze]

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.

[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.

[Sneftel]

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.

[johnnyBravo]

Quote:

Original post by Sneftel 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.

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 :)

[Sneftel]

Also I should mention that the A* algorithm is halfway between the algorithm you described and what's known as a "greedy search".

[hplus0603]

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.

[Sneftel]

Man, I can't believe I didn't notice that. Yeah. Breadth first. Talking about flooding with water got me thinking about depth. Sorry.

[WeirdoFu]

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?

[Sneftel]

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]

[Zefrieg]

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.