Preface

This will be my first tutorial for Devmaster.net and certainly not my last, bear with my articles they will have mistakes but they will be rectified, before I go on I'd like to thank Gamedev.net and also Game Tutorials for their informative articles.

Note: These articles won't provide the most data structures but the most relatively easy way of implementation. Using the information and your brain, you should easily be able to improve the code!

Introduction

I see algorithms expressed as mathematical formula all the time, yet I always find it difficult to break down and digest, so these articles will veer away. In essence they'll be rather wordy and simplistic, but will gradually increase in complexity.

First off some terminology you'll need to know:

Node/vertex

These are your destinations, if you've ever played Civilisation, then each tile is a node, or alternatively a computer on a network can be seen as a node.

Edge

These are what connect nodes/vertex's together. A single edge or several edges combine to make a path.

Weight

This is the cost of an edge that connects two nodes together. Usually this is usually decided from the distance between 2 nodes but can also be modified by other factors.

This can be pictured by looking at terrain. A node that starts at the bottom of a mountain and has a edge that connects to a node at the top of a mountain will have a large weight (hard to get there!). But two nodes on a flat even terrain will have a edge that has a low weight. Other considerations: not all nodes will connect together and a node can only be connect to another once (i.e. it has only one edge). This article won't comment on how weighting should be made and considered, that’s a design issue for you to ponder.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from the source/root node (this can be seen as a player/units position), using a greedy approach (i.e. it doesn't back track it sees the best option, takes it and doesn't look back), to all the nodes! Onto what we know so far.

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

So we initialise our array size to:

    EdgeWeights[MAX_NODES][MAX_NODES]

Next we populate the arrays, i.e.:

    EdgeWeights[node1][node2] = 7;        // node 1 and 2 are connected and have a edge of value 7
    EdgeWeights[node2][node3] = 4;        // node 2 and 3 are connected and have a edge of value 4

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:

    EdgeWeights[node1][node3] = 999999999999999;

This data should be created automatically from within another part of your program such as a heightmap (e.g. you have lots of canyons, and use this algorithm to find the quickest route to a point on the other side of the map).

Next we need another array initialised to:

    SpecialDistance[MAX_NODES] = 999999999999999;

IMPORTANT: At this point, set our root (node/vertex) player's position SpecialDistance to 0!!, this is essential. This will be explained later. And another:

    Predecessor [MAX_NODES] = 0

This array stores from which node we came from, i.e.:

    Predecessor [4] = 2;        // would represent that we are at node 4 and
                                // we got to node 4 from node 2.

We also need a priority queue ordered by SpecialDistance[MAX_NODES]. The priority queue works like this, add all of the 'SpecialDistances' to a queue, arrange into a priority queue by moving all those with lowest values to the front (the lower the value, the higher the priority). Every time we process a node we remove it from the queue and update.

So this means we have the following arrays:

    EdgeWeights[MAX_NODES][MAX_NODES];
    SpecialDistance[MAX_NODES];
    Predecessor[MAX_NODES];

The PriorityQueue of SpecialDistance[MAX_NODES] should have our start position at the front (since we set its value earlier to 0! ). Now for the guts of the algorithm:

While (priority queue not empty)
    CurrentNode =  highestpriority
 
    Remove node from priority queue
 
    For every node with a edge to CurrentNode, and is in the priority queue
        If SpecialDistance [node] > SpecialDistance[CurrentNode] + EdgeWeights[CurrentNode][node] then 
            SpecialDistance [node] = SpecialDistance[CurrentNode] + EdgeWeights[CurrentNode][node]
 
 
Remove SpecialDistance[CurrentNode] from priority queue
 
Set Predecessor[node] = current node

Reorder priority queue

SpecialDistance is the current shortest path from the root/source found so far to a particular node. If another special distance is found with a lower value than that, then the lower valued node becomes the special distance. Confused still? Here's some step by step diagrams to show what happens. On the diagram we have 9 nodes with an obvious shape. Node number (1) is our root/source node. Follow the diagram and try to relate it to the pseudo code:

Red node indicates current node,
Blue line indicates neighbours tested,
Red text indicates special value
Black Numbers indicate edge weight

We're at the root/source node, our neighbours at 2 and 4. We check their SpecialDistance value, which is infinity and check if we have a better value:

    If SpecialDistance [2] > SpecialDistance[1] + EdgeWeights[1][2]

In this code we know that SpecialDistance[2] = infinity, and that SpecialDistance[1] = 0, so only the edge weight to the neighbours matter in this case. So SpecialDistance[2] = 0 + 1. The same approach applies to node 4:

The priority queue has set the current node as number 2 since it has the lowest SpecialDistance value. So

    If SpecialDistance [3] > SpecialDistance[2] + EdgeWeights[3][2]

Results in, SpecialDistance [3] == infinity, and SpecialDistance[2] == 1, giving us SpecialDistance[3] = 1 + 2

Same approach as above nothing fundamentally different

This is where the greedy aspect of the algorithm kicks in and why the SpecialDistance value is important. Node 5 had an edge both to node 4 AND node 2, but the edge from node 2 has been dumped in favour for the edge connecting to node 4. Why? Lets look at the code and see. We know already that node 5 already has a SpecialDistance value of 6 set, but we never moved to node 5 since it had a high SpecialDistance value giving a low priority, since we moved to node 4 however this has happened.

If SpecialDistance [5] > SpecialDistance[4] + EdgeWeights[5][4]

                    6  >        3           +        2