Implement A* Pathfinding in Mazes in Unity2D

This tutorial will show how to implement A* pathfinding in mazes in Unity2D by applying a generic pathfinder.

We are not limited to using A* alone. We can use any pathfinders (A*, Djikstra or Greedy-best first) that come with the generic Pathfinder.

This tutorial is Part 2 of my tutorials on mazes. In the first part, Implement Mazes in Unity2D, we learnt how to implement mazes in Unity2D by applying the backtracking algorithm with an explicit stack.

In this tutorial, we will use the generated maze and apply Pathfinding to it.

Prerequisites for this Tutorial

This tutorial does not have any dependency as I have provided a starter package for you. However, I recommend that you refer to the following two tutorials for a better understanding.

1. Implement Mazes in Unity2D: Read the first part of the tutorial and understand how we can implement mazes in Unity2D by applying the backtracking algorithm with an explicit stack.
2. Implement a Generic Pathfinder in Unity using C#: Read the pathfinding tutorial that implements a generic pathfinder in Unity using C#. In this tutorial, we create a generic pathfinder that is algorithm agnostic. Then we create three implementations of the pathfinder using the A*, Djikstra and Greedy best-first algorithm. We apply this generic pathfinder to various pathfinding problems (8-Puzzle, rectangular grid-based map and graph-based map).

Contact me

Star

Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/tutorial-maze.

Pathfinding in Mazes

Create a new Unity 2D project. Download and import the starter package. The starter package contains the scripts, the prefabs and the scene from our last tutorial. It also includes the generic Pathfinder related scripts.

Select the Demo_MazeGeneration scene. Click Play and run the scene. You should see a maze being generated, like the video below.

Duplicate this scene and rename it to Demo_MazePathfinding. Double click and load the scene. We will now proceed to integrate our Pathfinder and implement Pathfinding in mazes.

Make Changes to Cell Class

Our Pathfinder uses a generic Node class. We want our Cell class derived from this generic Node.

Go ahead and make the following change to the Cell class.

 public class Cell : Node<Vector2Int>Code language: C# (cs)

Remember to add the using GameAI.PathFinding on top of the file.

This class is the primary node type for a maze-based map. We will derive this class from GameAI.Pathfinding.Node generic class. For a maze, we will use the Vector2Int type to represent the location of the cell.

From our previous tutorial, we had int x and int y to store the index of the cell. Once we derive our class from Node<Vector2Int>, the base class will hold the index via the Value property. We make the following change to remove the int x and int y from the Cell class.

    //public int x; //old code
    //public int y; //old code
    public int x { get { return Value.x; } }
    public int y { get { return Value.y; } }
Code language: C# (cs)

Instead of removing, we just changed x and y to properties and returned the values via Value.x and Value.y.

Change the constructor to call the base class’ constructor.

    // constructor
    public Cell(int c, int r, Maze maze)
      : base(new Vector2Int(c, r))
    {
      //x = c; //old code
      //y = r; //old code
      mMaze = maze;
    }
Code language: C# (cs)

GetNeighbour Function

The base generic class Node is abstract. We will need to implement the GetNeighbour function so that our Pathfinder can traverse the map.

    // get the neighbours for this cell.
    // here will will just throw the responsibility
    // to get the neighbours to the grid.
    public override List<Node<Vector2Int>> GetNeighbours()
    {
      List<Node<Vector2Int>> neighbours = new List<Node<Vector2Int>>();
      foreach (Directions dir in Enum.GetValues(typeof(Directions)))
      {
        int x = Value.x;
        int y = Value.y;
        switch (dir)
        {
          case Directions.UP:
            if (y < mMaze.NumRows - 1)
            {
              ++y;
              if (!flag[(int)dir])
              {
                neighbours.Add(mMaze.GetCell(x, y));
              }
            }
            break;
          case Directions.RIGHT:
            if (x < mMaze.NumCols - 1)
            {
              ++x;
              if (!flag[(int)dir])
              {
                neighbours.Add(mMaze.GetCell(x, y));
              }
            }
            break;
          case Directions.DOWN:
            if (y > 0)
            {
              --y;
              if (!flag[(int)dir])
              {
                neighbours.Add(mMaze.GetCell(x, y));
              }
            }
            break;
          case Directions.LEFT:
            if (x > 0)
            {
              --x;
              if (!flag[(int)dir])
              {
                neighbours.Add(mMaze.GetCell(x, y));
              }
            }
            break;
          default:
            break;
        }
      }
      return neighbours;
    }Code language: C# (cs)

Add the NPC and Destination Prefabs

The starter package comprises NPC and Destination prefabs. These two prefabs contain sprite renderer components to provide visual cues. The NPC prefab also includes a script component that allows the movement of the game object via waypoints.

Drag and drop these two prefabs into the scene. We will use the NPC prefab to move across the maze and the destination prefab to provide a visual indication of our target destination.

Maze Pathfinder Game Object

Right-click on the project hierarchy and add a new empty game object. Name it MazePathfinder. Select it, go to the inspector and add a new script component of the same name.

Double-click the MazePathfinder script and open it in Visual Studio (or our favourite IDE).

First, we will implement the functionality to select a destination cell and make the NPC move to the chosen destination cell without Pathfinding. Once we achieve this functionality, we will move on to integrate the Pathfinding.

Add the following variables.

  public Transform mDestination;
  public NPC mNpc;
  public MazeGenerator mMazeGenerator;
  // The start and the goal cells.
  private Cell mStart;
  private Cell mGoal;
Code language: C# (cs)

Implement the Start method.

  void Start()
  {
    mDestination.gameObject.SetActive(false);
    mNpc.gameObject.SetActive(false);
    // wait for maze generation to complete.
    StartCoroutine(Coroutine_WaitForMazeGeneration());
  }
Code language: JavaScript (javascript)

In the Start method, you can see that we wait for the maze generation to complete using the Coroutine Coroutine_WaitForMazeGeneration.

We also have SetActive to false for both the Destination and the NPC game objects. We will enable them when we complete the maze generation.

Next, we implement the coroutine Coroutine_WaitForMazeGeneration.

  IEnumerator Coroutine_WaitForMazeGeneration()
  {
    while (!mMazeGenerator.MazeGenerationCompleted)
      yield return null;
    // set the start cell to cell 0, 0.
    mStart = mMazeGenerator.mMazeCells[0, 0].Cell;
    mGoal = mStart;
    // maze generation completed.
    // Set the NPC to cell 0, 0
    mNpc.transform.position = 
      mMazeGenerator.mMazeCells[0, 0].transform.position;
    mNpc.gameObject.SetActive(true);
    mNpc.Init();
  }
Code language: C# (cs)

We then add the method to do raycast and select the destination cell. Once we find a destination cell, we set the position of the destination game object to the selected cell and show it.

We also add the destination cell’s position as a waypoint for the NPC to move.

  void RayCastAndSetDestination()
  {
    // disable picking if we hit the UI.
    if (EventSystem.current.IsPointerOverGameObject() || 
      enabled == false)
    {
      return;
    }
    Vector2 rayPos = new Vector2(
        Camera.main.ScreenToWorldPoint(Input.mousePosition).x,
        Camera.main.ScreenToWorldPoint(Input.mousePosition).y);
    RaycastHit2D hit = Physics2D.Raycast(
      rayPos, 
      Vector2.zero, 
      0f);
    if (hit)
    {
      GameObject obj = hit.transform.gameObject;
      MazeCell mazeCell = obj.GetComponent<MazeCell>();
      if (mazeCell == null) return;
      Vector3 pos = mDestination.position;
      pos.x = mazeCell.transform.position.x;
      pos.y = mazeCell.transform.position.y;
      mDestination.position = pos;
      mStart = mGoal;
      mGoal = mazeCell.Cell;
      mNpc.AddWayPoint(
        new Vector2(
          obj.transform.position.x, 
          obj.transform.position.y));
      // finally show the destination game object.
      mDestination.gameObject.SetActive(true);
    }
  }
Code language: JavaScript (javascript)

Go to Unity editor and associate the public fields of MazePathfinder script as shown below.

Click Play and run the application. You should see the maze generation taking place. After the maze generation is complete, you will see the NPC on the bottom left cell of the maze. Now you can left-click anywhere in the maze, and you should see that the NPC will move to the destination cell.

Of course, since we did not implement Pathfinding yet, the NPC directly moves to the destination cell without knowing anything about the walls.

The Final Showdown

We have implemented all necessary scaffolds for us to integrate the Pathfinder now. Double-click and open the MazePathfinder script file.

Add the below-highlighted variables.

  public Transform mDestination;
  public NPC mNpc;
  public MazeGenerator mMazeGenerator;

  // The start and the goal cells.
  private Cell mStart;
  private Cell mGoal;

  // Pathfinding related variables.
  LineRenderer mPathViz;
  AStarPathFinder<Vector2Int> mPathFinder = 
    new AStarPathFinder<Vector2Int>();
Code language: C# (cs)

Don’t forget to add “using GameAI.PathFinding” at the top of the file, as we have put all the pathfinding related core classes under the namespace GameAI.PathFinding.

Amend the coroutine with the following highlighted code.

  IEnumerator Coroutine_WaitForMazeGeneration()
  {
    while (!mMazeGenerator.MazeGenerationCompleted)
      yield return null;

    // set the start cell to cell 0, 0.
    mStart = mMazeGenerator.mMazeCells[0, 0].Cell;
    mGoal = mStart;

    // maze generation completed.
    // Set the NPC to cell 0, 0
    mNpc.transform.position = 
      mMazeGenerator.mMazeCells[0, 0].transform.position;

    mNpc.gameObject.SetActive(true);
    mNpc.Init();

    // create the line renderer to show the path.
    // We create a line renderer to show the path.
    LineRenderer lr = mNpc.gameObject.AddComponent<LineRenderer>();
    lr.startWidth = 0.1f;
    lr.endWidth = 0.1f;
    lr.startColor = Color.magenta;
    lr.endColor = Color.magenta;

    mPathViz = lr;

    // set the pathfinder cost functions.
    mPathFinder.HeuristicCost = GetManhattanCost;
    mPathFinder.NodeTraversalCost = GetEuclideanCost;
  }
Code language: C# (cs)

In the highlighted sections, we create a line renderer component. We will use this line renderer to show the final path generated by our Pathfinder.

In the last two lines, we set the cost functions to our Pathfinder. We have not yet implemented these two functions. The following section shows the implementation of these functions.

  public float GetManhattanCost(
  Vector2Int a,
  Vector2Int b)
  {
    return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
  }
  public float GetEuclideanCost(
    Vector2Int a,
    Vector2Int b)
  {
    return GetCostBetweenTwoCells(a, b);
  }
  public float GetCostBetweenTwoCells(
    Vector2Int a,
    Vector2Int b)
  {
    return (mMazeGenerator.mMazeCells[a.x, a.y].transform.position -
      mMazeGenerator.mMazeCells[b.x, b.y].transform.position).magnitude;
  }
Code language: C# (cs)

Next, we implement the function FindPath.

  public void FindPath()
  {
    mPathFinder.Initialize(mStart, mGoal);
    StartCoroutine(Coroutine_FindPathSteps());
    // reset the line.
    mPathViz.positionCount = 0;
  }Code language: JavaScript (javascript)

The above function calls a coroutine Coroutine_FindPathSteps and then resets the line renderer for a new line.

Then we implement the Coroutine_FindPathSteps.

  IEnumerator Coroutine_FindPathSteps()
  {
    while (mPathFinder.Status == PathFinderStatus.RUNNING)
    {
      mPathFinder.Step();
      yield return null;
    }
    if (mPathFinder.Status == PathFinderStatus.SUCCESS)
    {
      OnPathFound();
    }
    else if (mPathFinder.Status == PathFinderStatus.FAILURE)
    {
      OnPathNotFound();
    }
  }
Code language: JavaScript (javascript)

The above coroutine keeps calling the Step function of Pathfinder as long as the status for the Pathfinder is RUNNING.

If the pathfinding is a SUCCESS, then we call OnPathFound else, we call OnPathNotFound.

We now implement the OnPathFound and OnPathNotFound functions.

  public void OnPathFound()
  {
    PathFinder<Vector2Int>.PathFinderNode node = null;
    node = mPathFinder.CurrentNode;
    List<Vector3> reverse_positions = new List<Vector3>();
    while (node != null)
    {
      Vector3 pos = mMazeGenerator.mMazeCells[
        node.Location.Value.x,
        node.Location.Value.y].transform.position;
      reverse_positions.Add(pos);
      node = node.Parent;
    }
    LineRenderer lr = mPathViz;
    lr.positionCount = reverse_positions.Count;
    for (int i = reverse_positions.Count - 1; i >= 0; i--)
    {
      Vector3 p = reverse_positions[i];
      mNpc.AddWayPoint(new Vector2(
        p.x,
        p.y));
      lr.SetPosition(i, new Vector3(
        p.x,
        p.y,
        -2.0f));
    }
    // now change the start cell
    // for the pathfinder to current
    // goal.
    mStart = mGoal;
  }
  void OnPathNotFound()
  {
    Debug.Log("Cannot find path to destination");
  }
Code language: PHP (php)

OnPathFound function iterates through the cells and adds the position of the cells to a list. Note that this list holds positions from the goal to the start cells. So, we reverse traverse this list and add the positions to our NPC as waypoints.

We also add the positions to our line renderer to show the path.

Finally, we amend the RayCastAndSetDestination function to enable pathfinding by calling FindPath. Remember to comment off the old code that adds the position to the NPC’s waypoints. I have shown the codes below. The changes are only in the highlighted lines.

  void RayCastAndSetDestination()
  {
    // disable picking if we hit the UI.
    if (EventSystem.current.IsPointerOverGameObject() || 
      enabled == false)
    {
      return;
    }

    Vector2 rayPos = new Vector2(
        Camera.main.ScreenToWorldPoint(Input.mousePosition).x,
        Camera.main.ScreenToWorldPoint(Input.mousePosition).y);

    RaycastHit2D hit = Physics2D.Raycast(
      rayPos, 
      Vector2.zero, 
      0f);

    if (hit)
    {
      GameObject obj = hit.transform.gameObject;
      MazeCell mazeCell = obj.GetComponent<MazeCell>();
      if (mazeCell == null) return;

      Vector3 pos = mDestination.position;
      pos.x = mazeCell.transform.position.x;
      pos.y = mazeCell.transform.position.y;
      mDestination.position = pos;

      mStart = mGoal;
      mGoal = mazeCell.Cell;

      //mNpc.AddWayPoint(
      //  new Vector2(
      //    obj.transform.position.x, 
      //    obj.transform.position.y));

      FindPath();

      // finally show the destination game object.
      mDestination.gameObject.SetActive(true);
    }
  }

Code language: C# (cs)

Our maze should be now pathfinding capable. Click Play and run the application. You shall see pathfinding in action in our maze, as shown below.

Visualise Pathfinding Progress

The below section is optional. We have already implemented pathfinding in a maze. The below paragraphs will show you how you can visualise the pathfinding progress.

We add the following variables to define the colour for various node states during the pathfinding search.

  // Visualising patfinding progress.
  public Color COLOR_WALKABLE = new Color(49 / 255.0f, 77 / 255.0f, 121 / 255.0f, 1.0f);
  public Color COLOR_CURRENT_NODE = new Color(0.5f, 0.4f, 0.1f, 1.0f);
  public Color COLOR_ADD_TO_OPEN_LIST = new Color(0.2f, 0.7f, 0.5f, 1.0f);
  public Color COLOR_ADD_TO_CLOSED_LIST = new Color(0.5f, 0.5f, 0.5f, 1.0f);
  public Color COLOR_ACTUAL_PATH = new Color(0.5f, 0.5f, 0.8f, 1.0f);
Code language: PHP (php)

Next, we set the onChangeCurrentNode, onAddToClosedList and onAddToOpenList delegates to the Pathfinder. Amend the Coroutine_WaitForMazeGeneration and add the following lines towards the end of the function.

    // to show pathfinding progress.
    mPathFinder.onChangeCurrentNode = OnChangeCurrentNode;
    mPathFinder.onAddToClosedList = OnAddToClosedList;
    mPathFinder.onAddToOpenList = OnAddToOpenList;
Code language: JavaScript (javascript)

Then, we implement these functions to change the colour of the cell highlight at each state change.

  public void OnChangeCurrentNode(PathFinder<Vector2Int>.PathFinderNode node)
  {
    int x = node.Location.Value.x;
    int y = node.Location.Value.y;
    MazeCell mazeCell = mMazeGenerator.mMazeCells[x, y];
    mazeCell.SetHighColor(COLOR_CURRENT_NODE);
    mazeCell.SetHighlight(true);
  }
  public void OnAddToOpenList(PathFinder<Vector2Int>.PathFinderNode node)
  {
    int x = node.Location.Value.x;
    int y = node.Location.Value.y;
    MazeCell mazeCell = mMazeGenerator.mMazeCells[x, y];
    mazeCell.SetHighColor(COLOR_ADD_TO_OPEN_LIST);
    mazeCell.SetHighlight(true);
  }
  public void OnAddToClosedList(PathFinder<Vector2Int>.PathFinderNode node)
  {
    int x = node.Location.Value.x;
    int y = node.Location.Value.y;
    MazeCell mazeCell = mMazeGenerator.mMazeCells[x, y];
    mazeCell.SetHighColor(COLOR_ADD_TO_CLOSED_LIST);
    mazeCell.SetHighlight(true);
  }
Code language: JavaScript (javascript)

Finally, we reset the cell colours to default in the FindPath function. Add the following codes towards the end of the FindPath method.

  public void FindPath()
  {
    mPathFinder.Initialize(mStart, mGoal);
    StartCoroutine(Coroutine_FindPathSteps());

    // reset the line.
    mPathViz.positionCount = 0;
    for (int i = 0; i < mMazeGenerator.maze.NumCols; ++i)
    {
      for (int j = 0; j < mMazeGenerator.maze.NumRows; ++j)
      {
        mMazeGenerator.mMazeCells[i, j].SetHighColor(COLOR_WALKABLE);
        mMazeGenerator.mMazeCells[i, j].SetHighlight(false);
      }
    }
  }

Code language: C# (cs)

Then set a colour to the cells that form the final path. This process is the same as the line that shows the path.

Add the highlighted lines of code in the OnPathFound function.

  public void OnPathFound()
  {
    PathFinder<Vector2Int>.PathFinderNode node = null;

    node = mPathFinder.CurrentNode;

    List<Vector3> reverse_positions = new List<Vector3>();

    while (node != null)
    {
      Vector3 pos = mMazeGenerator.mMazeCells[
        node.Location.Value.x,
        node.Location.Value.y].transform.position;
      reverse_positions.Add(pos);
      mMazeGenerator.mMazeCells[
        node.Location.Value.x,
        node.Location.Value.y].SetHighColor(COLOR_ACTUAL_PATH);
      node = node.Parent;
    }

    LineRenderer lr = mPathViz;
    lr.positionCount = reverse_positions.Count;
    for (int i = reverse_positions.Count - 1; i >= 0; i--)
    {
      Vector3 p = reverse_positions[i];
      mNpc.AddWayPoint(new Vector2(
        p.x,
        p.y));

      lr.SetPosition(i, new Vector3(
        p.x,
        p.y,
        -2.0f));
    }

    // now change the start cell
    // for the pathfinder to current
    // goal.
    mStart = mGoal;
  }

Code language: C# (cs)

To view the progress of pathfinding gradually, change the coroutine Coroutine_FindPathSteps from yield return null to yield return new WaitForSeconds(0.1f).

  IEnumerator Coroutine_FindPathSteps()
  {
    while (mPathFinder.Status == PathFinderStatus.RUNNING)
    {
      mPathFinder.Step();
      //yield return null;
      yield return new WaitForSeconds(0.1f);
    }

    if (mPathFinder.Status == PathFinderStatus.SUCCESS)
    {
      OnPathFound();
    }
    else if (mPathFinder.Status == PathFinderStatus.FAILURE)
    {
      OnPathNotFound();
    }
  }

Code language: C# (cs)

Now click Play and run the application. You should see the change in colour of the cells as they are added to the open list, closed list or becomes the current node.

You can do more to visualise by displaying the H, G and F cost onto some text fields. I will leave that to you. I hope that this tutorial has been helpful to you.

Read My Other Tutorials

1. Implement Mazes in Unity2D
2. Reusable Finite State Machine using C++
3. Flocking and Boids Simulation in Unity2D
4. Runtime Depth Sorting of Sprites in a Layer
5. Implement Constant Size Sprite in Unity2D
6. Implement Camera Pan and Zoom Controls in Unity2D
7. Implement Drag and Drop Item in Unity
8. Graph-Based Pathfinding Using C# in Unity
9. 2D Grid-Based Pathfinding Using C# and Unity
10. 8-Puzzle Problem Using A* in C# and Unity
11. Create a Jigsaw Puzzle Game in Unity
12. Implement a Generic Pathfinder in Unity using C#
13. Create a Jigsaw Puzzle Game in Unity
14. Generic Finite State Machine Using C#
15. Implement Bezier Curve using C# in Unity
16. Create a Jigsaw Tile from an Existing Image
17. Create a Jigsaw Board from an Existing Image
18. Solving 8 puzzle problem using A* star search
19. A Configurable Third-Person Camera in Unity
20. Player Controls With Finite State Machine Using C# in Unity
21. Finite State Machine Using C# Delegates in Unity
22. Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
23. Augmented Reality – Fire Effect using Vuforia and Unity
24. Implementing a Finite State Machine Using C# in Unity
25. Solving 8 puzzle problem using A* star search in C++
26. What Are C# Delegates And How To Use Them
27. How to Generate Mazes Using Depth-First Algorithm

Shamim Akhtar

A  committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.

I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor