A-Star Pathfinding
Individual unit requests
First of all, we need to tie the existing pathfinding algorithm to each unit so the player can move them individually. I've written this code in the unit manager class so that when the player right clicks, all highlighted/selected units are queued for pathfinding.
This runs the "startPath" function in each object's basic unit class. This function queues the unit for pathfinding with the unit's current position. When pathfinding is complete, the path manager class then runs the callback function, which in this case is "onPathFound".
The "onPathFound" function stops any current movement coroutines and starts a new movement coroutine if the pathfinding algorithm was successful. The movement coroutine moves the ai in the direction of the next waypoint until is has reached proximity with it, then continues to the next waypoints in the list. The velocity is normalised because otherwise, the ai would have a greater velocity for further waypoints.
Path request manager
The path request manager queues each unit one by one so that multiple states of the algorithm aren't running at once, reducing performance. It does this by creating a "struct" (as of Microsoft's documentation, a struct is a value type that encapsulates groups of related variables)1. The struct stores the start, end and callback variables. When a path is requested, a new struct is created with the unit's pathfinding information. It then queues this request and attempts to process the next request in the queue (if the queue's size is greater than zero and it is not currently processing, then it starts the process). Also, once a current process has finished, it also tries to process the next request and activates the callback with the success boolean and found path.
Turning the algorithm into a more efficient and accurate a-star algorithm
In order to transform the algorithm into an a-star algorithm, new variables must be added to the nodes. The gcost is the total cost of movement from the star node to the next node. The hcost is the total cost of movement from the next node to the end node. The fcost is the total cost of the node (gcost + hcost). The algorithm now checks whether the new gcost of the node is less than the current gcost or whether the open list does not contain the new node (If the node hasn't been checked already). It then applies the gcost and hcost of the new node so they can be read later. The next node is now the parent of the current node (This is stored in a new variable within the node class) and is added to the open list.
Once the pathfinding process has finished, it tells the path request manager after retracing the path, passing the waypoints. To retrace the path, the function simply gets the end node and finds its parent and so on. It then reverses the path so that the unit can follow it.
