Back to Basics — Divine Algorithms Vol III: A* Algorithm
You are here!
HA! I see you… found your way to my blog *BA DUM TS*. Okay, in hindsight, this joke is not going to make sense until I actually explain today’s blog topic. But, if you were successful enough to find the hint in my previous blog, you might have an idea of what I am talking about and the joke was probably… not lost on you *BA DU… ok sorry, last pun, promise. If you did not read my last blog, which you should it’s amazing, or you did not find the hint, this was it:
After all, you don’t want to be stuck in a maze.
So, without further ado, welcome back to Back to Basics — Divine Algorithms, where we talk about the A* Algorithm.
The A* Search Algorithm is one of the best and most used algorithms for implementing path-finding and graph traversals. Today, we are going to be focusing on the algorithm’s usage for path-finding. Now, buckle up, and let’s talk A*!
A* Student? A* Master!
So, what is the A* Algorithm? Unlike the previous blogs, where the algorithms were finding the shortest path in a tree, a rather abstract concept when it comes to real-life applications, this algorithm finds the shortest path in real-life situations. An example of a real-life situation might be a 2D grid map for example. A proper way of trying to explain how this algorithm works is by showing an example:
We can already see one key difference here between performing other algorithms on a tree and performing the A* on a 2D map grid. We can see here that not every path is available. We have blocked paths that the algorithm cannot traverse. This makes this algorithm’s use cases less abstract and more real-life oriented, as mentioned above. Think of a road that’s a part of a map. Roads are often blocked because of repairs, they are blocked because they are closed, or they are blocked because of traffic even. This is where the A* really shines.
Not only is the A* able to find these blockages, but the A* is also programmed to take the optimal path. If we look at the example above we have an idea of the decision making that the algorithm performs. Instead of taking the route [4,2] → [4,3] → [3,3], the algorithm took the route of [4,2] → [3,3], eliminating one extra step. The optimal decision making and the blockage detection is why the A* is the most popular and most used algorithm in regards to path-finding
Ace the A*
Terminology
Just like any of the other data structures or algorithms, there is some base terminology that is needed in order to fully understand how to use it. There are three letters that you have to remember to cover all the terminology for the A* algorithm:
- F: Total cost to reach one node in the graph. That is calculated by doing G+H. But, what is G, and what is H?
- G: The distance between the current node that the algorithm is currently visiting and the start node that the algorithm started on
- H: The heuristic. What that means is the estimated distance between the current node that the algorithm is currently visiting and the end node. This can be calculated in ways such as the Pythagorean Theorem
Bear in mind, these are not my naming conventions, meaning that, I didn’t just choose random letters. These are the actual names of the variables as agreed on by the computer science community. Now, these letters seem irrelevant now, however, they are pivotal when we go through the steps of the algorithm. Here are the steps of the algorithm explained using the above-mentioned letters:
- Initialize your lists: The first thing we need to do is initialize two lists. A list of open nodes, and a list of closed nodes. The open node list is going to contain all the nodes that are unvisited and viable nodes. The closed node list is going to contain the visited or unviable nodes.
- Start node: Add the start node of the maze in the open list
- Now, time to repeat some steps!
- 1- Lowest F: We explained earlier what the F value is. After calculating the F value for the nodes in the open list, we try and look for the lowest F. Once we have it, we move it to the closed/visited nodes list. Let’s call this the current square!
- 2- For each adjacent square surrounding the current square (8 in total) we do steps A-C
- A- If it is a blocked node or it’s on the closed list, we skip that specific square. If not, we proceed with step B
- B- If it has not yet been recognized as a part of the open list we add it there, we also recognize it as the parent node to the current node we are on. We also record the F, G, H. As a rule of thumb, you always record these values. They are also known as scores
- C- If the current square is on the open list, you check for the F score. If the F score is lower then we use that new current path and we update the parent node. The current path is updated by backtracking from the parent node to the start node
- Stop!: These are the steps you keep doing until you either:
- 1- Find the target node, usually indicated by someone adding the target node to the list of closed nodes
- 2- There was no successful attempt at finding the target node, which is usually indicated by the list being of open nodes being empty and never hitting the target node.
Looking at this, it might seem like it’s a daunting algorithm. However, the code implementation I am about to provide in the next section will definitely be useful to grasp it more. If that is not enough, here is an animation of the A* algorithm to help ease the wait until you see the code!
🎶 Teach me how to code it, teach me, teach me how to code it 🎶
I have been getting into the habit of including the code implementation for the topics of the blogs that I write as I did with the RB Search Trees and Bellman-Ford algorithm. People have found this to be very helpful! It’s always beneficial to solidify the theoretical knowledge with some code. Especially that, surprisingly enough, it is not really that hard to program the A* algorithm. One more point for A*!
Instead of including a code implementation from a computer science website, as I did with my previous blogs, this time I have a little surprise. My colleague at Capgemini, Daniel Oliemans, has actually worked on an implementation for the A* algorithm for a side project he is working on. I asked him if I can use his, VERY well-made implementation, and he was quite open to the idea! So, without further ado, here is Mr. Oliemans’ implementation of the A* algorithm using Java
Having said that, for the sake of trying to include as many people as possible, Daniel selflessly guided me to a website that has implementations, other than his own, of the A* using Python and C++, just in case someone prefers these languages over Java.
Use Cases
Like we said before, this is a shortest path algorithm, so the use cases that were mentioned in my Dijkstra blog are also applicable here. But there is one use case that prefers using A* over other algorithms and that is the shortest path-finding in games. The reason people use this in games is that A* is quite fast and also accounts for blocked passages that the player cannot take in a game. So, whenever you see an “AI” enemy that is, for example, hunting you down, the path it is taking to follow you is probably using A* algorithm!
Now What?
Now, you can actually explore something really interesting concerning algorithms in general but is quite fascinating for the A* algorithm. What I want you to explore are two things called:
- Proof of completeness
- Proof of Optimality
These two things take a theoretical concept such as an algorithm and extrapolate it and karate chops it into another theoretical realm! I will not dive into what both these terms mean, but who knows what the future holds? They are, nevertheless, very interesting topics that will help strengthen your theoretical knowledge!
I hope you enjoyed this article! It took the longest time to write compared to all my previous ones. You should also check out all the other code projects by Daniel Oliemans and check out for his near future projects, he has a lot of things cooking! That’s all for now and I will see you on the next blog of Back to Basics!
Resources
To freshen up on my knowledge of the A* algorithm, I had to do some research. Below, you will find all the resources I used to write this blog for you!
