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.