Verbose A* pathfinding algorithm in C# for Unity3D

We’ve been using this basic Board structure quite a lot lately. It is pretty useful for simple turn-based games!

It comprises a Cell class, a Board class and a basic A* class for pathfinding. Its usage is pretty straightforward in a Unity3D scene, but your code must inherit from it in order to implement specific game logic behaviours.

Basic Cells store their coordinates within the board and implement two methods required by A*: IsWalkable – which returns true if the cell is not an obstacle; and MovementCost, a float between 0 and 1 that represents the cost of traversing a given cell (for instance, walking on mud is harder than walking on a road). Here’s their code:

using UnityEngine;
using System.Collections;

public class Cell : MonoBehaviour {
  public Vector2 coordinates {get; set;}
  public virtual bool IsWalkable() {
    return true;
  }
  public virtual float MovementCost() {
    return 0;
  }
}

They inherit from MonoBehaviour, so they can be added to an empty GameObject to create prefabs from them. Thay way you may add an OnMouseDown event to react to mouse clicks. The Board class may use these prefabs to instantiate Cells in the Unity3D scene, creating a visual board on the scene if they are attached to sprites or cubes.

Boards are a bit more complex. They require a public GameObject cellPrefab, store their own with and height and an array of Cells. Plus, they could listen to the OnCellClicked event and raise their own OnCellChosen event, which should be used in your game to react to clicks on cells (the game logic should decide what to do with them). We are not adding that, for simplicity.

They also inherit from MonoBehaviour. When attached to a GameObject one can edit their size in the inspector. When the scene is launched, Boards will create a visual representation, instantiating with x height Cell prefabs. This works best when the cell prefab is a 1×1 square (or 1x1x1 cube), so that cell positions in space coincide with their coordinates in the board.

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class Board: MonoBehaviour {
  public int width;
  public int height;
  public GameObject cellPrefab;
  Cell [,]board;

  void Awake() {
    CreateBoard ();
  }

  void CreateBoard() {
    board = new Cell[width,height];
    for (int i = 0; i < height; i++)
      for (int j = 0; j < width; j++) {
	GameObject cell = GameObject.Instantiate(
	  cellPrefab,
	  new Vector3(j, i, 0),
	  Quaternion.identity) as GameObject;
	cell.transform.parent = transform;
	Cell c = cell.GetComponent<Cell>();
	c.coordinates = new Vector2(j, i);
	board[j,i] = c;
      }
  }

  protected List<Cell> FindPath(Cell origin, Cell goal) {
    AStar pathFinder = new AStar();
    pathFinder.FindPath (origin, goal, board, false);
    return pathFinder.CellsFromPath ();
  }
}

The FindPath method returns a list of Cells, from an origin to a goal, avoiding obstacles. In this case we use A* (AStar), but any other method can be used.

Our A* algorithm is quite verbose, which makes it suitable for learning purposes. I won’t explain it here – yes, I know, it’s suitable for learing purposes, but it has already been described lots of times! Have a look in Wikipedia if you want to learn more about this solution.

The AStar class does not inherit from MonoBehaviour, so the Node subclass and many functions use two integers to map a coordinate. But the Node subclass contains a Cell! This way the algorithm is able to return both the list of coordinates and the list of Cells that conform the path. You’ll find the two lists A* uses to find the best solution: openList and closeList, a list of neighbours to explore and the final path.

Our A* was created for a square grid, considering just four neighbours. Feel free to change FindValidFourNeighbours to include diagonals or even to apply this algorithm to a hexagonal grid.

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class AStar {
  
  class Node {
    public int x;
    public int y;
    public float G;
    public float H;
    public float F;
    public Node parent;
    public Cell cell;
    public Node (int x, int y, float G, float F, float H, Node parent, Cell c) {
      this.x = x;
      this.y = y;
      this.G = G;
      this.H = H;
      this.F = F;
      this.parent = parent;
      this.cell = c;
    }
  }
  
  List<Node> openList;
  List<Node> closeList;
  List<Node> neighbours;
  List<Node> finalPath;
  Node start;
  Node end;

  Cell[,] map;
  int mapWidth;
  int mapHeight;
  
  public AStar () {
    openList = new List<Node>();
    closeList = new List<Node>();
    neighbours = new List<Node>();
    finalPath = new List<Node>();
  }
  
  public void FindPath(Cell startCell, Cell goalCell, Cell[,] map, bool targetCellMustBeFree) {
    this.map = map;
    this.mapWidth = map.GetLength(0);
    this.mapHeight = map.GetLength(1);
    
    start = new Node((int)startCell.coordinates.x, (int)startCell.coordinates.y, 0, 0, 0, null, startCell);
    end = new Node((int)goalCell.coordinates.x, (int)goalCell.coordinates.y, 0, 0, 0, null, goalCell);
    openList.Add(start);
    bool keepSearching = true;
    bool pathExists = true;
    
    while ((keepSearching) && (pathExists)) {
      Node currentNode = ExtractBestNodeFromOpenList();
      if (currentNode == null) {
        pathExists = false;
        break;
      }
      closeList.Add(currentNode);
      if (NodeIsGoal(currentNode))
      keepSearching = false;
      else {
        if (targetCellMustBeFree)
        FindValidFourNeighbours(currentNode);
        else
        FindValidFourNeighboursIgnoreTargetCell(currentNode);

        foreach (Node neighbour in neighbours) {
          if (FindInCloseList(neighbour) != null)
          continue;
          Node inOpenList = FindInOpenList(neighbour);
          if (inOpenList == null) {
            openList.Add (neighbour);
          }
          else {
            if (neighbour.G < inOpenList.G) {
              inOpenList.G = neighbour.G;
              inOpenList.F = inOpenList.G + inOpenList.H;
              inOpenList.parent = currentNode;
            }
          }   
        }
      }
    }
    
    if (pathExists) {
      Node n = FindInCloseList(end);
      while (n != null) {
        finalPath.Add (n);
        n = n.parent;
      }
    }
  }

  public List<int> PointsFromPath() {
    List<int> points = new List<int>();
    foreach (Node n in finalPath) {
      points.Add (n.x);
      points.Add (n.y);   
    }
    return points;
  }
  
  public List<Cell> CellsFromPath() {
    List<Cell> path = new List<Cell> ();
    foreach (Node n in finalPath) {
      path.Add(n.cell);   
    }

    if (path.Count != 0) {
      path.Reverse ();
      path.RemoveAt(0);
    }
    return path;
  }
  
  Node ExtractBestNodeFromOpenList() {
    float minF = float.MaxValue;
    Node bestOne = null;
    foreach (Node n in openList) {
      if (n.F < minF) {
        minF = n.F;
        bestOne = n;
      }
    }
    if (bestOne != null)
    openList.Remove(bestOne);
    return bestOne;
  }
  
  bool NodeIsGoal(Node node) {
    return ((node.x == end.x) && (node.y == end.y));
  }
  
  void FindValidFourNeighbours(Node n) {
    neighbours.Clear();
    if ((n.y-1 >= 0) && ((map[n.x, n.y-1].IsWalkable()))) {
      Node vn = PrepareNewNodeFrom(n, 0, -1);
      neighbours.Add (vn);
    }
    if ((n.y+1 <= mapHeight-1) && ((map[n.x, n.y+1].IsWalkable()))) {
      Node vn = PrepareNewNodeFrom(n, 0, +1);
      neighbours.Add (vn);
    }
    if ((n.x-1 >= 0) && ((map[n.x-1, n.y].IsWalkable()))){
      Node vn = PrepareNewNodeFrom(n, -1, 0);
      neighbours.Add (vn);
    }
    if ((n.x+1 <= mapWidth-1) && ((map[n.x+1, n.y].IsWalkable()))){
      Node vn = PrepareNewNodeFrom(n, 1, 0);
      neighbours.Add (vn);
    }
  }

  /* Last cell does not need to be walkable in the farm game */
  void FindValidFourNeighboursIgnoreTargetCell(Node n) {
    neighbours.Clear();
    if ((n.y-1 >= 0) && ((map[n.x, n.y-1].IsWalkable()) || map[n.x, n.y-1] == end.cell)) {
      Node vn = PrepareNewNodeFrom(n, 0, -1);
      neighbours.Add (vn);
    }
    if ((n.y+1 <= mapHeight-1) && ((map[n.x, n.y+1].IsWalkable()) || map[n.x, n.y+1] == end.cell)) {
      Node vn = PrepareNewNodeFrom(n, 0, +1);
      neighbours.Add (vn);
    }
    if ((n.x-1 >= 0) && ((map[n.x-1, n.y].IsWalkable()) || map[n.x-1, n.y] == end.cell)){
      Node vn = PrepareNewNodeFrom(n, -1, 0);
      neighbours.Add (vn);
    }
    if ((n.x+1 <= mapWidth-1) && ((map[n.x+1, n.y].IsWalkable()) || map[n.x+1, n.y] == end.cell)){
      Node vn = PrepareNewNodeFrom(n, 1, 0);
      neighbours.Add (vn);
    }
  }
  
  Node PrepareNewNodeFrom(Node n, int x, int y) {
    Node newNode = new Node(n.x + x, n.y + y, 0, 0, 0, n, map[n.x + x, n.y + y]);
    newNode.G = n.G + MovementCost(n, newNode);
    newNode.H = Heuristic(newNode);
    newNode.F = newNode.G + newNode.H;
    newNode.parent = n;
    return newNode;
  }
  
  float Heuristic (Node n) {
    return Mathf.Sqrt((n.x - end.x)*(n.x - end.x) + (n.y - end.y)*(n.y - end.y));
  }
  
  float MovementCost(Node a, Node b) {
    return map [b.x, b.y].MovementCost ();
  }
  
  Node FindInCloseList(Node n) {
    foreach (Node nn in closeList) {
      if ((nn.x == n.x) && (nn.y == n.y))
      return nn;
    }
    return null;
  }
  
  Node FindInOpenList(Node n) {
    foreach (Node nn in openList) {
      if ((nn.x == n.x) && (nn.y == n.y))
      return nn;
    }
    return null;
  }
}

That’s it! Not too complex, is it? The thing is that most of these methods should be invoked from inheriting classes, those that are specific to the game they are used in. For instance, one would receive a OnCellClicked event on the inherited Board whenever a cell is clicked, decide that the hero should walk to the clicked cell, call FindPath(heroCurrentCell, clickedCell), traverse its cells and animate hero’s movement somehow. That’s a different story, but I’m sure you’ll be able to make the most of these three classes.

Enjoy!