I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
Take the 2-minute tour
×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
closed as too broad by Josh Petrie♦ Apr 7 '14 at 22:04There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs. If this question can be reworded to fit the rules in the help center, please edit the question. |
|||||
|
|||||
|
If you're looking to research and learn about pathfinding in general, I'd definitely suggest learning more than just one algorithm. You'll want to understand the overall concepts but be able to apply them to whatever it is you are working on. Most game developers who need to do any serious pathfinding end up writing their own custom algorithms, although highly based on known solutions, every game is different and will have different requirements. I'd start by reading up on some of the more well know methods like A*, Dijkstra's Algorithm, Depth and Breadth-First searches. There's a lot of good information on the internet on each of these. (http://en.wikipedia.org/wiki/Pathfinding) While reading them, take note on what the upsides and downsides are to each approach, as well as the type of data the algorithm can operate on. Can it be applied to 3-dimensional paths? Can it be modified to account for our human AI who wants to avoid the landmines in the map? When it comes to pathfinding, A* is pretty much the golden ticket that everyone uses. You should definitely know how it works. (http://en.wikipedia.org/wiki/A*_search_algorithm) Here's a good example of A* as it applies to an RTS game, which needs to take entities of different size into account: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/ Good luck! |
|||||
|
|
Pathfinding algorithms are basically a graph search problem solving algorithms. http://en.wikipedia.org/wiki/Pathfinding#Algorithms Most known being Djikstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra's_algorithm and its variant A* search algorithm: http://en.wikipedia.org/wiki/A* |
|||||||||
|
|
This is a great beginning resource that takes a look at all aspects of path finding in a very easy to digest approach. Amit’s Notes about Path-Finding
|
|||||||||||||
|
|
Pathfinding is a pretty solved problem... as mentioned in almost every answer here, some variation on A* is going to be what you use. The bigger challenge to me, is how you want to represent your path. Using a grid, pathnodes, navmeshes, hierarchical grids or other complex structures, etc. I don't have any specific references in mind, but exploring AIGameDev will give you all kinds of ideas as to what's out there. Just remember that each representation has its pros and cons; it's not about finding the 'best one', it's about finding the one that is the best fit for your gameplay. |
||||
|
|
|
There's a good list on Wikipedia: Pathfinding As far as I know, A* and D* are both pretty popular. |
|||||
|
|
There are several path finding algorithms out there. One of the most popular ones is probably A* (A-Star). It's a very useful algorithm if you have a heuristic function that can give you estimated costs to reach a goal (example would be the line-of-sight distance to the target). A* is very useful to find the shortest path from a start to an end point. Other than that there's also Dijkstra's algorithm which is very useful to find the nearest item out of several items. Eg. if you want to find out which power-up (or similar) is closest to your gaming character. There are several other algorithms out there, but I guess A* is by far the most popular one. Mat Buckland has an excellent chapter about Path-Finding in his Book Programming Game AI by Example. I strongly encourage you to get a copy of it. Otherwise you'll find loads of information online by searching for "A Star search". |
|||||||||
|
|
Here's a tutorial on using Dijkstra's Algorithm for pathfinding. |
||||
|
|
|
Here is a good example of A* being used in a game with some psuedo code: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/ |
||||
|
|
|
This isn't much of a primer, but we discussed graph algorithms extensively in our algorithms class last Fall 2009. We used this book, Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein http://mitpress.mit.edu/algorithms/ and it also has accompanying youtube lectures from an MIT class. Chapters 17, 18, and 19 dealt with shortest paths. |
||||
|
|
|
See [Graph and tree search algorithms] on Wikipedia1. They are pretty much just a variations of State Space Search, You just have to go trough all of these and find where they differ. There is also Collaborative Diffusion, which is one of previously mentioned algorithms done interesting way. |
|||||||||
|
|
This one looks interesting: http://www.codeproject.com/Articles/455 I wonder is it better than A*? |
|||||||||||||
|
