# What path finding algorithms are there?

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?

-

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!

-
+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

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*

-
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

This is a great beginning resource that takes a look at all aspects of path finding in a very easy to digest approach.

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

-
 +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 at 2:32

There's a good list on Wikipedia: Pathfinding

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

-
 +1 for mentioning dynamic A* better know as D* – David Young Aug 31 '10 at 21:09

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

-
 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

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.

-

The only thing I know of is the A* pathfinding algorithm. You can find a beginners tutorial on it right here: http://www.policyalmanac.org/games/aStarTutorial.htm

-

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.

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.

-

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.

-
+1 That document on Collaborative Diffusion is quite interesting. – Nick Wiggill Aug 31 '11 at 14:42
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