Modified A* Pathfinding Algorithm for Grid
Let's say you want to travel from point A to point B and you are given 3 options. Option A is a straight path but with many obstacles, option B is longer but with fewer obstacles, and Option C is the longest path but with no obstacles. How would you determine which path will get you from point A to B in the shortest time? Well, one way is to basically use trial and error and test out all options. But is that a viable strategy? What if there are over a hundred options with many options seemingly identical at first look? You will need a way to tell which path is the best besides using the tedious trial and error method.
Wire Pathfinding
The same dilemma is faced when it comes to wiring between components. Take a look at the schematic below
What will be the best path to join R1 and R2? There are many options here. With the naked eye it is easy to recognize what is the best path to take. However, a program does not “see” like how human see. A program need an algorithm to teach it to choose the best path as per how we humans see it.
Similarly, the need for an algorithm to recognize the best/shortest path is crucial for complex PCB designs. Sizing of the PCB correlates with the cost for its manufacturing. Designers will need to find the least cost wiring path to make them as compact as possible, thus saving cost. Due to the complexity of the PCB board, this is not something achievable by determining using the naked eyes, thus designers will need an algorithm that will help optimize for the shortest and most cost effective wiring.
Throughout the years, many algorithms are conceived for this purpose. In this article, we will focus on one of it: A* algorithm.
Dijkstra’s Algorithm
But before discussing A* algorithm, we have to touch on Dijkstra’s. Formulated and put forth by Edsger W. Dijkstra in 1956, Dijkstra’s algorithm is the basis of the A* algorithm. The concept is to analyze each available intersection point (or node) between the start and the destination with reference to the destination node. It does so with in a uniform pattern radiating outwards from the start node.
At each node, a score is calculated. After each node is “visited” and the score calculated, the least-cost path is formed by backtracking from the destination node through the adjacent intersections with the least score all the way to the start node.
The main disadvantage of this method is the computation time due to the fact that it has to analyze all nodes equally regardless of how unrealistic the node is. In other words, even though there is an obvious least-cost path present, Dijkstra will still continue to calculate the score for all the other nodes before finalizing on the path.
In a grid space, this will be an issue. Take for example the image on the right. Using Dijkstra’s algorithm, connecting from point A to point B would mean that approximately 90–95% of the nodes (green crosses) in the grid space would have to be covered before it can determine the least-cost path.
A* Algorithm
Whereas in A* algorithm, the main disadvantage of Dijkstra is addressed. Instead of covering the entire grid to determine the least-cost path, A* algorithm introduces a heuristic to help give the algorithm a “sense of direction” on the potential nodes to the shortest path. This means that nodes that deviates away from the destination are given low priority in favor of the nodes that is closer to the destination.
The formula for A* algorithm is given as:
f(n) = g(n) + h(n)
f(n) : The final score given to a node, the lower the better
g(n) : The cost needed to travel from the origin node to the node, the lower the better
h(n) : The heuristic score indicating its potential as a viable path node, the lower the better
With the formula, the summarized steps of the A* algorithm is given as below:
Step 1: Calculate f(n) of nodes adjacent to start node. (start node has a score of 0)
Step 2: Add calculated nodes to an “open” list
Step 3: Choose a node with the least score, f(n), from “open” list. If the node is the destination. Go to step 6
Step 4: Calculate f(n) of nodes adjacent to the selected node. Move selected node to “close” list.
Step 5: Repeat step 2–4
Step 6: Back trace from the destination to the start node for the least cost path
Every node needs to take note of its “parent”, which is the least cost node pointing into it. This helps the back tracing for the least cost path.
It is also worth to note that some nodes may be visited multiple times (a node can be adjacent to multiple nodes). When it happens, the f(n) score is checked and the score is updated with the lowest one calculated. With that, its “parent” will also be updated.
Modified A* Algorithm for Grid
In a grid space, some parameters are easy to determine. Often times, a grid has a uniform distance between nodes, which means g(n), the cost from node to node can be easily determined. h(n) can then be found by taking the hypotenuse from the Pythagoras theorem as the displacement from the end node to the node. This is a proper assumption because in a uniform grid space, the nodes would form right-angled squares where the catheti of the right-angled triangle can be easily determined. The image below will give a visual explanation of the reasoning.
- a node
- 2) distance between nodes, g(n)
- 3) hypothenus displacement between end node and node
However, there is a catch. Often times in a grid, the diagonal adjacent nodes are not considered. By using the Pythagoras’ theorem as the heuristic, the resultant shortest path (which is suppose to be a diagonal line) would instead become an awkward looking “ladder step” line.
To address this, the A* algorithm would need to be modified. Because the least-cost path is ultimately determined by the score, f(n), by inflating its score when a bend happens, the algorithm can be “tricked” into thinking that the node is ofless potential as the shortest path.
To do this, the formula can be modified to
The penalty is added whenever a bend is detected. This means that ideally speaking, a wire that go in a straight line will always be prioritized, and the bend will only happens when absolutely necessary (which is when the f(n) of the straight line far out-weight the cost of the bend).
Now we will be able to get a wire connection that is simple and clean.
Conclusion
As an algorithm that is smart and dynamic, A* is surprisingly easy to comprehend. Aside from the application here in determining wire pathing in software (and PCB), A* can be potentially used in applications such as traffic navigation software and maze running robots. Of course, there are many more algorithms that may outperform A* in its effectiveness and performance. However, for many cases, A* potential is sufficient to fulfill the requirement and easy enough to be implemented in many cases.
So why not you give it a try and learn up this algorithm today?
Reference
Below are two videos that explains A* algorithm very well.
Originally published at http://filpal.wordpress.com on January 10, 2021.
