The A* algorithm explained
For making my A* algorithm i used several resources to help me understand the logic behind it and how the path-finding works, these websites were the most helpful:
However i had to make many of my own additions and adjustments in order for the algorithm to work with what i wanted it to do including a way for it to handle diagonal movement without “clipping” through tiles. I also needed it to work with different sizes of grid for different enemies.
C# LINQ was used for it’s usefulness in manipulating lists and elements in lists, saving me time and meaning i could use less code in my algorithm
A custom class named Node is defined. This contains it’s position, F G and H values and it’s parent node. Secondly a method is created called IndexOf, this will allow me to input the world-coordinates of a tile in the grid and the method will find which index position within the 2D grid array and return it’s index as a vector2.
Next we have method WorldCoordsOf which reverses IndexOf by finding the actual world Vector2 of a position in the 2D grid array. The next 3 methods are for calculating the H, G and F scores of the nodes in the algorithm using Pythagoras as it will be calculating distances between nodes.
calcAdjacentNodes will create a list of the 4 nodes diagonal and vertical to the current node and not return nodes where they are obstacles (0,0).
calcAdjacentNodesDiag does the same as the above one but takes into account the extra 4 diagonal directions in a grid. It also takes into account where there are two obsticles diagonal to eachother so that the enemy cannot move through the perceived gap:
Enemy will try and move this way to path-find.
Code in calcAdjacentNodesDiag makes it ‘see’ an extra obstacle preventing path finding through blocks
Pathfinding Logic Part 1
Pathfinding Logic Part 2
When the enemy uses this method several things need to be done to the output:
The enemy works in ‘steps’ and the path is recalculated every step to account for the player changing position. The path is reversed and has the first entry removed as the first entry is the enemies position and will endlessly path-find to itself. nextLocation is then set to the first entry in the list as this is the next position in the path it has to follow. When it reaches this position the optimalpath is cleared and recalculated to adjust for changes.