A* ALGORITHM
A* is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.
ALGORITHM EXPLANATION
Lets create a grid and choose a random grid points, and mark those points as A(GREEN) and B(RED). And the middle black grids are obstacles. The computer needs to find the shortest path between these two nodes from A to B.
For that we need to help the computer to understand the logic behind the path finding between these two points.
We need to get the nodes near the A point and assign values for the
Multiply by 10 and assign those values to the nodes.
Now, we need to understand the 3 terms or values needed to find the shortest path between the points.
Gcost - Distance from the starting node.
Hcost - Distance from the End node.
Fcost - Gcost + Hcost
Let, me explain in detail how the algorithm works without the obstacles, the path will be obviously a straight line.
In the about diagram u can get a clear view of the point A and the Side and Diagonal points around the point A. But, you can see many numbers around the point A. Do you have any guess?? The points are Gcost Hcost Fcost
In the above diagram,we need to choose the lowest Fcost in the each cell ,you can find that the Cell no.1 has the minimum F cost 42. Then go the cell which has the lowest Fcost and generate the distance between that node to the End node. The process continues until the new node meets the existing node.
The below image shows how the caluclation occurs between the nodes, and finds a way to the point.
As you can see the Gcost increses as we go closer to the node B. and the Fcost descreses.
Node Grid
Now, we are going to
Create a class Node, which has 2 reference variable as Bool
and Vector 2 as walakable and world position.
Create a struct and assign walkable and world position.
public class Node
{
public bool walkable;
public Vector3 worldPosition;
public Node (bool _walkable, Vector3 _worldpos)
{
walkable = _walkable;
worldPosition = _worldpos;
}
}
Then create a new class Grid, attach it to a GameObject.Assign Layer mask to unwalkable paths.
public LayerMask unwalkablemask;
public Vector2 gridWorldSize;
Node[,] grid;
public float noderadius;
We create a OnDrawGizmos() function to Display a grid.
Assign a values for the grid to fit the Plane. The result will seem to be same.
Now we need to calculate how many Nodes can be shown inside the Grid we created.
We, need to calculate by Dividing total volume of the Grid size by NodeRadius*2(Diameter)
