What path finding algorithms are there? [closed]

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?

• Apr 19, 2014 at 0:54

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. Aug 31, 2011 at 14:24
• Unfortunately the aigamedev.com page seems to not exist anymore. Any alternative sources? Nov 8, 2023 at 8:52

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 Aug 31, 2010 at 22:47
• fixx0r3d both links Sep 1, 2010 at 7:51
• Simple graph search algorithms are only the basics for pathfinding. May 14, 2016 at 12:35

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

• +1 for Amit. I learned A* from his website 10+ years ago. Sep 1, 2010 at 7:52
• Great illustrations too. High Quality. Mar 27, 2013 at 2:32

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.

• +1 for mentioning dynamic A* better know as D* Aug 31, 2010 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 :) Jul 14, 2010 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 Jul 15, 2010 at 16:05

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.

This one looks interesting:

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

• 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. Apr 6, 2014 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. Apr 6, 2014 at 23:21
• I'm just going to repeat what Seth said. Summarize.
– Grey
Apr 6, 2014 at 23:30