# 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**:

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.

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.

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:

# 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:

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

Here is the Pseudocode:

- Declare open set for nodes that are being evaluated and closed set for nodes that has been already checked
- With given start and target nodes, add start node to the open list
- 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 - If outside of loop, return null – cannot find the path

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
using UnityEngine; using System.Collections.Generic; namespace Pathfinding { public static class AStar { static public List<Node> FindPath(Node startNode, Node targetNode, Grid grid) { List<Node> openSet = new List<Node>(); openSet.Add(startNode); List<Node> closedSet = new List<Node>(); while (openSet.Count > 0) { Node currentNode = openSet[0]; for (int i = 1; i < openSet.Count; i ++) { if (openSet[i].FCost < currentNode.FCost || (openSet[i].FCost == currentNode.FCost && openSet[i].HCost < currentNode.HCost)) { currentNode = openSet[i]; } } openSet.Remove(currentNode); closedSet.Add(currentNode); if (currentNode == targetNode) { return RetracePath(startNode, targetNode); } foreach (Node connection in grid.GetConnections(currentNode)) { if (connection.Walkable && !closedSet.Contains(connection)) { int costToConnection = currentNode.GCost + GetEstimate(currentNode, connection) + connection.Cost; if (costToConnection < connection.GCost || !openSet.Contains(connection)) { connection.GCost = costToConnection; connection.HCost = GetEstimate(connection, targetNode); connection.Parent = currentNode; if (!openSet.Contains(connection)) { openSet.Add(connection); } } } } } return null; } private static List<Node> RetracePath(Node startNode, Node endNode) { List<Node> path = new List<Node>(); Node currentNode = endNode; while (currentNode != startNode) { path.Add(currentNode); currentNode = currentNode.Parent; } path.Reverse(); return path; } private static int GetEstimate(Node first, Node second) { int distance; int xDistance = Mathf.Abs(first.X - first.X); int yDistance = Mathf.Abs(second.Y - second.Y); if (xDistance > yDistance) { distance = 14 * yDistance + 10 * (xDistance - yDistance); } else { distance = 14 * xDistance + 10 * (yDistance - xDistance); } return distance; } } } |

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.

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**

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.

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.

# 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

Man, this tutorial is awesome. Please post more often tutorial like these.