A Small Game In Unity With A* Pathfinding Algorithm

In this lesson, we'll examine how to use a grid to determine the shortest path between two points in a tilemap-based environment. In other words, adversaries will move around a game world on their own without running into any impediments.

Preparation of Pathfinding:

To effectively implement the core runtime pathfinding algorithm, a few auxiliary methods will prove indispensable.

Initially, we require a method that translates the character's position within the game world into the corresponding cell position on a grid. This conversion is crucial as it pinpoints the grid cell to which the path should be calculated. I shall achieve this by utilizing the built-in 'WorldToCell()' tilemap member method, extracting the pertinent cell data stored within my designated data structure.

Additionally, a function is necessary to determine the distance between any two arbitrary cells within the grid. This distance calculation is pivotal as the algorithm might need to adjust the cost of a specific cell if it lies along a shorter path than the currently established route.

Lastly, a means to reverse the order of cells forming the final path is indispensable. This reversal ensures that our enemy character follows the path in chronological order, progressing from the starting point to the destination rather than the opposite direction.

Convert Position of Object to Cell Position:

Let's begin by creating a helper method that will translate a character's world position into a grid cell position. Anytime we need to know the precise location of a cell on our path, we will call this function.

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 take note that I'm using the built-in 'WorldToCell()' function to help myself here. In order to retrieve the precise cell from our grid (line 11), we must first obtain the tile position in a tilemap (line 3).

Calculate Distance Between Two Cells:

The method I am going to use to calculate the distance between two random cells is the next item on our list. I'll apply the principle from the earlier article and compute the sums using the expenses of motions. These are based on the number of discrete steps the algorithm must take to travel from one cell to another.

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);
}        

If you have any trouble understanding why I'm using 10 and 14 coefficients here, please refer to the prior article. Basically, these are the expenses associated with moving between cells in both cardinal and diagonal orientations.

Tracing and Sorting Cells in Found Path:

Another essential auxiliary method is required to facilitate the retracing of the path. This function serves the purpose of ensuring that our enemy character traverses the established route from its inception to its conclusion. The concept behind this method is straightforward, we will utilize a temporary list to temporarily store the intermediate outcomes while the processing takes place.

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;
}        

The Core Logic of A* Pathfinding Search Algorithm:

In this section, I'll begin by offering a concise review of the A* search algorithm. Following this, I will proceed with the implementation of the script, drawing from a pseudocode that lays out the essential stages for pathfinding. Concluding this section, I will guide the process of having the enemy character navigate along the established path. Let's dive right in!

Recapping the Pseudocode:

To ensure clarity, let's revisit the pseudocode for the A* search algorithm outlined in the previous article. It encompasses a sequence of specific steps that must be executed in a defined order during the pathfinding process. The pseudocode is as follows:

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        

The Runtime Pathfinding Code Implementation:

In this segment, the primary emphasis will be on the core code responsible for guiding enemies real-time navigation within game levels. The implementation of the A* search algorithm will adhere closely to the earlier introduced pseudocode. While the algorithm can be realized in various programming languages, I shall leverage the capabilities of C# since we are operating within the Unity framework. The comprehensive code listing is as follows:

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 code snippet presented above is fairly self-explanatory and closely mirrors the logical progression detailed in the preceding section. The 'WorldTile' object type denotes an individual cell within the grid. The process commences by extracting the positions of both the starting and ending cells within the grid, derived from the global positions (lines 3-4). These positions are initially passed as function parameters in the form of Vector3 coordinates, subsequently converted using the 'GetWorldTileByCellPosition()' function established earlier.

Subsequently, the code aligns with the sequential steps outlined within the pseudocode. Once the path is successfully identified, the order of the cell nodes composing it is inverted via the 'RetracePath()' function. This preparatory step ensures the seamless movement of enemies along the path, transitioning from one cell to the next in a fluid and natural manner.

Move to Next Destination:

Now that we've successfully determined the path, the subsequent objective is to guide our enemy along it. While numerous methodologies can achieve this, I've opted to repurpose the grid-based movement scripts discussed in previous sections (linked here and here). The existing 'Update()' function already encompasses the code responsible for executing movement. However, an adjustment is necessary for the 'setMovementVector()' method, which stipulates the direction the enemy should move in at each frame.

Essentially, we need to ensure that the 'movement' Vector2 variable contains the data corresponding to the cell's location at any given point along the path. Following the vector's configuration, the 'Update()' method will facilitate automatic movement execution. For comprehensive insights into the implementation details, I invite you to review my earlier articles encompassing grid-based movement and Unity game development on iPhones.

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 on your progress! Assuming you've successfully executed the steps discussed so far, your enemy character should now be autonomously navigating throughout the level. At this juncture, the possibilities are vast, allowing you to extend the functionality in diverse directions. For example, you can choose to expand upon this script to incorporate distinct enemy states like "chasing" or "patrolling", reminiscent of the animation depicted below.

In the animation, the blue squares signify the cells encompassing the newly determined path, while the red square denotes the current direction. The groundwork has been laid, and the potential for further development is at your fingertips.

I trust you've found this tutorial valuable. Should you have any inquiries or thoughts to share, or perhaps you've ingeniously incorporated additional captivating effects using Unity's 2D techniques, feel free to share them with us in the comments section below. Your feedback and insights are greatly appreciated!

We also provide Services of 2D/3D Game Development, 2D/3D Animations, Video Editing and UI/UX Designing.

If you have questions or suggestions related to game or want something to build from us, Feel free to reach out to us anytime!

?? Mobile: +971 544 614 238

?? Email: [email protected]