Tilemap-based A* algorithm implementation in Unity game

  • 29th Jun 2020
  • by Pav
  • Reading Time: 11 minutes

Introduction

In this tutorial we’re going to look into the implementation of Tilemap-based A* algorithm in Unity. One of the more exciting features of fully fledged games is the way the enemies can make up more intelligent decisions. It is usually thanks to underlying AI scripts responsible for processing the spatial information and forming output. In a first instance we would like the enemies to find their ways around the levels without stumbling into walls or other ‘unwalkable’ areas. When the grid-based game world is considered it is often recommended to go for a popular A* algorithm.

Table of contents:

  1. A quick theory behind A* algorithm
  2. Building a grid for Tilemap-based A* algorithm

1. A quick theory behind A* algorithm

The A* algorithm is one of the most popular search algorithms often used in different computer science fields thanks to its efficiency and self-contained nature. It is using a grid data structure to perform a specific graph traversal in order to find the shortest path between two points. It is perceived as an extension of Edsger Dijkstra’s algorithm, which was published in 1959. However, unlike Dijkstra’s algorithm, the A* algorithm uses the heuristics to guide its search in order to achieve better performance. The only major drawback is that all nodes constituting a calculated path are stored in memory, which ironically can cause some bottlenecks in memory management department.

How A* algorithm works? The basics

The A* utilizes a grid where each cell is either ‘walkable’ or ‘unwalkable’. In order to find a path between two points we have to first calculate the distance between them. That is to say, we have to specify how we are going to measure the distance between two arbitrary cells in a grid. The easiest way to approach this is to say that any move between cells in cardinal direction is equal to 1. The cost of moving between cells in a diagonal manner is then equal to \sqrt2\approx1.4. To make things easier, let’s multiply those two values by 10 so that we end up with 10 and 14 for cardinal and diagonal directions respectively. The image below represents this case scenario.

where:

  • for each cardinal direction: cd=1*10=10
  • for each diagonal direction: dd=\sqrt2\approx1.4*10=14

Finding a path between point A and B

In order to find a path between the two points depicted in the image we have to calculate the “weight costs” for each adjacent cell. There are 3 complementary costs involved in the formula – the ‘G’ cost, the ‘H’ cost and the ‘F’ cost:

  • ‘G’ cost represents the distance from starting cell node
  • ‘H’ (Heuristic) cost represents the distance from ending cell node
  • ‘F’ cost represents the sum of ‘G’ and ‘H’ costs

In other words, for each cell we have to calculate how far it is from the starting cell (‘G’ cost) and the ending cell (‘H’ cost). After that, we sum up these two values to receive the total cost (‘F’ cost). We do this for each adjacent cell. Subsequently, we select cell with the lowest ‘F’ cost and move to it. We repeat this process until we reach our destination, i.e. when the ‘H’ cost equals to 0. The image below shows how the algorithm does that.

where:

  • the red numbers represent ‘G’ cost
  • the black numbers represent the ‘H’ cost
  • the ‘F’ cost is marked with white numbers
  • the red and black lines are the example movement costs taken into consideration by the algorithm during the calculation of ‘G’ and ‘H’ costs respectively.

A more complex path finding example

We now have a very basic understanding of the A* algorithm. However, the trivial example I presented in previous subsection was only to illustrate the very principles of the algorithm. In a real game I want my enemies to walk around the obstacles such as walls. This creates a situation where there may not always be a straight path from point A to B. Consequently, the ‘F’ costs may be the same for movements on several “possible” paths that the enemy has to take in order to reach the destination. When that happens, the algorithm also looks at the ‘G’ and ‘H’ costs to decide the next cell it needs to move to.

The trick here is to calculate the costs for only the ‘walkable’ cells at each step. After that, select only those with the lowest ‘H’ cost if ‘F’ cost is the same for multiple adjacent ones. The algorithm then looks at the already calculated cells costs, updates them for the intermediate ones and explores the ones with the lowest scores. Consider the following example in the animation below. I coloured the ‘unwalkable’ cells with gray.

The tilemap-based A star algorithm finding a path step by step

Please note that the movements costs weights may have to be adjusted subject to the scrutinised “locked” (or closed) cell. For instance, if the potential path’s cell nodes suddenly deviate from the obvious routes (e.g. closer to the obstacles) then there is a possibility to come across cells with lesser ‘G’ cost but higher ‘H’ cost. If the algorithm follows this route then the previously analyzed cell may now have lesser ‘G’ cost. The algorithm takes into account the new path and updates cell’s costs to reflect that change in course. All this will hopefully become more obvious in the next subsection.

The pseudocode of the A* algorithm

At this point you should have a clear understanding of how the tilemap-based A* algorithm works. In this sub-chapter I will summarize all the steps discussed so far with a pseducocode that needs to be executed at runtime in order to find a path between two points.

OPEN_LIST
CLOSED_LIST
ADD start_cell to OPEN_LIST

LOOP
    current_cell = cell in OPEN_LIST with the lowest F_COST
    REMOVE current_cell from OPEN_LIST
    ADD current_cell to CLOSED_LIST

IF current_cell is finish_cell
    RETURN

FOR EACH adjacent_cell to current_cell
    IF adjacent_cell is unwalkable OR adjacent_cell is in CLOSED_LIST
        SKIP to the next adjacent_cell

    IF new_path to adjacent_cell is shorter OR adjacent_cell is not in OPEN_LIST
        SET F_COST of adjacent_cell
        SET parent of adjacent_cell to current_cell
        IF adjacent_cell is not in OPEN_LIST
            ADD adjacent_cell to OPEN_LIST

There are two lists that will keep track of the scrutinized cells. The open list contains all the cells that are to be analyzed and evaluated. The analogous closed list has all the cells we’ve finished inspecting. We begin by adding the starting point cell to the open list and enter the loop. As long as the open list has cells to analyze and until we stumble across finish_cell we are going to run it.

We assign the temporary current_cell variable with a cell from the open list with the lowest ‘F’ cost. After that, we remove it from the open list and then add it to the closed one. Next we check if that current_cell variable is in fact the finish_cell and if it is, we are going to stop since the path has been found. However, if we have passed this point we are going loop through all the current_cell adjacent cells that are ‘walkable’ and not already in closed list. If the distance to the adjacent_cell is shorter we need to adjust its ‘F’ cost. After that, we parent it to the current_cell and finish by making sure the adjacent_cell is in the open list.

That wraps up the the theory! Let’s now get to practice!

2. Building a grid for Tilemap-based A* algorithm

Firstly, we are going to need a class representing a cell in our grid. All the fields inside it are going to contain the values we have discussed so far. However, due to practical reasons I’m going to introduce 4 additional integers. Two of them will help me to keep track of cells in memory and grid (gridX, gridY) and the other two their physical locations in a game world (cellX, cellY).

using System.Collections.Generic;
using UnityEngine;

public class WorldTile : MonoBehaviour
{
    public int gCost;
    public int hCost;
    public int gridX, gridY, cellX, cellY;
    public bool walkable = true;
    public List<WorldTile> myNeighbours;
    public WorldTile parent;

    public WorldTile(bool _walkable, int _gridX, int _gridY)
    {
        walkable = _walkable;
        gridX = _gridX;
        gridY = _gridY;
    }

    public int fCost
    {
        get
        {
            return gCost + hCost;
        }
    }
}

Now we have to create a script that will be responsible for laying out the grid in memory. I will do this on a basis of the tilemaps that are normally used to create levels. To that end, I’m going to need references to the ‘Grid’ component, ‘walkable’ tilemap and all ‘unwalkable’ tilemaps that can be placed on different layers.

public class CreateGrid : MonoBehaviour
{
    Grid gridBase;
    Tilemap floor;                         // walkable tilemap
    public List<Tilemap> obstacleLayers;   // all layers that contain objects to navigate around
    public GameObject gridNode;            // where the generated tiles will be stored
    public GameObject nodePrefab;          // world tile prefab

    //these are the bounds of where we are searching in the world for tiles, have to use world coords to check for tiles in the tile map
    public int scanStartX = -300, scanStartY = -300, scanFinishX = 300, scanFinishY = 300, gridSizeX, gridSizeY;

    private List<GameObject> unsortedNodes;   // all the nodes in the world
    public GameObject[,]     nodes;           // sorted 2d array of nodes, may contain null entries if the map is of an odd shape e.g. gaps
    private int gridBoundX = 0, gridBoundY = 0;
}

I will use the gridBoundX and gridBoundY integers to check if during a scan I’m hitting a boundary. It will prevent a stack overflow error when adding cells to the list. The nodePrefab field will contain a prefab I’m going to instantiate in a place of a cell. This is a highly unoptimized approach but during the test runs I want to make sure that the cells in memory correspond to the tiles in tilemaps. To do this, our prefab will have a Sprite Renderer component so that I can have some visualisation of the cell. In the production code I will change it so that no Game Objects are ever instantiated.

After we defined all necessary fields, we need to start by defining the size of our grid.

void Start()
{
    gridSizeX = Mathf.Abs(scanStartX) + Mathf.Abs(scanFinishX);
    gridSizeY = Mathf.Abs(scanStartY) + Mathf.Abs(scanFinishY);
}

The grid creation methods for tilemap-based A* algorithm

Before I jump into writing a function that will create the actual grid I’ll add one extra helper method. I will use it for getting the adjacent cells of any cell. It is going to be a pretty long one since I need to consider all directions, account odd shapes of the terrain and grid boundaries.

public List<WorldTile> getNeighbours(int x, int y, int width, int height)
{
    List<WorldTile> myNeighbours = new List<WorldTile>();

        if (x > 0 && x < width - 1) {
            if (y > 0 && y < height - 1) {
                if (nodes[x + 1, y] != null) { 
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }

                if (nodes[x, y + 1] != null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null) myNeighbours.Add(wt3);
                }

                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null) myNeighbours.Add(wt4);
                }
            }
            else if (y == 0)
            {
                if (nodes[x + 1, y] != null) {
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }

                if (nodes[x, y + 1] == null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null) myNeighbours.Add(wt3);
                }
            }
            else if (y == height - 1)
            {
                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null) myNeighbours.Add(wt4);
                }
                if (nodes[x + 1, y] != null) {
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }
            }
        }
        else if (x == 0)
        {
            if (y > 0 && y < height - 1)
            {
                if (nodes[x + 1, y] != null) {
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null)myNeighbours.Add(wt4);
                }

                if (nodes[x, y + 1] != null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null) myNeighbours.Add(wt3);                    
                }
            }
            else if (y == 0)
            {
                if (nodes[x + 1, y] != null) {
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x, y + 1] != null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null) myNeighbours.Add(wt3);
                }
            }
            else if (y == height - 1)
            {
                if (nodes[x + 1, y] != null) {
                    WorldTile wt1 = nodes[x + 1, y].GetComponent<WorldTile>();
                    if (wt1 != null) myNeighbours.Add(wt1);
                }

                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null) myNeighbours.Add(wt4);
                }
            }
        }
        else if (x == width - 1)
        {
            if (y > 0 && y < height - 1)
            {
                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }

                if (nodes[x, y + 1] != null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null)myNeighbours.Add(wt3);
                }

                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null)  myNeighbours.Add(wt4);
                }
            }
            else if (y == 0)
            {
                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }
                if (nodes[x, y + 1] != null) {
                    WorldTile wt3 = nodes[x, y + 1].GetComponent<WorldTile>();
                    if (wt3 != null) myNeighbours.Add(wt3);
                }
            }
            else if (y == height - 1)
            {
                if (nodes[x - 1, y] != null) {
                    WorldTile wt2 = nodes[x - 1, y].GetComponent<WorldTile>();
                    if (wt2 != null) myNeighbours.Add(wt2);
                }

                if (nodes[x, y - 1] != null) {
                    WorldTile wt4 = nodes[x, y - 1].GetComponent<WorldTile>();
                    if (wt4 != null) myNeighbours.Add(wt4);
                }
            }
        }

    return myNeighbours;
}

Now we are ready to write the main method. I will need to scan through the boundaries of the area I defined earlier. The temporary variables will help me through navigating the cells and keep track of where I am in the process. The gridX and gridY will ensure that I’m not hitting the boundary of the scanned area of the levels.

void createGrid()
{
    int gridX = 0, gridY = 0; 
    bool foundTileOnLastPass = false;
    for (int x = scanStartX; x < scanFinishX; x++) {
        for (int y = scanStartY; y < scanFinishY; y++) {

        }
    }
}

Next, I’ll extract the tile from the ‘walkable’ tilemap and see if it lies within any of the ‘unwalkable’ layers. Depending on what layer the tilemap cell lies it is ‘recreated’ for the purposes of the grid. I’m using the world position of the cell to get the position of the tile in the tilemap. This data will be later used during path finding.

void createGrid()
{
    int gridX = 0, gridY = 0; 
    bool foundTileOnLastPass = false;
    for (int x = scanStartX; x < scanFinishX; x++) {
        for (int y = scanStartY; y < scanFinishY; y++) {
            TileBase tb = floor.GetTile(new Vector3Int(x, y, 0)); 
            if (tb != null) {
                bool foundObstacle = false;
                foreach (Tilemap t in obstacleLayers) {
                    TileBase tb2 = t.GetTile(new Vector3Int(x, y, 0));
                    if (tb2 != null) foundObstacle = true;
                }

                Vector3 worldPosition = new Vector3(x + 0.5f + gridBase.transform.position.x, y + 0.5f + gridBase.transform.position.y, 0);
                GameObject node = (GameObject)Instantiate(nodePrefab, worldPosition, Quaternion.Euler(0, 0, 0));
                Vector3Int cellPosition = floor.WorldToCell(worldPosition);
                WorldTile wt = node.GetComponent<WorldTile>();
                wt.gridX = gridX; wt.gridY = gridY; wt.cellX = cellPosition.x; wt.cellY = cellPosition.y;
                node.transform.parent = gridNode.transform;

                if (!foundObstacle) {
                    foundTileOnLastPass = true;
                    node.name = "Walkable_" + gridX.ToString() + "_" + gridY.ToString();
                } else {
                    foundTileOnLastPass = true;
                    node.name = "Unwalkable_" + gridX.ToString() + "_" + gridY.ToString();
                    wt.walkable = false;
                    node.GetComponent<SpriteRenderer>().color = Color.red;
                }

                unsortedNodes.Add(node);

                gridY++; 
                if (gridX > gridBoundX)
                    gridBoundX = gridX; 

                if (gridY > gridBoundY)
                    gridBoundY = gridY;
            }
        }

        if (foundTileOnLastPass) {
            gridX++;
            gridY = 0;
            foundTileOnLastPass = false;
        }
    }
}

Looking good, but we still need to sort out our cells in the grid. Furthermore, we need to get the lists of all adjacent tiles. We do this by utilizing the helper method I wrote earlier.

void createGrid()
{
    int gridX = 0, gridY = 0; 
    bool foundTileOnLastPass = false;
    for (int x = scanStartX; x < scanFinishX; x++) {
        for (int y = scanStartY; y < scanFinishY; y++) {
            TileBase tb = floor.GetTile(new Vector3Int(x, y, 0)); 
            if (tb != null) {
                bool foundObstacle = false;
                foreach (Tilemap t in obstacleLayers) {
                    TileBase tb2 = t.GetTile(new Vector3Int(x, y, 0));
                    if (tb2 != null) foundObstacle = true;
                }

                Vector3 worldPosition = new Vector3(x + 0.5f + gridBase.transform.position.x, y + 0.5f + gridBase.transform.position.y, 0);
                GameObject node = (GameObject)Instantiate(nodePrefab, worldPosition, Quaternion.Euler(0, 0, 0));
                Vector3Int cellPosition = floor.WorldToCell(worldPosition);
                WorldTile wt = node.GetComponent<WorldTile>();
                wt.gridX = gridX; wt.gridY = gridY; wt.cellX = cellPosition.x; wt.cellY = cellPosition.y;
                node.transform.parent = gridNode.transform;

                if (!foundObstacle) {
                    foundTileOnLastPass = true;
                    node.name = "Walkable_" + gridX.ToString() + "_" + gridY.ToString();
                } else {
                    foundTileOnLastPass = true;
                    node.name = "Unwalkable_" + gridX.ToString() + "_" + gridY.ToString();
                    wt.walkable = false;
                    node.GetComponent<SpriteRenderer>().color = Color.red;
                }

                unsortedNodes.Add(node);

                gridY++; 
                if (gridX > gridBoundX)
                    gridBoundX = gridX; 

                if (gridY > gridBoundY)
                    gridBoundY = gridY;
            }
        }

        if (foundTileOnLastPass) {
            gridX++;
            gridY = 0;
            foundTileOnLastPass = false;
        }
    }

    nodes = new GameObject[gridBoundX + 1, gridBoundY + 1];

    foreach (GameObject g in unsortedNodes) { 
        WorldTile wt = g.GetComponent<WorldTile>();
        nodes[wt.gridX, wt.gridY] = g;
    }

    for (int x = 0; x < gridBoundX; x++) {
        for (int y = 0; y < gridBoundY; y++) {
            if (nodes[x, y] != null) { 
                WorldTile wt = nodes[x, y].GetComponent<WorldTile>(); 
                wt.myNeighbours = getNeighbours(x, y, gridBoundX, gridBoundY);
            }
        }
    }
}

When you run this method in the beginning using Start() function your grid will be created. If you have used the Sprite Renderer component inside the cell prefab then you can easily visualise it. The example of how this may look like is shown in the next image.

The end result of tilemap-based grid creation for A* algorithm

Conclusion

Writing a good AI for games enemies is never easy. It always requires a good amount of skill to convince the player that he’s facing an intelligent being rather than just empty shell. One of the oldest and popular algorithms that can help achieving that goal is the tilemap-based A* algorithm. It is utilized in many different computer science fields to find the shortest path between two points in some kind of a graph or grid. In this tutorial I have presented the theory behind it and the main principles of its mechanism. After that I moved on to the implementation of a grid based on native tilemap system of Unity. This was made in preparation for the next article in the series where I’m going to focus on finding a path between two points.

References

The A* Search Algorithm from Wikipedia free encyclopedia
A* Search Algorithm by Rachit Belwariar
A* Pathfinding (E01: algorithm explanation) by Sebastian Lague
Creating AStar Nodes from Unity Tilemaps by Unit02Games