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.

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?

share|improve this question

closed as too broad by Josh Petrie Apr 7 at 22:04

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

11 Answers 11

up vote 25 down vote accepted

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!

share|improve this answer
2  
+1 for the bit about programmers having to learn to adapt known solutions. This is something many would-be-game-developers do not understand. –  Nick Wiggill Aug 31 '11 at 14:24

This one looks interesting:

http://www.codeproject.com/Articles/455 I wonder is it better than A*?

share|improve this answer
    
Welcome to the site. What you've given is known as a link-only answer, which is discouraged. It would be better to summarize the method's qualities in your answer. You could then argue whether it is better than simple A*, rather than idly pondering it in text. –  Seth Battin Apr 6 at 23:15
    
I see your answer is more or less on par for this question (which is unfortunate). I don't mean to single you out, I merely passed your entry in the first posts review queue. Regardless, improving your answer is always welcome. –  Seth Battin Apr 6 at 23:21
    
I'm just going to repeat what Seth said. Summarize. –  Grey Apr 6 at 23:30

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.

share|improve this answer
    
+1 That document on Collaborative Diffusion is quite interesting. –  Nick Wiggill Aug 31 '11 at 14:42
1  
I think the link is broken. Maybe this is the correct one: scalablegamedesign.cs.colorado.edu/gamewiki/index.php/… –  pek Oct 3 '11 at 16:07

There's a good list on Wikipedia: Pathfinding

As far as I know, A* and D* are both pretty popular.

share|improve this answer
    
+1 for mentioning dynamic A* better know as D* –  David Young Aug 31 '10 at 21:09

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*

share|improve this answer
2  
The last link is broken because the * is not seen as part of it: en.wikipedia.org/wiki/A%2A –  Hendrik Brummermann Aug 31 '10 at 22:47
    
fixx0r3d both links –  tenpn Sep 1 '10 at 7:51

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.

share|improve this answer

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 addresses the problem of finding a good path from the starting point to the goal―avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). Movement addresses the problem of taking a path and moving along it. It’s possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm ...

share|improve this answer
1  
+1 for Amit. I learned A* from his website 10+ years ago. –  tenpn Sep 1 '10 at 7:52
    
+1 for adding Amit before I did :P –  pek Oct 3 '11 at 16:03
    
Great illustrations too. High Quality. –  monkey Mar 27 '13 at 2:32

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.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Chapters 17, 18, and 19 dealt with shortest paths.

share|improve this answer

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/

share|improve this answer

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

share|improve this answer
    
Oh my. While I was typing this, the same answer was given about a gazillion times. Sorry :) –  bummzack Jul 14 '10 at 19:27
    
Just noticed that the book in mentioned is also on Google-Books (although not complete). Read it here: books.google.com/books?id=gDLpyWtFacYC –  bummzack Jul 15 '10 at 16:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.