A* Pathfinding


Even if you are not a game developer you’ve probably heard the name “A*” (A Star). In this tutorial I will try to introduce you to this algorithm.

You can download a full project from GitHub:

Unity project

I used the Unity Chan model which is available for free on the Asset Store

I encourage you to take a look into the project and see by yourself how it works.  There are already some basic classes responsible for generating the grid, managing the character movement etc.

Grid size

GridManager

In the scene Pathfinding.unity you can find a game object called GridManager  with attached script of the same name. You can specify there a size of your grid.

Under the Resources folder you can find a prefab called NodeVisual which is the base tile that all the grid will be built of. Another interesting thing is the ScriptableObject called Tiles. It hold an array of all the terrain types specified in the enum TerrainType.cs. You can set there a colour that the terrain is visualised with, and the cost of moving on this terrain.

Unity project

NodeVIsual and Tiles editor

When you hit Play, the grid is of specified size is being generated with the NodeVisual in the Resources folder. By Right-Click on the node you switch to the next TerrainType. As you drag mouse over the nodes, the new path is calculated. When you Left-Click on any of them, Unity Chan will go to the selected node:

Preview

Top-down view of the scene

 


The A* algorithm

 

To make long story short, A* is a pathfinding algorithm widely used in all kind of video games. It is an extension of Dijkstra algorithm. Its biggest advantage over Dijkstra algorithm is that it uses a heuristic that estimates which nodes of the graph should be traversed first.

Our heuristic will be a distance from the current node to the target node. Here is a great article about two most popular heuristics used with 2D  grids.

There are many algorithms out there that can outperform A* (most modern game engines use Navigation meshes), but I can imagine many situations where it can be still used. One of the most common applications is finding the shortest path in tile-based games. Let’s dive right into it.

Imagine a 2D grid of nodes like on a picture below:

5x3 grid of tiles

5×3 grid of nodes

Each of these green tiles will be called a Node. You can move in this grid vertically, horizontally and diagonally.

Here is the Pseudocode:

  1. Declare open set for nodes that are being evaluated and closed set for nodes that has been already checked
  2. With given start and target nodes, add start node to the open list
  3. While open set is not empty
    3.1. Find a node with the lowest F cost int the open set and assign it to variable current node
    3.2. Remove current node from open set and add it to closed set
    3.3. Check if current node is the target node, if yes – return
    3.4. For each neighbouring node which is walkable and is not in the closed set:
    3.4.1. If path to neighbour is shorter or neighbour is not in open set
    3.4.1.a. Set F cost of neighbour
    3.4.1.b. Set current as parent of neighbour
    3.4.1.c. Add neighbour to open set if it’s not there yet
  4. If outside of loop, return null – cannot find the path

 

Here is how it looks like in real-life C# code:

 

If it’s still not clear for you, no worries, I will go through it step-by-step.

Let’s assume that Unity Chan tries to find the shortest path from the red node to the blue node.

Target and start nodesUnity Chan

As you can see on the picture above there are three numbers inside the first node. I will use them to represent the H, G and F costs:

  • bottom – H cost (Estimated cost)
  • centre – G cost (Cost so far)
  • top – F cost (Total cost)

Green nodes represent unvisited nodes

Black nodes represent closed set

Red nodes represent open set

First iteration

First iteration

When we run the algorithm, first (start) node is added to the open set, right before entering the main loop. The exit condition of the loop is that the open set is empty. Since there is one node there in the open set, the first iteration of the loop starts. The current node is chosen by the lowest F and H cost and it’s added to the closed set.
Then, we take all the neighbours of the current nodes that are not inside the closed set and the proper G, H and F costs are calculated. the parent of the neighbour is set as a current node.

Second iteration

Second iteration

As you can see, within the second iteration of the loop, the node with the lowest F cost and H cost was chosen and we move diagonally. After checking all the neighbours and setting parents to the current node, open and closed sets should look like on a picture above.

After few more iterations, the current node will be equal to the target node (blue colour) and the main loop finishes. Because within every iteration we set the current node as a parent of all its neighbours, we can retrace the path that we need to follow.

Final Path

Final path


Summary

In this tutorial we have learnt how to implement a basic A* pathfinding algorithm in Unity3D and C#. There are plenty of optimisation we can make here. If you wish there is a next part about different variations and improvement on this pathfinding technique please let me know.

If you are interested in exploring A* by yourself, feel free to take a look into my project on GitHub.

If you found it tutorial useful, you want to learn about some other solutions, please let me know about it in the comments section below, or contact me by e-mail.

Cheers!

These are websites that you might find useful when learning about A* by yourself:

Stanford materials
Sebastian Lague Youtube tutorial

1 comment

Add yours

+ Leave a Comment