• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
a_bertrand

I offer a: Simple path finding algorithm

19 posts in this topic

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
0

Share this post


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

0

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

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]
0

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
0

Share this post


Link to post
Share on other sites
I checked A* but it seems much more complex to code, and I'm not sure that it's as doable in javascript.
0

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*
0

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

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

Share this post


Link to post
Share on other sites
A* doesn't always guarentee finding the optimal path, it only guarentees this if h' never over estimates h. (f = g + h')
0

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Also I should mention that the A* algorithm is halfway between the algorithm you described and what's known as a "greedy search".
0

Share this post


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

Share this post


Link to post
Share on other sites
Man, I can't believe I didn't notice that. Yeah. Breadth first. Talking about flooding with water got me thinking about depth. Sorry.
0

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0