Artificial Intelligence for Games 101 – Dijkstra’s Algorithm & A* Algorithm

Previous Post: Introduction to Artificial Intelligence

Edsger W. Dijkstra created the algorithm in 20 minutes when out shopping with his Fiance. The main objective of this Algorithm is to calculate the shortest path from one point to another. This is practical in a lot of different sections for Artificial Intelligence including Games and Satellite Technology. Surprisingly, Facebook uses such an Algorithm to recommend Friends – finding the “shortest path” between people, aka ‘Six Degrees of Separation’.

How to use Dijkstra

Dijkstra’s Algorithm initially notes every non-visited point at a distance of infinity, as the algorithm is currently unaware of the distance. After all are labelled, you can select the starting point and give it a Distance of “0” as we are currently there. These points are all put inside a Queue / Array of “Incomplete Points”.

The next step is to go through each neighbouring point to the “current” point and label their distances. Each of these points will now have a “distance” and a “total distance”, with the total distance being the previous point + next point. In the case of the first point, it’s distance is 0 anyway, so it would be whatever the next distance is + 0.

Once the algorithm has scanned all neighbouring points, it selects the shortest distance as the current point, and puts the previous point as it’s “Parent” point while moving the previous point into a new “Completed” Queue so it can’t go back through it. Then it follows the same technique, checking every neighbouring point (except the previous one) to find the shortest.

After it has gone through this next point, it will backtrack and go to the next neighbour of the previous point, following the same method as before. Eventually once all neighbouring points have been checked and labelled correctly, it goes to the current shortest point depending on each of the “distances” and repeats same as before.

This goes on until eventually the Algorithm reaches the final destination. Once done, it runs through each parent starting at the End Point and working it’s way backwards, thus giving the final result – A complete path!

A Star Algorithm

A Star Algorithm is a variation of Dijkstra’s Algorithm, but this time it uses a Heuristic function to find the shortest path and also calculates the distance from each point to the final point – preventing it from possibly backtracking as much as Dijkstra’s sometimes can. As an example, with Dijkstra’s algorithm in Motorways, there may be a small amount of traffic down one junction so it could recommend going all the way in the opposite direction before figuring out to go the correct way. Whereas A Star recognises this adds on extra unnecessary time. This makes A Star faster in some aspects, though choosing between either Algorithm is dependant on the users needs.

The Heuristic Function and Distance To Target can make A Star quite effective in that it doesn’t need to check every single point once it knows what the shortest path currently is, cutting run time potentially massively depending on how big of a graph it needs to check.

The Pseudocode for A Star isn’t much different from Dijkstra’s, except for an added “Distance to Target” variable for each point.

What to Read Next

AI Algorithms: Flow Fields
Finite State Machines
Navigation Meshes