Pathfinding Algorithms & Implementations In Unity
It is pretty surprising that the A* algorithm, the one being used in Unity’s NavMesh system for pathfinding, was actually found at 1968. In this article, I will try to explain the basics of some of the widely known algorithms and try to demonstrate them using Unity. You can access the github repository by following this link.
Intro
If you carry out a quick research, you will find out many resources explaining the concept using Graphs Theory. Despite computer science is relatively young, graphs have been being used for visualizing relationship in between multiple objects in different fields for quite some time. That’s why, it is not quite surprising that finding the shortest route has been a great struggle for a long time, and still today with the boom in the AI field.
Briefly, the theory defines the smallest moveable unit as a “Node” or “Vertex”. Each connection between two nodes are called “Edge”. The edges can have values (denoting the movement cost), or directions. For the sake of this article, I will not be digging into the Graphs.
In order to visualize the algorithms in Unity, a board that consisted of a unit sized object are generally used. I preferred square, but you can go with whatever shape you want as long as you consider the distances in between two neighbour nodes.
Please note that in the repository of the example below, I have used “Cell” keyword rather than “Node”. They simply denote the same thing, visualized by a single square.
Certainly, the cost of movement from A to B might be a function of many things (time, distance, etc.), but for the sake of the example, the associated cost of moving from one node to another is only subject to the distance. The costs considered are always greater than zero.
Visualization & Implementation
The associated costs of unit movement from the center node to the each of the neighbour nodes are provided below:
In my Unity representation below, the Nodes are colored as below:
Green: The start Node
Red: The goal Node
Gray : Visited Node
Blue: Node on Path.
*If you are to download the project from the repository, you can manipulate the Map properties from the Board Game Object via MapView.cs. If you increase the blockage ratio, you will notice that in some cases the algorithms will not come up with a solution.
Breadth’s First Search Algorithm
As the name suggests, this is more likely a search algorithm rather than a pathfinding one. Beginning from the start point, the algorithm expands one degree of depth on each run, checking the neighbour points if the target point is reached. The neighbours are added to a queue, meaning that before moving onto the next degree of depth, all of the neighbours at the first degree will be searched. The algorithm continues to run until the target point is reached or there are no points left to be checked.
As you can guess, this is relatively a costly algorithm as it will be keep searching on all available directions — without considering if it is moving further away from the target. Despite the fact that it will always find a solution if any available, Breadth’s First Search Algorithm does not guarantee that it will find the best path in between two nodes. As you can notice below, it came up with a solution which is far away from the optimal one.
In the example above, the generated path is dependant on the neighbour sorting in the Directions.cs. In my case, each cell starts to gather its neighbours starting from the upper side, following the clockwise direction. The path is subject to the order of the Direction.cs. If you shuffle the values within the Directions.cs, you will gather a completely different solution using the same algorithm. If you want to discard the diagonal ones, you can simply take out them, making the algorithms only moving horizontal and vertical.
Dijkstra’s Algorithm
Dijkstra’s algorithm was built over the Breadth’s First Search Algorithm to find the shortest path, if available. As the predecessor Breadth’s algorithm does not consider any distance or cost of movement at a particular node, Dijkstra tries to find the optimal route by measuring the cost of moving to a particular node from the start point. If a particular node has a neighbour with a lower cost of moving than it’s associated parent node, it’s parent will be changed in the way of decreasing it’s associated cost.
The regarding cost can be calculated by considering the distance and the cost of using a particular edge (such as moving through a muddy road rather than a normal one).
In the example below, you can observe that the Dijkstra’s Algorithm has resulted with the shortest path, whereas Breadth’s First search came up with a much longer path.
Still, you can realize that both of the algorithm’s searched equal amount of nodes, which is actually far away from being an efficient method. For this particular reason, more efficient ways were required to reduce the computational cost of exploring unnecessary cells.
Greedy Search Algorithm
As the name of it suggests, this algorithm tries to reach to the destination by computing the heuristic cost of moving to the end point. It is called heuristic as at the time of the calculation, the node does not know if there are some blocks or additional costs associated on the calculated path.
The H cost will always denote the cheapest way from the particular node to the end point, regardless of the status of the nodes along the path. In other words, it simply says, “Hey! I want to go there, give me the lowest distance node on each step”. Rather than keeping track of every neighbour of a discovered node, the algorithm expands by comparing the heuristic costs of explored nodes. As the H cost is irrelevant from the start point, it will be constant for a given end point, regardless from the parent node.
Unlike the previous algorithms, only the neighbours of the moved node will be discovered and compared with the explored nodes; according to their heuristic values.
This algorithm does not ensure that the found path is the optimal(shortest) one. As I have stated, given the fact that it does not take into account the occurred cost of moving, only considering the heuristic cost of moving to end point, the path may be resulted with unnecessary movements. You can notice that this algorithm was able to reach to the destination much faster than the previous ones, almost 1/4th on my case.
A* Algorithm
And it was 1968 when Peter Hart, Nils Nilsson and Bertram Raphael came up with the brilliant A* algorithm. The algorithm was developed to overcome the unnecessary movements of the Dijkstra’s algorithm by taking the heuristic costs into account. The step by step movement of the algorithm is just like the Greedy Algorithm, rather, it also consider’s the occurred cost upto that point.
So you get it, the A* algorithm uses both the distance from the start and the heuristic distance to the goal point. The total(final) cost of each node is denoted by “F”, whereas the occurred cost of moving from the start point is denoted by “G” and the Heuristic cost of movement to the end point is
F = G+H.
So, in a case in which a node has a G cost of 14, and H cost of 20, it means the associated total cost of the node will be 34.
G: Distance from the Start
H: Heuristic Distance to the End
On each stage, the algorithm will search for the node with the lowest final cost as its next destination, until the end point. As you can guess, the more we get closer to the end node, the lower the H costs and higher the G costs. In the case that two or more nodes have the same F value, the algorithm will prioritize the node with the lower H value as its next node to check.
As this algorithm only searches for the neighbourhood of a particular node, the neighbour of the discovered node might(well, at the early stages, will) have undiscovered nodes with a lower G value. This will require us to update the G cost of these nodes once they are discovered, just like the Dijkstra’s algorithm.
Despite it includes more calculations according to the other algorithms, the A* algorithm results with the perfect solution, it will come up with the shortest path, if a path is available.
Time Comparison
You can find the completion time for each of the algorithms on two different cases below:
Despite the fact that these time are subject to the neighbour ordering and the map, it is evident that the last two algorithms were able to come up with significantly lower amount of time and of course, only the A* providing the indisputable optimal solution.
As AI and MR becomes more and more adapted into our lives, the importance of pathfinding algorithms are likely to hold their significance for some amount of time, being a significant element for the spatial computing.
