Pathfinding with A* algorithm in Unity small game project

  • 02nd Jul 2020
  • by Pav
  • Reading Time: 5 minutes

Introduction

In this tutorial we are going to look into the pathfinding of the shortest route between two points in a tilemap-based world on a basis of a grid. It is a continuation of the previous article where I’ve presented the concepts behind A* search algorithm. Last time, I’ve implemented a grid that now will be used by enemies to move around levels. That is to say, the enemies will independently wander around a game world without bumping into obstacles.

Table of contents:

  1. In preparation for pathfinding
  2. The core of pathfinding A* search algorithm

1. In preparation for pathfinding

The implementation of the main runtime pathfinding algorithm will require few helper methods.

Firstly, we are going to need a method that will convert the character’s game world position to the cell position in a grid. This is essential since we need to know the location of the cell inside our grid to which we want to calculate our path to. To that end, I’m going to use the built-in ‘WorldToCell()’ tilemap member method and extract the necessary cell data stored inside my data structure.

Secondly, I’ll need a function that returns the distance between two arbitrary cells in a grid. As we remember from the previous article, the algorithm may have to adjust the costs of a specific cell if it lies on a shorter path than the already established one.

Thirdly, we need to reverse the order of the cells constituting a final path the algorithm found. This is to make our enemy follow the path from the beginning to the end rather than vice-versa.

Converting world position to cell position

Let’s start from writing a helper method that will take the world position of a character and convert it to cell position in a grid. We are going to use this function whenever we need to find out the exact cell location on our path.

WorldTile GetWorldTileByCellPosition(Vector3 worldPosition)
{
    Vector3Int cellPosition = floor.WorldToCell(worldPosition);
    WorldTile wt = null;
    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>();
                    
                // we are interested in walkable cells only
                if (_wt.walkable && _wt.cellX == cellPosition.x && _wt.cellY == cellPosition.y) {
                    wt = _wt;
                    break;
                } else {
                    continue;
                }
            }
        }
    }
    return wt;
}

Please note that I’m aiding myself here with a built-in ‘WorldToCell’ function. This is to get the tile position in a tilemap (line 3) and use it to extract the exact cell from our grid (line 11).

Getting distance between two cells in a grid

Next on our list is a method with which I’m going to get a distance between two arbitrary cells. I’ll follow the theory from the previous article and use the costs of movements to calculate the totals. These are based on the amounts of individual moves the algorithm needs to take to reach a cell from a different cell.

int GetDistance(WorldTile nodeA, WorldTile nodeB)
{
    int dstX = Mathf.Abs(nodeA.gridX- nodeB.gridX);
    int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

    if (dstX > dstY)
        return 14 * dstY + 10 * (dstX - dstY);
    return 14 * dstX + 10 * (dstY - dstX);
}

Please refer to the previous article if you have trouble understanding why I’m using 10 and 14 coefficients here. These are basically movement costs from cell to cell in both cardinal and diagonal directions.

Tracing and sorting cells in a found path

We need one more helper method that will be responsible for tracing back the path. This is to ensure that our enemy moves from the beginning till the end of the established route. There’s no bigger philosophy behind it. We are only going to need a temporary list to hold our intermediate results during the processing.

List<WorldTile> RetracePath(WorldTile startNode, WorldTile targetNode)
{
    List<WorldTile> path = new List<WorldTile>();
    WorldTile currentNode = targetNode;

    while(currentNode != startNode) {
        path.Add(currentNode);
        currentNode = currentNode.parent;
    }

    path.Reverse();
    return path;
}

Now that we have all the necessary helper methods in place we can move onto the implementation of the main algorithm.

2. The core of pathfinding A* search algorithm

In this chapter I’ll start by recapping quickly the A* search algorithm. After that, I’ll move on to the implementation of the script on a basis of a pseudocode outlining all necessary steps to find the path. I’ll finish by making my enemy follow the established route path. Let’s get right to it!

Recapping the pseudocode

I have already outlined the pseudocode of A* search algorithm in the last article. However, let’s recap all steps that need to be executed in a specific order during pathfinding procedure. The pseudocode is the following:

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

We now have all the elements to start writing the main algorithm. Let’s get right to it!

The runtime pathfinding code implementation

In this section I’ll focus on the main code that’s going to be executed at runtime by enemies to navigate around levels. The implementation of the A* search algorithm will be done on a basis of a pseudocode presented earlier. The algorithm can be implemented with any programming language but since we are working in Unity I’ll take the full advantage of C#. The full code listing is the following:

void FindPath(Vector3 startPosition, Vector3 endPosition)
{
    WorldTile startNode = GetWorldTileByCellPosition(startPosition);
    WorldTile targetNode = GetWorldTileByCellPosition(endPosition);

    List<WorldTile> openSet = new List<WorldTile>();
    HashSet<WorldTile> closedSet = new HashSet<WorldTile>();
    openSet.Add(startNode);

    while (openSet.Count > 0)
    {
        WorldTile 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)
        {
            RetracePath(startNode, targetNode);
            return;
        }

        foreach (WorldTile neighbour in currentNode.myNeighbours) {
            if (!neighbour.walkable || closedSet.Contains(neighbour)) continue;

            int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
            if(newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
            {
                neighbour.gCost = newMovementCostToNeighbour;
                neighbour.hCost = GetDistance(neighbour, targetNode);
                neighbour.parent = currentNode;

                if (!openSet.Contains(neighbour))
                    openSet.Add(neighbour);
            }
        }
    }
}

The listing above is self-explanatory. It corresponds directly to the logic outlined in previous section. The WorldTile type object represents a singular cell a grid. I’m starting by extracting the position of the starting and ending cells in a grid on a basis of the global positions (lines 3-4). These are given as function paramaters in a form of Vector3 and later converted with GetWorldTileByCellPosition() we wrote earlier. After that I’m following the algorithmic steps outlined in the pseudocode. Once the path is found I’m reversing the order of the cell nodes it constitutes with RetracePath() function. I’m doing this in preparation for moving the enemies along path from cell to cell in a natural manner.

Let’s move to our next destination!

So we have found the path but now we want our enemy to follow it. There are many different ways of doing it, but what I’m going to do is to reuse the grid-based movement scripts described here and here. The Update() function already has the code responsible for executing the movement. However, we need to adjust the setMovementVector() method which specifies the direction in which we want our enemy to move at a given frame. In other words, we have to ensure that the ‘movement’ Vector2 contains the data corresponding to the cell’s location at a given point in a path. Once the vector is set, the Update() method will execute the movement automatically. Please refer to my earlier articles for the full implementation details (grid-based movement and building Unity games on iPhone).

public class Movement : MonoBehaviour
{
    Vector3 lastDirection = Vector3.zero;
    bool moveDone = false;   
    List<WorldTile> reachedPathTiles = new List<WorldTile>(); 

    void Start() {
        ...
    }

    void Update() {
         MovementPerformed();
    }
    
    void MovementPerformed() {
        ...
    }

    void SetMovementVector()
    {
        if (path != null)
        {
            if (path.Count > 0)
            {
                if (!moveDone)
                {
                    for (int i = 0; i < path.Count; i++)
                    {
                        if (reachedPathTiles.Contains(path[i])) continue;
                        else reachedPathTiles.Add(path[i]); break;
                    }
                    WorldTile wt = reachedPathTiles[reachedPathTiles.Count - 1];
                    lastDirection = new Vector3(Mathf.Ceil(wt.cellX - transform.position.x), Mathf.Ceil(wt.cellY - transform.position.y), 0);
                    if (lastDirection.Equals(Vector3.up)) movement.y = 1;
                    if (lastDirection.Equals(Vector3.down)) movement.y = -1;
                    if (lastDirection.Equals(Vector3.left)) movement.x = -1;
                    if (lastDirection.Equals(Vector3.right)) movement.x = 1;
                    moveDone = true;
                }
                else
                {
                    movement = Vector2.zero;
                    if (Vector3.Distance(transform.position, movePoint.position) <= .001f)
                        moveDone = false;
                }
            }
        }
    }

}

Congratulations! If you have implemented everything up till now your enemy should be moving independently across the level. At this stage you can take this anywhere you want. For instance you can develop this script further to swap between different enemy states such as “chasing” or “on patrol” like in the animation below. The blue squares represent the cells that are part of the newly found path while the red one – the current direction.

The pathfinding algorithm in action

Conclusion

In this article I have presented an example of the implementation of an A* search algorithm in Unity. The material that was presented in the previous article became a foundation of a pathfinding function. I used the traversable grid to find the candidate cells that could constitute a final path between two points on a map. During the process the algorithm makes sure to adjust different costs in cases when shorter route is available. At the end I showed how the path can steer the enemy through the level while avoiding the obstacles.

References

A* Pathfinding (E03: algorithm implementation) by Sebastian Lague