OutlineThis post will cover the basics of Dijksta's shortest path algorithm and how it can apply to path finding for game development. It is my opinion that understanding this algorithm will aid in understanding more complex AI algorithms, such as A*. This post is aimed more towards developers starting out in game development or those curious about Dijkstra's algorithm, but this will be a somewhat simplification of it and discuss mainly the concepts.
What's an algorithm?An algorithm is basically a system for solving a problem. For us humans, looking at a 2D grid with many objects we can easily tell which path the character should take to reach his or her goal without thinking much about it. What we want to try to do is translate those semi-subconscious mental steps to a list of steps that anyone (or a computer) can repeat to get the same answer every time. Finding the shortest route from one object to another when developing game AI is a very common problem and many solutions exist. At least in 2D grid / tile based games, perhaps the most common one is A*, with Dijkstra's being also quite good. Depending on the complexity of the game, Dijkstra's algorithm can be nearly as fast as A*, with some tweaking. A* is generally a better implementation, but can be slightly more complex, so I'm going to discuss the fundamentals of Dijkstra's algorithm and in later posts talk about others, such as A*. I'll be using the word graph here a lot, and it may not be immediately obvious how this translates to game dev, but you can easily translate this to 2D grid or tile based maps.
Dijkstra's AlgorithmLet's first define what exactly the problem is. Take this graph, for instance.
How it worksFirst we'll describe Dijsksta's algorithm in a few steps, and then expound on them further: Step 0
Temporarily assign C(A) = 0 and C(x) = infinity for all other x. C(A) means the Cost of A C(x) means the current cost of getting to node xStep 1
Find the node x with the smallest temporary value of c(x). If there are no temporary nodes or if c(x) = infinity, then stop. Node x is now labeled as permanent. Node x is now labeled as the current node. C(x) and parent of x will not change again.Step 2
For each temporary node labeled vertex y adjacent to x, make the following comparison: if c(x) + Wxy < c(y), then c(y) is changed to c(x) + Wxy assign y to have parent xStep 3
Return to step 1.Before diving into a little more tricky graph, we'll stick with the original graph introduced above. Let's get started.
Step 0.Temporarily assign C(A) = 0 and C(x) = infinity for all other x. C(A) means the Cost of A C(x) means the current cost of getting to node x. The following graph has changed a little from the one shown above. The nodes no longer have labels, apart from our starting point NodeA and our goal NodeB.
Orange line - path to parent node Yellow arrow - points to the node's parent Green node cost text - node cost is permanent White node cost test - node is temporary Yellow highlight - Current nodeWe assign a cost of 0 to Node A and infinty to everything else. We're done with this step now.
Find the node x with the smallest temporary value of c(x). If there are no temporary nodes or if c(x) = infinity, then stop. Node x is now labeled as permanent. Node x is now labeled as the current node. C(x) and parent of x will not change again. Since 0 is the lowest value, we set A as the current node and make it permanent.
For each temporary node labeled vertex y adjacent to x, make the following comparison: if c(x) + Wxy < c(y), then c(y) is changed to c(x) + Wxy assign y to have parent x There are two temporary nodes adjacent to our current node, so calcuate their cost values based on the current node's value + the cost of the adjacent node. Assign that value to the temporary node only if it's less than the value that's already there. So, to clarify: The top node is adjacent to the current node and has a cost of infinity. 0 (the current node's value) + 1 (the cost associated with the temporary node) = 1, which is less than infinity, so we change its value from infinity to 1. This value is not yet permanent. Now, do the same calucation for the next adjacent node. which is the bottom node. The value is 0 + 2 = 2, which is also less than infinity. To illustrate: [attachment=24272:sp_1_2.png] So we now have looked at each temporary node adjacent to the current node, so we're done with this step.
Return to step 1.So, let's go back to step 1. From this point forward, I'll be using the term iteration to describe our progression through the graph via Dijkstra's algorithm. The steps we previously took I'll refer to as iteration 0, so now when we return to step 1 we'll be at iteration 1.
Iteration 1We're back at the first step. It says look for the smallest temporary cost value and set it as permanent. We have two nodes to look at, the top node with cost 1 and the bottom node with cost 2. The top node has a cost of 1, which is less than 2, so we set it as permanent and set it as our current node. We designate this by a yellow shadow in the image. Now, it is important to keep in mind that the bottom node still has a temporary cost assigned to it. This temporary cost is what allows the algorithm to find actual cheapest route - you'll see in a second.
Find the cheapest node. Done, it's set as permanent and our current node is this one. This node value will not change. [attachment=24273:sp_2_1.png] The yellow highlight indictates the node we are currently on, and the green text means the node cost is permanent. The nodes with white text for their costs are temporary nodes.
Assign cost values. There is only one adjacent node to our current node. Its current value is infinity, which is less than 1 + 10, so we assign 11 to its temporary cost value. [attachment=24274:sp_2_2.png] This is not the shortest path from NodeA to NodeB, but that's fine. The algorithm traverses all nodes in the graph, so you get the shortest path from a node to any other node. You can see that the shortest path from NodeA to the top node is the line between NodeA and the top node - well, of course, you say, because that's the only possible path from NodeA to the top node. And you are right to say that, because it's true. But let's say we have a node above the top node (we'll call it Top2). The shortest path to that would from NodeA to the top node to node Top2. Even though our goal is to go from A to B, as a side effect we also get the shortest route to every other node. If that's a bit unclear, it should clear up after we go through the next iteration. Done with step 2, let's continue to step 3.
Return to step 1.
Iteration 2Ok, so now we look again at the temporary nodes to see which has the lowest value. Even though we calculated the temporary value of B as 11, we are not done because that value might change (in this case, it will definitely change).
Pick the cheapest node from the remaining temporary nodes. Set it as the current node, make it permanent, and then assign the parent. Let's take a look at the graph to elucidate a bit. We have two remaining temporary nodes. Out of the costs 11 and 2, pick the cheaper node (2). We set this node's value to be permanent and assign its parent is NodeA, demonstrated by the arrow. [attachment=24275:sp_3_1.png]
Assign cost values to temporary nodes adjacent to the current node. Again, like in the previous iteration, there is only one node to do a cost calculation on, as there is only one temporary node adjacent to the current node. This adjacent node is NodeB. So, we check to see if 2 + 5 < Node B's temporary cost of 11. It is, so we change Node B from 11 to 7. [attachment=24276:sp_3_2.png]
Return to step 1
Iteration 3Almost done.
Choose the cheapest temporary node value. There is only one temporary node remaining, so we pick it and set it as permanent, set it as our current node, and set its parent. [attachment=24277:sp_4_1.png]
Assign costs. There are no temporary nodes adjacent to Node B (there -are- permanent nodes, but we don't check them).
Return to step 1.
Choose the cheapest temporary node. If none exists or c(x) = infinity, then stop. There are no more temporary nodes and no nodes have values of infinity, so we're done. Algorithm has finished, and we have our shortest path from A to B, but also from that node to every other node in the graph. With such a small graph as this, it's not immediately obvious how powerful and useful this algorithim is.
Another ExampleSo, on to a more complicated graph now.
A is our starting point, and B is the ending point. Now, we could just as well apply this to a 2D tile based game where A could represent an NPC and B could represent the NPC's desired destination. If you take a minute, you can probably find the least expensive route yourself. As mentioned earlier, it's fairly trivial for us to come up with the answer, what we need to do is figure out how to convey the steps we take to more extensible steps that can be repeated by a computer for any graph. For this graph, I won't be as thorough explaining every step, but the exact same process is applied. Instead, I'll just provide an example of a slightly more complex graph and what it would look like using Dijkstra's algorithm.
Temporarily assign C(A) = 0 and C(x) = infinity for all other x. C(A) means the Cost of A C(x) means the current cost of getting to node x So what's this mean? Well, our start point is A so c(A) = 0 means assign A a cost of 0 and set the cost of x for every other node to infinity. Like the following [attachment=24278:shortest_path2_1.PNG] We assign a cost of 0 to our starting node A and a cost of infinity to every other node. As before, none of these costs are permanent yet.
The node with the smallest temporary value is node A with a cost of 0. Therefore, we're going to make it permanent - meaning c(x) and the parent will not change. [attachment=24279:shortest_path2_1_a_selected.png] The 0 will not change now. If there are no temporary nodes, or if c(x) is infinity, the algorithm stops. Now, step 2.
Basically, we're going to look at all the nodes that are connected to the currently selected node and calculate the cost to get to them. If the cost of y is less than what it previously was, it will change - this will be discussed soon. So, let's first calculate the cost to get to the adjacent nodes. The cost is based on the value of the current node code plus the edge (node path) cost. Right now, since this our first go, the cost of our current node is at 0 since we haven't done any traversals. So, let's start to figure out the c(x), the node costs. [attachment=24282:shortest_path2_1_a_selected_3.png] Notice the yellow arrows. I'm using them to designate what node it got its cost from. Here, since there is only one possible parent node, they all point to the same place. For the three nodes adjacent to A, we add the values of the edge and our current node (value of 0). So, the top node is 0 + 3 = 3, which is less than the current value (which is infinity), so we apply the value of 3 to the node. Then, the middle node 0 + 7 = 7, also less than infinity. Finally the bottom node has a value of 0 + 5 = 5, which is less than infinity. Therefore, the top node has a c(x) of 3, the middle a c(x) of 7, and the bottom a c(x) of 5.
Return to step 1As before, we just iteratively go through graph applying the same steps. So, walking through this - as step 1 says: We find node x with the smallest temporary value of c(x). So, out of the three temporary nodes with values 3, 5, and 7 that we just worked out, the smallest value is 3. We then make this node permanent.