An Introduction to Pathfinding

An Introduction to Pathfinding
Author: Russell Long
Description: The author introduces the subject of pathfinding and explains about Dijkstra's Algorithm, which is one of the algorithms for finding the shortest path between two points.

Post your discussions/comments here by clicking on Add Reply.

A very fine tutorial. That is what I was looking for, thank you very much Russell Long.

np

yeah - thanks! very informative and useful.

A* will be my next article and should elegantly proceed the dijkstra tutorial since in essence A* is dijkstra with only one major addition!!!!!


and then I'll probably end with a Civilisation style demo as last article

(maybe pure SDL or opengl in 3D, if I get the hang of textures)


(i.e. you've got to get a person across some terrain)

Wow, yeah, that would be great! Thanks a lot.

Good Evening:

Thanks for the great article!

My question is: What is the most efficient way of finding the shortest path? Is it Dijastra's Algorithm or is there another one? How efficient is it? Also, how practical is it when using it in a game?

Thank you.

The most effcient in terms of memory speed etc is the A* algorithm (its used in loads of games). The A* algorithm is based upon the dijkstra algorithm but includes a heuristic(guess) element. Thats going to be my next article, and if you grasped my dijkstra article, A* should be trivial

Cool. I'm looking forward to that article. When will get it get posted? Will it get posted here on this site (I am already liking this site, btw).

I'll probably do a write up this weekend of the A* tutorial, maybe a few diagramd to show the different approach, apex will sort the formatting and then whoop it on

Great, thank you so much!

Is a heuristic usually just a bit of pythags to find he distance (maybe taking into avg. tile cost too), or is it a lot more complicated than that? How accurate is a guess (I know, more the better in efficiency)

Thanks for this tutorial!

Ed Mack your virtually there, basically there are 3 major types eulian which you mention and also arrrg (grid x,y) based. They merely make going to your destination more attractive, thus your likely to get there earlier. Why is this important? Well our dijkstra algorithm finds EVERY path to EVERY node. The A* algorithm stops when it finds the destination node.


ANd your right about talking average tile cost it works by



Attractiveness of edge = Distance from goal + edge weight.


When adding to the shortest path special value though, we only add the edge weight, its not accumulative with the distance from goal

Russell Long??

sorry...

* bump *

Any ideas of when the next article in the series will be up?

This algorithm is quick for small boards ie 5x5, 10x10, at most 20x20. What about a big 100x100 or 200x200 board with 10.000 and 40.000 nodes. It would be inefficient. Pre-calculation of the paths would not only be too memory consuming (you'd have to save every path for each pair of positions (or areas) ). What i have thought and trying to implement (damn it i quit easily whenever i have to think ;-)) is to creating a picture map (a monochrom would be enough: white for passable terrain - black for non passable terrain) and making line tests. That is to check every pixel in the line joining start and end and if we find a black pixel we "crawl" around the obstacle until we find a point that "sees" the end point. So we find all posible paths, we "stretch" them (that is if we have 10 points in the path and 1st "sees" the 3rd or 4th then we delete the between points (needless : a straight line is the quickest way)) and then get the quickest path (simple if we just count the distances - complex if we compute the terrain speed so we also have to compute the non-"stretched" and semi-"stretched" paths). It must surely quickest than computing all the pixels around the start point until we find the path. If you'd like a more carefull description of the "algorithm" please tell me to write an article to present it.

Now i dont want to take the credit for this (truly divine i must confess ;-)) algorithm so if you have seen a good description of it or something like that please tell me to know. Else i will have to give my name to it and get all the fame and recognition to hope that in the future they will say how did Costas beat up Dijkstra (;-) ;-) ;-))

If dijkstra doesnt meet your needs use A-star (A*) This is pretty much the fastest for general pathfinding.

I really wanted to learn more about this, im not english so its kind of hard to understand it, what do u mena by relax edges ? and what happens when 2 edges adjacent to a node have the same height ? can someone help plz ?

No ofense intended in the following comments. Just to show you why your article is uneffective.

It was suposed to be an introduction to Pathfinding, and it all went well until I got to:

EdgeWeights[node1][node3] = 999999999999999;

What on earth is that suposed to mean?!

And then you just keep talking about a heightmap which I know what it is but, due to the nature of the article, you should have explained and made a graphical example.

Then you keep your 999999... madness with the specialDistance[MAX_NODES] without explaining why it should be set up at a large number.

Advancing through the article, ideas become more confusing, and even with patience, no true beginner would make it to the end.

Your technical knowledge is O.K. , but the article's rough walkthrough makes it badly named, considering the word 'introduction' in the title.

If you had read the article more carefully, you would have noticed the following line:

But what if there exists no edges between nodes!! Well you'd have to have a number that’s large i.e. take it as infinity, which will be used to indicate no edges exists. That is... 999999999999999

It might make the code more readable to define a constant, like

const float infinity = 999999999999;

and use that instead of hard-coding the extremely large value. In fact, what's even better is to use

#include <limits>
const float infinity = std::numeric_limits<float>::infinity();

as this gives you the true floating-point infinity value, which is guaranteed to compare as greater than any finite floating-point value.

We have a series of nodes, with edges. This is our first consideration, we need to know which nodes are connected before we start (a limitation of dijkstra's algorithm). For this article we'll use a 2D array, in which we store the edge weights. The maximum number of edges that could possibly exist would be:

    Number of Nodes * Number of Nodes

This is wrong. The maximum number of nodes for Djikstra's Algorithm is n(n-1)/2, where n is the total number of nodes in your graph. This is because Djikstra's does not consider a node having a path to itself, nor does it consider a path being traversed from different directions as possibly having different weights (e.g. EdgeBA has weight 5, but EdgeAB has weight 3).

Originally Posted by Brullig

We have a series of nodes, with edges. This is our first consideration, we need to know which nodes are connected before we start (a limitation of dijkstra's algorithm). For this article we'll use a 2D array, in which we store the edge weights. The maximum number of edges that could possibly exist would be:

    Number of Nodes * Number of Nodes

This is wrong. The maximum number of nodes for Djikstra's Algorithm is n(n-1)/2, where n is the total number of nodes in your graph. This is because Djikstra's does not consider a node having a path to itself, nor does it consider a path being traversed from different directions as possibly having different weights (e.g. EdgeBA has weight 5, but EdgeAB has weight 3).

i was just about to query this - didnt think it made sense if there is only a maximum number of 2 edges to 1 node - thanks for clearing this up