A Star Pathfinding
A* is a widely used pathfinding algorithm. It calculates a path from a starting node to an ending node based on movement costs associated with each node as the path is created. Once the path is created then an AI can move along that path, always knowing during runtime the most efficient path to its target.
Let's start with the Grid Class.
On Start() we set up basic variables such as node diameter which is the node radius * 2. Then the size of each grid square is equal to the grid's world size x and y, divided by the diameter of the node. This is so we know how many nodes can fit into our grid.
Now, the grid needs to be created. We have a variable called grid which is an array of nodes and will hold however many nodes on the x and y axis that we specified for gridSizeX and gridSizeY to be. The nodes will be filled in from the bottom left as each of the x,y coordinates in the grid is looped over and evaluated. As we loop, worldPoint keeps track of which square in the grid we are at. We can use a Physics.checkSphere at that point to check if an object is on the un-walkable layer, meaning that node will not be part of the generated path. Once that information is found then a function creates the node with the parameters that were passed in.
The node class itself is not shown but is straight forward. It has those four parameters: the walkable boolean, a vector 3 world point, and its x,y vector 2 grid coordinates. Plus it has f, g, and h costs, and also a spot for a parent node. To eventually find the correct path, we loop through the parents recursively (imagine chain links).
A node will need to know what other nodes are around it and the best place for that logic is the grid class. The GetNeighbors function will take in a node and create a list of its neighbors. Then the for loops are going to create a 3x3 grid to check around the node. We add those to the nodes grid location and that gives us spots to check. If that check does not go off the game world, meaning the the node is in the game world, then each of those nodes are added to the list. Later, this will be used to evaluate the cost of the neighboring nodes to decide where to move next.
We are also going to need to be able to find a node from a world point, in case we want to keep track of enemies, players, objective, etc. We need to convert our location to grid coordinates. Then convert those into the node coordinates so the position is centered in the node on the corresponding grid square.
For example, if the player in Unity is at 0,0,0 then the player's world point is Vector 3 (0,0,0). The grid is also created from a game object at 0,0,0 but is 10 x 10. This means its bottom left point in relation to its position when it was created, is -5,0,-5. It subtracts the positions of the player and the grid and you have a player at 5,5, the center of the grid because 0 - (-5) is 5. If our node radius is 1 (huge node size for a 10x10 but easy for the examples sake) then the node diameter is 2. Our x,y position (5,5) of the player divided by our diameter (2) gives is 2.5 minus the nodes radius (1) to center our point. It is now at 1.5 so we need to round it to 2 meaning we are at point 2,2 on our node grid, since the point can not be halfway between nodes. Our grid starts at 0 so take 3 steps right and up to get to the center (2,2). Then, weclamp it to make sure the values stay within the grid when they are returned even if our player were to somehow leave the world then we would not get errors.
We know how to get nodes from our grid so to find the path we grab the node at the start and end point. The open and closed lists are used to keep track of what nodes we search when finding a path. Neighbors will be put in the open set and when a current node is found we change whatever neighbor had a lower F cost to our current node then find all of its neighbors. This step needs to be repeated until the target node is found.
To calculate which node to move to, we find the F cost which is the G cost plus H cost values. If the newMovementCost is less than the F cost, the current nodes values become the neighbor values. H cost is equal to the distance from the neighbor node to end node. G cost is from the start node to the current node.
To calculate H or any distance, we use the GetDistance() function. A diagonal move cost 14 while a straight moves cost 10. When finding the point from where we are, we count up and over for the vertical and horizontal axis (x,y). The lowest move along an axis to be in line with the end point is how many diagonal moves it will cost. For example, if it took 5 moves we subtract 5 from however many are left on the other axis to get how many more moves to reach the end.
Retrace Path allows us to find the path to hand over to the AI so it can move. We have a variable on our node class that is a parent. Each time we find a new current node, we set the parent to the node before it creating this chain of nodes leading us from the start to the end. At the end, we need to reverse the path so we hand it back in the correct order.
To visualize it all, we loop through all of the nodes in our grid and check them against variables like the player, end goal, etc then we change the color of that node.
