Pathfinding

Pathfinding is an algorithm AI uses to find the closest distance to a target. So in our case, a game, pathfinding is made to allow the AI to find the closest distance to the player. Some of you might ask, why would we need such an algorithm if we can write a few lines of code to chase the player. If we didn't have a pathfinder, the AI will not be able to chase the player, if there was an obstacle in the way. For example, if the player and the enemy was at opposite sides of a table, the enemy will not be able to chase the player, as there is something blocking its way.

How does it work? 

When making a pathfinding manager, you should make a singleton for it. For those who don't know what a singleton is, a singleton is a way of making sure that there are no duplicates of a script. For instance, there should only be ONE GameManager script throughout the whole game. A singleton is made to ensure that this is true. However, for a pathfinging manager, we don't want to destroy the manager as soon as we load into a new scene, we want to keep the manager and the algorithm itself so we can use it for multiple levels, when needed. Once the singleton is done, there are 3 problems you should take care of:

1 - Building the Graph - The graph consists of the nodes (or waypoints) positions and the distances between each and every one of them. The graph also contains information of which nodes are connected to each other, and which ones aren't. The graph (for visual aid) is like the multiplication table. But in this case, instead of putting the total, you put in the distances and -1 for any nodes which aren't connected.

2 - Making the algorithm - The algorithm I used is the Dijkstra algorithm, where it will keep track of the accumulated shortest distance, if the node has been visited or not, from which node did it arrive from and a queue list which will check each node it arrives. This algorithm will go through each node, between the enemy and the player's position. It will then check which nodes have the closest distance to the player. 

3 - Backtracking - Once the closest distance has been calculated, the algorithm will now need to backtrack, from the player, to the enemy. Once the backtracking process is complete, the AI will then start to follow the points, given by the data/information given by the algorithm itself.