Jump to content
  • Advertisement
Sign in to follow this  
a_bertrand

I offer a: Simple path finding algorithm

This topic is 4834 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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:

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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*

Share this post


Link to post
Share on other sites
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 :-)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!