This is the first article I am writing for this blog. I would like to address Dijkstra’s pathfinding algorithm. You might be wondering why I chose this specific subject for my first article. Well the answer is very simple, I already had this article written for an assignment in the past and for testing purposes I decided to put it up.
Dijkstra’s algorithm is used for finding the shortest path from a random point A to a random point B in a random maze. This text is for people who are already familiar with programming. The tutorial isn’t limited to a particular programming language. I wrote my version in C++ (in combination with OpenGL). At the end pseudo-code is given for those willing to write their own version of the algorithm.
Before we can start thinking about the algorithm we first have to write a skeletal program which contains some sort of maze and a starting and ending point. My version of the skeletal program is show in figure 1.
The maze consists of 16 x 12 squares. The green square is the starting point and the red square is the ending point. Blue squares represent walls. Now that we have made this program we can start implementing the pathfinding algorithm into it.
The program has to create two lists of variables. These are called the open-list and the closed-list. The open-list contains the coordinates of the squares that we probably have to check and the closed list contains the coordinates of squares that we need to find the shortest path (we’ll get back to this in a minute). Our search begins by selecting the starting square as the current square. The current square is the square that we are looking at. The next step is to put all adjacent squares (except walls) of the current square on the open-list. We also have to calculate a value for each of these squares. This first step is shown in figure 2.
Fig. 2 – step 1
Here we can see that the squares around the starting point are highlighted with a value in the left-bottom corner. This value is also called the G value of this square. It stands for the distance from the starting point to that square. Also notice that horizontal and vertical steps have a weight of 10 and diagonal steps have a weight of 14. The colored lines show us also something important. They show us for every square what it’s parent square is. The lines should be ‘read’ from red side to blue side (they’re faded lines). The square at the blue side of the line is the parent of the square at the red side of the line. The current square is always the parent square for the squares it puts on the open list. Next, the program should take the current square from the open-list and put it on the closed-list. After this all has happened the program must go through the open-list looking for the square with the lowest G value. The found square is the new current square and the process that happened to the first square repeats. This is show in figure 3.
Fig. 3 – The next step.
And again the current square is placed on the closed list and the program goes through the open list to find the square with the lowest G value. This process will repeat until the ending point is put on the open-list. At that point the path is calculated (show in figure 4).
Fig. 4 – Done calculating
Now we want to highlight the shortest path. This happens by starting at the ending point and jumping to it’s parent square (from red side to blue side of line), highlight the square and again jump to it’s parent square. This continues until the starting point is reached. At this point we have one of the shortest path from starting to ending point on our screen (shown in figure 5).
Fig. 5 – Shortest path is shown
A summary in the form of pseudo-code is supplied here for a clear picture of what your algorithm should do:
- 1. Put the starting square on the open-list.
- 2. Repeat the following steps:
- a) Find the square with the lowest G value from the open-list, this square is the new current square.
- b) Put the current square on the closed list.
- c) For each of the 8 adjacent squares to the current square the following steps are executed:
- If the square is a wall than we ignore that square.
- If the square is not yet on the open-list it will be put on it. The current square is the parent square for this square. Calculate the G value for this square.
- If the square was already on the open-list than there must be checked of the current path is a shorter path than the square already has. A lower G value means a shorter path. If this is the case than this square should change it’s parent square and it should be given the new G value.
- d) Stop the calculation if:
- the ending point is put on the open-list. (in this case the shortest path has been found)
- The program cannot find the ending point and the open-list is empty. (in this case there is no possible route from start- to endpoint)
- 3. Save the found path in memory. Follow the parent squares from the ending to the starting point. In my implementation just follow the lines from the ‘red’ side to the ‘blue’ side until the starting point is reached. Now you have found one of the shortest paths from starting to ending point.