A* Pathfinding in Unity

Programming, Technical and System Design · 10 minutes Read

Exploring A* pathfinding in Unity, before adapting it to work with both 2D and 3D games and projects.

To use and create interesting AI with this idealogy, make sure to read my Designing AI post.

Through my last year's dissertations for both the 2D platformer and the top-down RTS, I found interest and delved deep within A* pathfinding methodologies 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 Unity's navmesh would have functioned to complete a similar task, custom A* pathfinding opened the choice and free-manoeuvrability for 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.

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.

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 values of the grid in real-time as they also move around, re-drawing and re-mapping certain parts of the grid.

Part 1: 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 ray cast, 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.

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.

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.

Part 2: 2D Implementation

This is, overall, a very quick way to cover A* pathfinding, but it allows for more efficient broader adaptations to then be taken and utilised. Using this methodology 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.

Both of these instances were created for two separate projects I worked on through the year, and I found it enjoyable to explore this methodology to such a degree.

I do 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.