Dijkstra's Path Finding Algorithm
Author : Jack Hoxley
Written : 26th January 2001
Contact : [Web] [Email]
Download : GM_Dijkstra.Zip [62 Kb]

Contents of this lesson:
1. Introduction
2. The Problem
3. Solving it using a graph
4. The Data Structures
5. Dijkstra's Algorithm
6. Making this work in code
7. Enhancing the Algorithm

1. Introduction

Path finding is a crucial part of almost every game, and has been for a very long time. Take your average strategy game - Red Alert for example - select a unit and click somewhere on the map, off the unit goes until it gets to the location - how did it get there, why didn't it get stuck anywhere? The reason being that it used a path finding algorithm of some kind. Even games like Quake/Unreal use path finding - your character may not, but how does the enemy get from A to B?

There are many forms of path finding, graph based, natural, bump 'n' grind, tracing, orbital... each subset with many different implementations, or complete hybrids of both. Depending on the type of game and the players view point, selecting a good path finding algorithm is essential - an RTS game using the bump 'n' grind method (where it drives into a wall, changes angle a bit, drives into the wall, changes angle again - until it gets around the object) would look awful - the player would be able to watch his crack, highly trained army tanks driving into rocks and trees quicker than a learner driver... Natural algorithms (modelling genetics) are by far the best type of algorithm for path finding - for looks anyway; they simulate (theoretically) how our minds solve the problem of path finding; but unfortunately they aren't really a realistic option just yet - they require vast amounts of memory and quite a bit of processing power - which isn't good for the current set of computer hardware available.

By the end of this article you will be able to construct, with ease, a path finding module for your game - lightning quick and very simple as well. This algorithm can traverse a fairly simple map in a fraction of a millisecond - anything from 1/10000th to 1/1000000th of a second - which is pretty damn fast. After we have our path, all we need to do is follow it...

2. The Problem

Take a blank map - just a flat terrain, choose a point A and B, to get from A to B you just follow a vector between the two - not too complicate really. Introduce something as simple as a tree in this landscape and it gets a whole lot more complicated - if the line between AB is blocked by the tree we either have to walk through it or walk around it - which isn't too difficult in this case, just sidestep, go around and get back on course again. Introduce a more complicated set of obstacles - caves, paths, forests, cliffs, buildings - and it gets even more complicated; so complicated that you probably wouldn't be able to get to where you want to without getting stuck somewhere. Take this picture for example...

On the above picture you can see two paths - "As the Crow flies" and "As the Crow Walks", assuming that the unit cannot actually fly over the obstructions you can instantly see the problem with the straight (red) line method. Instead we would have to take the blue line - and walk around and between the various obsticles on our route.

So, to put it simply, the problem is - how do we mathematically (and programmatically) calculate a path from A to B in a similiar style to the blue line?

3. Solving it using a graph

Now we've outlined the problem we can start thinking about how to solve it. The easiest, fastest and most realistic looking method is by using graphs. Not graphs like bar-charts and line-graphs that you may be used to - network graphs. The following illustration will explain:

The blue lines and red dots are the graph, and as you can see they extend to almost every place on the map. A bit of terminology for you: The red dots are vertices (plural of vertex) and the blue, connecting, lines are called edges. Some people call them nodes and arcs, but they all mean the same thing.

To construct a graph the first thing we need to do is place the vertices, these should be key points that extend into all the little nooks and crannies of our world, this example uses 40 of them, but you can quite easily go into the hundreds before it starts to slow down to much. The key point to remember when placing these vertices is NOT to put them too close together, and not put them too far apart. Each vertex needs to be able to "see" another vertex along a straight line, in order to do this you may need to add additional vertices to the world. The order that they are placed in doesn't really matter a great deal - but some sort of logical pattern will help slightly later on.

The next step will be to work out where the edges go, if you take a quick look at the above illustration you'll see that each vertex has at most 4 edges coming out of it, and that all edges have a start and end vertex. I've programmed the algorithm to only use 4 possible routes from one vertex purely because of processing power, as we'll see later on the algorithm needs to analyse each vertex connected to the current vertex before it'll move on - having 100 possible edges coming from one vertex will quite obviously cause a slow down; should you need more than this you can easily increase it to 5 or 6, but many more than that and it might start slowing down.

Just a little bit more complicated now, as I said before, a logical pattern to numbering is quite useful - in this case it tends to go left-right and back again. With this information we can now construct our edges, we know what vertices there are, we know how to identify them (through the number). Visually we can tell that vertex 17 connects to vertices 10,12,20 and 21 - if we store this information we can draw a line between vertex 17 and all the vertices it connects to. Do this for every vertex on the map and we have ourselves a graph. This part will almost certainly be done by a level designer pre-runtime and then saved out; it would be fairly slow to generate them at runtime; and anyway - you fancy writing an algorithm that designs a graph for the level? I didn't think so...

4. The Data Structures

Now we get onto the fun part, writing the code to hold all this data. At first glance it looks fairly simple, but there are several ways in which it can go wrong (I tried a few methods before getting one that I liked). The data that we need to store can be contained in two UDT's :

Not too complicated really, but some explaining is required. The type NodePoint could probably be integrated into the TreeNode structure, but I prefer it this way around, makes things slightly easier I think. First we create an array of nodes based on the constant nNodes (40 in this case), this array represents the red dots on the diagrams above. Next we create a TreeNode structure, this acts as a set of extended information on the red dots, where each node connects and how far. The CurrNode member points to an entry in the NodeList( ) array, so if we want to find the actual coordinates of the point we could use something like:

NodeList(TreeNodeList(n).CurrNode).X , NodeList(TreeNodeList(n).CurrNode).Y

and if we wanted to look at a node that this one connects to we can analyse the the NextNode( ) property:

TreeNodeList(TreeNodeList(n).NextNode(0)).CurrNode

Which will query the node connected to the current node n for which NodePoint it's using.

Lastly we create an array of these tree nodes the same size as the number of actual nodes there are - effectively saying, one tree node per node. You may well think that some nodes, on the very edge of the graph, dont need a TreeNode structure - that's wrong. If we know how to get there we also need to know how to get back, when we're sitting on this node we'll have no information about any other nodes that we can get to - even though we just travelled here. In general each node will reference the one it's come from and the one it's going to - so that we can go back and forth around the graph quite easily...

Filling these structure is quite easy, the sample code (and this article) wont go into how you can load/save the data, or let the user decide where the nodes are, all of it is hardcoded into the Form_Load procedure. This should be avoided at all costs for a proper game, but for this example it really doesn't matter a great deal. It looks like this though:

The only thing to note about this is the inclusion of -1 in the NextNode( ) properties. As explained, the NextNode( ) member points to an entry in it's own array - therefore it must be a + real number and within the array boundaries - which makes -1 an error (you dont have a -1 entry in an array). Later on we'll be including logic that ignores any NextNode( ) entries with a value of -1, which will signify that there is no node to go to from there, which if you think about it is perfectly reasonable, not every node should have or need 4 subsequent edges coming out of it...

Lastly we need to fill in the Dist( ) members, the reason that these are included will become clear later on, but the calculation for getting the distance between two points isn't as fast as I'd like, so pre-calculating it is preferable. So after we've filled out all the data structures we need to run a loop through all the TreeNodeList( ) entries calculating the distance between it and the connected node. The code for doing this looks like:

Looks quite complicated doesn't it - well it isn't. The GetDist2D( ) call is so long partly because of the long names of variables I've used and partly because it requires 4 parameters. Also note the precursor to each calculation: If Not (TreeNodeList(I).NextNode(0) = -1) Then which basically says "If the next node is anything other than -1 we'll calculate the distance", as mentioned above, -1 indicates that the branch does not go anywhere.

5. Dijkstra's Algorithm

In 1959 Dijkstra designed an algorithm to solve such a problem. Take a series of vertices interconnected by edges, each edge has a weight (in this case the distance) and we know the start vertex and the end vertex.

Before we begin to think about making some code for this algorithm we need to understand how it works, which fortunately is very simple - I picked it up in 15 minutes from my maths book. First I'll explain the stages required to find the path, then I'll run through a simple mathmatical example:

Step 0: Preparation
We're going to be doing several calculations and needing to store numbers. These can be setup in the following table:

Take the following graph network, okay, you can probably calculate the shortest route easily, but we want to do it using Dijkstra's algorithm.

Task: Find the shortest route from 1 to 5, where the black lines are edges, red dots are vertices, blue numbers are vertex numbers and the green dots are the distances (made up) along the edge.

Step 0 & 2: Draw our table, and add the first vertex

Step 3 ( i ) : Vertices 2, 8 and 9 can be reached from vertex 1, we need to work out their temporary variables and add them to the table:
Vertex 2 Temp = 0 + 2 = 2
Vertex 8 Temp = 0 + 3 = 3
Vertex 9 Temp = 0 + 3 = 3

Step 4 ( i ) : Choose the lowest temporary value from all the unvisited vertices. In this case it will be 2. We move here.

6. Making this work in code

As you'll agree (I hope), it's much better to let the computer work out the path for us - there's probably about 5 A4 pages of tables and workings in the previous section - and for a relatively simple graph. Fancy calculating the path around an office block? 1000's of nodes? didn't think so....

Also, considering the fact that the computer would of done all the above work in under 1ms ....

Onto the main feature then - converting this algorithm to visual basic code. We already have the data structures setup (section 4), so all we really need to do is design a function that takes a start and finish vertex index, and spits out a path that we can follow from A to B.

The first thing we need to do is update our TreeNode structure so that we can store the table information. We also need to setup an open ended array where we can dump the finalised path in. The updated structures look like:

Everything else remains the same. Now we move onto the actual pathfinding code. Before we start doing the proper searching we need to lay the ground work:

Above is the function header, the variables that are required and the ground work that needs to be done. The first stage is to check if where we're going is where we're at - in this case it just returns a path starting and finishing in the same place; hopefully the calling function will have checked this already (and decide not to call the function). Next we run through each node setting some default values for the table entries - in particular the .TmpVar value is set very high, hopefully we wont get a graph where we're using edges 100,000 or more in length (cant imagine what would really make use of something like that). Then we do stage 2, make the source node the first visited with distance and temporary variables of 0.

As you've already seen, the Dijkstra algorithm comes in two parts, visiting and marking the vertices and then tracing the route back. The first part of marking the vertices is shown here. Note that it's effectively an infinite loop, whilst it's unlikely to get stuck on a complete graph if you start modifying the algorithm (see the next section) you could introduce states where the destination cannot be reached - in this case the loop would never terminate. The next section uses a time-out clause that breaks out after a certain time period if no path can be found, if we dont have this the loop could continue for ever (or until windohs crashes). If you think that your implementation will incur this scenario then you should include a time-out clause in this loop as well.

the above is fairly explanatory, and identical to the worked example above. The only reason it looks complicated is because of the large identifiers/names used and the large number of logic statements that need to be evaluated.

The next part of the function looks equally scary, but is actually very simple. The core code is actually repeated 4 times for each of the possible child nodes, so you only need to understand the first one and you'll understand all the others.

Looks complicated doesn't it. After we've decided that the vertex is part of the path we increase the size of the pathlist by 1 and add the entry in the new space, before setting the current node to be the new path entry we found - and then carrying on. If we get a situation (as in the worked example) where there are two possible paths to take this code will take the first found, as you can see, when it finds a valid vertex it skips straight to the end of the loop, so if there is a valid vertex on NextNode(0) and NextNode(3) it'll evaluate (0) and then skip straight to the end - it wont even look at (3).

The final part of the code is to reverse the function, if you were really looking to save time and speed up this algorithm (as if it isn't fast enough already) you could remove this next part and read the array backwards - but I find it easier to read it start-finish.

Not too complicated really, we create an array the same size as the path list, run through the original array backwards copying the data in the correct order into the temporary array, then we copy the temporary array back to the main array. And then we've finished.

At this point in time we have our path finding algorithm completed, if we feed in two indices to nodes, and the relevent structures are filled out correctly it'll fill out an array with the path to take - what more could you want? The code in it's current form is extremely simple to adapt (see the next section) and easy to implement into other projects - just copy the code and structures across, fill them as you require and off you go....

7. Enhancing the Algorithm

In the final section of this mammoth article I want to discuss improvements and alterations that you can make to this algorithm. Whilst it is a perfectly functional algorithm and works 100% of the time on all properly created graphs there are several things that I thought about changing - and it is quite possible you have several adaptations you may want to add. Here's my list:

Edge Weighting
Currently the "weight" of an edge is just the distance between it's start and end vertex. This is fine, but what if we want to disuade the player from going down one route - or in certain circumstances stop them going down a route altogether. One example of this would be a landscape with a swamp and a path. You're standing on one side of the swamp and you want to get across to the other side, if you make a network that joins you directly to the destination, but also goes around the swamp as well, it's almost garaunteed that the path across the swamp will be shorter, therefore the chosen route; but in real life it would be easier to walk around the swamp than walk through it. You could decide on a weighting system so that any edge going over a swamp gets a weight 2x the distance, which will almost always make the Dijkstra algorithm choose the path around the edge, even more so if you weighted that path with a 0.5x multiplier. You could also include conditional logic for an edge, if the player has wading boots let him/her use the path across the swamp, or if the player is in a hurry / running away from something let him/her use the path across the swamp.

Moving the Player
This article as only covered finding a route from one point on the graph to another. Unless you have a pointlessly complex graph 99% of the time the player will not be standing on top of a node. Hopefully the player will be standing quite close to one though - and if you scan the network to find the closest node you can vector the player towards that node, then once on the graph you can move them around using interpolation, then once at the end you can do the reverse of getting onto the network. You may well want to set it up so that the player has to choose a node within n distance of itself, otherwise you may well get natural pathfinding problems just getting it to the network. Take a couple of steps back and I mentioned interpolation - whats that then? If you haven't heard of it before it's the process of blending a set of values between the start and end values by a given amount. Use the formula (B * V) + A * (1.0 - V) for this, where A is the source, B is the destination and V is the distance between on a 0.0 to 1.0 scale, where 0.0 is at A and 1.0 is at B. In order to follow the path decide what the start vertex is and the end vertex is, then frame-by-frame move between them, when you're at the destination switch it so that the previous destination is now the start and the destination is now the next vertex in the path list...

Path Variation
You may also encounter the problem of predictabilty when using any graph based algorithm, if the player can see a birds-eye view (as in Red Alert) he/she may well be able to remember the exact route that the AI characters take (or their own), in doing this it can look very unnatural or can lead to poor gameplay (or advantages to the player). To combat this you could either make more could make more complex graphs, but this wouldn't actually work, the algorithm would still pick the same shortest path every time; alternatively when moving along the path you could add or subtract a random amount from the start/finish nodes - this way it wouldn't always end in the same place or start in the same place; this would have to be carefully controlled - small variation in confined spaces, large variation in wide open landscapes.

Beyond linear
Currently the lines drawn between the nodes are always straight lines. If you wanted to make it more natural you could use curved lines between the nodes - but these would have to be closely checked in the editor - the whole point is that the lines dont intersect with any un-passable objects, which is quite likely to happen with curves when in confined areas. If you're using this method with DirectX8 you can make use of the D3DXVec3Hermite or D3DXVec2Hermite to do curved interpolation for you.

C/C++ DLL
Whilst not everyone can also program in C/C++ this algorithm would be very easy to port to a C/C++ DLL for use in VB. Whilst it's already quite fast I haven't tried it on networks with 1000's of vertices in them - if you do find it slows down to much you may well want to consider this option.

Generating the Graph
One very easy way of generating a graph network that I believe Half-Life uses (and probably others as well), is to make the level editor only have to place the vertices, the editor then runs through the 4 closest vertices and puts an edge in - whilst checking if the edge intersects with any solid/impassable objects. Whilst not entirely necessary, it does make it easier for the level designer.

Storing the graph
As mentioned above, the graphs will probably be generated by an editor and saved, rather than generated at runtime. Storing them using VB's binary file access is extremely extremely simple. Use this code snippet to save all the data that this example uses, and to load it again:

You could also save a matrix of possible routes, depending on your graph size it would not be very big at all. In this example I've used 40 nodes, if each of these nodes can visit 39 other nodes (40 including itself) then a simple 2D array would be capable of holding all the possible paths. On average each path appears to pass through 8 vertices, if these are stored as integers (2 bytes) that would require 16 bytes per path stored; 40x40 is 1600 possible paths, which if 16 bytes in length would add up to 25600 bytes, or 25kb - not a particularly large file. This would then require that you never needed to search for a path during the actual game - just look it up in our table; this is fine if the weights of the edges never change - but as mentioned above you may well want to dynamically affect the paths chosen, in which case this method would be useless. For your information, a 100 vertex graph would require 156kb to be stored, maybe less if compression was used.

Things to bare in mind when designing the graph
There are several things that you should bare in mind when designing the graphs for this algorithm, whilst writing the sample code for this I made a couple of mistakes with the edges and it made areas of the graph inaccessable and certain nodes could not be reached. To guarantee that you'll have no problems write a test that checks if every node can be reached by every other node - similar to the 2D lookup table mentioned above, if this is satisfied we call it a Complete Graph. The other thing you need to bare in mind are cycles - or loops. If you design your graph so that there are cycles in it you may well find in the odd situation an area of the graph that once entered cannot be exited, or as far as the algorithm is concerned a solution will not be found.

Directional graphs
Something that I haven't covered yet are diagraphs - directional graphs. Currently, as long as the vertices are connected we can travel both ways - from and to. Whilst it's perfectly possible with the current code to design a graph like this, you may well want to add an option so that you can only travel one way along an edge. During the Dijkstra search you can add additional logic in the same place as it checks if "NextNode(0) = -1". If you decide to add this option you have to be aware of two potential problems - sinks and sources. A sink is a vertex where all edges come into it, but none leave it, so once your at that vertex you cant leave again, and with sources you cant get there because all edges point away from it (the only way you can get there is if you start there).

3D graphs
The final thing I can think of is changing this so that it's in 3 dimensions, which is actually so simple it hurts. Change the NodePoint structure to include a Z value, then alter the GetDist2D to be GetDist3D and thats it - the algorithm will adapt fine and carry on working as per normal.

Well done, you've survived a mamoth 24 (A4) page article. If you liked this or found it useful drop me an email at the address at the top of the page (if you can be bothered to scroll up again). If you do you can pick up the source code while you're there...