Pathfinding
My interests in path-finding algorithms starts from an FPS game I have been working on, where the alien bots would chase the player and attack when in closed range. For this purpose, Unity has already provided an excellent tool called the NavAgent, Unity’s navigation system implemented using A* searching, and this feature did solve my need at that time. Nonetheless, I became obsessed at not merely implementing such feature through Unity, but being able to peep into the black box and learn it, which would be useful in many real-life challenges such as building logistic robotic system. Through few weeks of researching, I was able to code up four major pathfinding algorithms including the industrial A* searching, and visually implemented them with some self-drawn mazes in Unity.
Github Link: https://github.com/lei-go/Pathfinding
Breadth First Search
Breadth First Search (BFS) is one of the most fundamental and easiest implemented algorithms in graph searching. The idea has it that, in each virtual iteration, each frontier node would search through all of its neighboring nodes that have not been explored, and assigned itself to be the previous node of frontier nodes. Thus, when the algorithm reaches the end goal node, it can then connect each previous node in the queue, one by one backward from the goal node to the starting node, and thus make a path.
In an open space, each nodes on the frontier would explore all its neighboring nodes in eight directions. The so-called “breadth-first” refers exactly to this idea of exploring each current “breadth” first, i.e., all current frontier neighbors, before entering the next iteration.
The pixel maze was generated via an online tool mazegenerator.net in which the black blocks represent the wall and white for open space. This maze would be built in Unity at runtime using tiles assets via two scripts, and both the assets and scripts can be found using my Github link above. Below animation illustrate how BFS performs in a confined maze.
While BFS seems to get its work done in finding its path to the end node (in red), however, it must be noted that this maze is of very mini-scale with only one way to the end node. In reality, while being easy to implement, BFS is not an efficient algorithm. Below is another example running BFS but on a slightly larger scale, open-space map.
In this open map, not only is BFS seems slow and not-so-intelligent, as it must iterate through every single node before reaching the end node (Imagine an open world game with millions of nodes!!), but that the final path is not optimal neither. While BFS did give us one result, we would need some improvements on both the aspects of accuracy and speed.
Evolution: Dijkstra & Greedy
The solution is indeed very simple. Instead of blindly iterating every single neighboring nodes at each frontier nodes, one can add a priority queue to the BFS so that the process of exploring nodes is more selective. Depending on the priority criteria, two algorithms were later developed - the Dijkstra’s, which emphasizes on accuracy and guarantees the shortest path, and the Greedy Search, which emphasizes on the finding speed.
Dijkstra’s Algorithm
In the Dijkstra’s algorithm, before each node is about to be explored, the algorithm would compute its distance to the origin by adding its distance to the previous node to the accumulated distance stored in that previous node, from all the previous nodes coming before it through this manner, all the way till the starting point. The ones in the frontier nodes that have the smallest accumulated distance would be prioritized in searching. In simple words, the Dijkstra’s algorithm calculates the accumulated distance of every nodes from the origin, and would always search the closest ones first. This guarantees that when the algorithm traces backward after reaching the end node, it would always output the shortest distance, since every previous node in the path is linked through this “shortest accumulated distance” at run time, and so the sum of them must be the shortest.
One can also induce that, per the idea of prioritizing the closest-to-origin nodes first, its searching routine would be more of a circular shape than grid scanning of BFS, since Dijkstra “radiate” from the origin and so the radius are the shortest per say. Below are its running example on the same map, and the output is indeed the shortest possible path.
Greedy Search
Opposite to Dijkstra, Greedy Search prioritize the frontier nodes not by their distance from the origin, but distance to end node. For people who took CS, this straightforward approach indeed follows the Greedy Algorithms Principle - find a safe move, and repeat it till the end. In this case, since our goal is to find the end goal, then the safe move would naturally be prioritizing the ones that are the closest to the goal. Thus, it would not be a surprise to see that the algorithm goes in a straight, even like an “explosive” way.
The pros and cons of Greedy are obvious as well. Greedy is extremely fast. It is fast, fast, ridiculously fast, which is favored by some even over the A*. Of course, the cons would be accuracy, as the ridiculous long path show in the animation. In addition, some people would argue that, unlike the BFS or the Dijkstra, Greedy need to somehow “know” the position, or at least the direction of the end node, which is some form of “cheating” to some perspective… BUT, since these algorithms are embedded in games or some back ends, the system would have already known the position of all the nodes. It just need to find a way to link them all together. Moreover, even in reality, such as a setting of logistic robots in a factory storage, it is common to grasp the location of an object. So it’s not cheating…
Some Thoughts
We have seen Dijkstra and Greedy, with one emphasizing the accuracy and one for the speed. Each of these algorithm have their irreplaceable advantages, and yet also serious flaws that made them not so satisfying. A natural thought after seeing these two algorithms, of course, would be whether one could combine both, to make a algorithm that is both reasonably accurate and fast in implementing. This the starting point of the creation of A*, the nowadays industrial standard which is also used in the Unity Engine.
A* Search
A* Search basically prioritizes its frontier nodes based on the sum of a few parameters.
The simplest form is just the addition of two factors, h_score and g_score, where h_score is the distance from origin used in Dijkstra and g_score being the distance to goal used in Greedy. The nodes with the lowest of this hybrids would be expanded and assigned first.
An example of A* running on the same L-Wall map is shown below.
Bonus
It is not easy to see that A* is faster than the Dijkstra as it did not waste time in searching through every unnecessary nodes, and much more accurate than the Greedy. Below is another example of A* looking for a node hidden in a narrow valley, which could be a tricky challenge to traditional pathfinding algorithms. A* was able to complete it with reasonable runtime and accuracy.
In addition, since A* is basically a hybrid of different prioritized parameters, it could be easily tuned to fit in different situation for different goals, depending one prefer more on accuracy or speed. As a bonus, for example, one can add in a parameter penalty for terrain nodes in a terrain map, in which cost on the grass nodes are added an extra penalty of 1 (marked in green), muddy nodes with penalty of 2 (marked in yellow), and mountain of 3 (marked in brown). Again, A* is able to find the most suitable route based on its hybrid prioritization.
