**0**

# I offer a: Simple path finding algorithm

Started by a_bertrand, Aug 16 2005 03:51 AM

19 replies to this topic

###
#1
Members - Reputation: **184**

Posted 16 August 2005 - 03:51 AM

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

Sponsor:

###
#7
Members - Reputation: **328**

Posted 16 August 2005 - 09:34 PM

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*

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*

###
#9
Members - Reputation: **236**

Posted 16 August 2005 - 10:47 PM

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.

###
#12
Members - Reputation: **100**

Posted 21 August 2005 - 01:53 PM

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.

###
#13
Senior Moderators - Reputation: **1781**

Posted 21 August 2005 - 02:40 PM

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.

###
#14
Members - Reputation: **100**

Posted 21 August 2005 - 02:49 PM

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

###
#16
Moderators - Reputation: **7262**

Posted 21 August 2005 - 03:12 PM

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.

###
#19
Senior Moderators - Reputation: **1781**

Posted 22 August 2005 - 03:54 AM

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]

###
#20
Members - Reputation: **316**

Posted 22 August 2005 - 11:07 AM

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.