Jump to content

  • Log In with Google      Sign In   
  • Create Account


I offer a: Simple path finding algorithm


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
19 replies to this topic

#1 a_bertrand   Members   -  Reputation: 184

Like
0Likes
Like

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:

#2 Mushu   Members   -  Reputation: 1396

Like
0Likes
Like

Posted 16 August 2005 - 04:10 AM

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:



#3 a_bertrand   Members   -  Reputation: 184

Like
0Likes
Like

Posted 16 August 2005 - 04:14 AM

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.

#4 Mushu   Members   -  Reputation: 1396

Like
0Likes
Like

Posted 16 August 2005 - 04:16 AM

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]

#5 xEricx   Members   -  Reputation: 560

Like
0Likes
Like

Posted 16 August 2005 - 04:34 AM

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

#6 a_bertrand   Members   -  Reputation: 184

Like
0Likes
Like

Posted 16 August 2005 - 06:12 AM

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

#7 NQ   Members   -  Reputation: 328

Like
0Likes
Like

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*

#8 a_bertrand   Members   -  Reputation: 184

Like
0Likes
Like

Posted 16 August 2005 - 09:41 PM

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

#9 FlowingOoze   Members   -  Reputation: 236

Like
0Likes
Like

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.


#10 StevoHolmes   Members   -  Reputation: 122

Like
0Likes
Like

Posted 16 August 2005 - 10:55 PM

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

#11 FlowingOoze   Members   -  Reputation: 236

Like
0Likes
Like

Posted 16 August 2005 - 10:57 PM

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.

#12 johnnyBravo   Members   -  Reputation: 100

Like
0Likes
Like

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.


#13 Sneftel   Senior Moderators   -  Reputation: 1773

Like
0Likes
Like

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 johnnyBravo   Members   -  Reputation: 100

Like
0Likes
Like

Posted 21 August 2005 - 02:49 PM

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

#15 Sneftel   Senior Moderators   -  Reputation: 1773

Like
0Likes
Like

Posted 21 August 2005 - 02:54 PM

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

#16 hplus0603   Moderators   -  Reputation: 4527

Like
0Likes
Like

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.


#17 Sneftel   Senior Moderators   -  Reputation: 1773

Like
0Likes
Like

Posted 21 August 2005 - 03:20 PM

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

#18 WeirdoFu   Members   -  Reputation: 205

Like
0Likes
Like

Posted 22 August 2005 - 02:45 AM

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?

#19 Sneftel   Senior Moderators   -  Reputation: 1773

Like
0Likes
Like

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]

#20 Zefrieg   Members   -  Reputation: 316

Like
0Likes
Like

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS