A* Pathfinding

Exploring A* pathfinding in Unity, as well as integrating it to both a 2D action adventure, and a top-down RTS.


A* Image

THEORY


Through my last years dissertations for both the 2D platformer and the top-down RTS, I found interest and delved deep within A* pathfinding methadologies through Unity. This journey involved understanding the core principles, utilising it within a simple top-down space, and then adding limitations and restrictions to have it work in a 2D plane. Whereas other systems such as Unitys navmesh would have functioned to complete a similar task, custom A* pathfinding opened the choice and free-manoeuvrability to both the player, and the AI, to replicate realistic behaviour and movement, a vital factor when attempting to nourish the players magic circle within these realistic genres.


A* Image


So, to briefly explain, A* pathfinding works by first drawing a grid filled with 1x1 nodes. Placing down two positions, the target, and goal, and then trying to locate the shortest path between the two by calculating the vertical and horizontal movement. In this diagram, we're trying to calculate the distance from both green squares starting with a G cost - how far that currently selected node is from the start, and then adding it to the H cost - how far that selected node is from the end node, resulting in the accumulative F cost.


A* Image


As the algorithm runs and loops through each value, it can then find the next place to move, and so on, calculating the most efficient path with obstacles and other units directly affecting the grids values in real time as they also move around, re-drawing and re-mapping certain parts of the grid.


IMPLEMENTATION

To implement this theory into Unity, we start by first creating two Layers (this can be expanded once comfortable with the A* methodology), a walkable terrain, and an un-walkable terrain. This is followed by setting a size for the grid, generally revolving around how big the world is. We then loop through each node inside the grid, detecting what Layer each node is currently being hit by shooting a raycast, before then determining whether it's walkable or not, adding a movement penalty, before moving onto the next node on the grid. This will later be accessed by our units when determining their path movement.


A* Image


Starting the actual algorithm by entering the start position and target position, we then evaluate the two different types of nodes, the open nodes which need to be evaluated, and the closed nodes which have already been evaluated. An easy way to cheat this is by creating a list and adding the open nodes to that list after they've been evaluated. Upon becoming more familiar and moving forward to optimise the code, you can then create classes that hold these values to prevent repetitive looping. Once added we can enter a loop and start calculating the most efficient path by moving between each node. This is where G cost and H cost come in, calculating the values of each node, determining whether its F cost is currently lower than the adjacent nodes before then adding it to the closed list and so on, determining which path is the most efficient.


A* Image


The unit accessing this A* pathfinding script can then loop through each closed node, either moving towards it by simply adding velocity and changing direction to look at the upcoming node, erasing them one by one as it loops through, to more efficient coding where it can create independent lists, removing certain points that seemingly have no change in direction, and moving through them that way.


2D PLATFORMER

This is, overall, a relatively basic way to cover A* pathfinding, but it allows for more efficient broader adaptations to then be taken and utilised. Using this methadology you can create a new iteration for a more complicated flat 2D plane, simply adding restrictions in how it calculates its path by creating new invisible costs such as jump height, gravity and even weight.


A* Image


Both of these instances were created for two seperate projects I worked on through the year, and I found it enjoyable to explore this methadology to such a degree, adapting it in numerous ways whilst also understanding its core principles. To experience this methadology in practise, play Abtohka: Kingdoms of Despair.

Lastly, I truly believe A* pathfinding, as well as most custom created controllers, are incredibly easy to adapt once one has a decent conceptual understanding of its functionality, allowing it to not only overtake most modern game engine adaptations but also offer a level of freedom and customisation of AI that is a must in most games and genres.




Go Back