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!

18 thoughts on “Verbose A* pathfinding algorithm in C# for Unity3D

  1. Harry January 9, 2015 / 1:07 pm

    Hi, I think your script is great, its simple, just like I wanted to.

    But… when I implemented it on Unity 4.6.0, the List class return error
    “The type or namespace name `List’ could not be found. Are you missing a using directive or an assembly reference?”

    I’ve make sure, the script use the “using System.Collections.Generic;” but it still return error
    do you have any idea?

    thanks!

    • LuisAnton January 9, 2015 / 4:22 pm

      He… The thing is WordPress removed all pieces of code when I copy-pasted it! Change all List to List and it should work (I’ll try to add them, though) 🙂

    • LuisAnton January 9, 2015 / 4:42 pm

      Sorry! I deleted your last comment by mistake 8(

      It’s the damned WordPress editor, that removes ‘html like tags’ with < and > (I’m not even sure you’ll see those)

      I’ve updated the post, now you see what I mean. Lists require a type, but WordPress removed it because it looks like HTML!

  2. Harry January 9, 2015 / 4:58 pm

    Aahh I see,

    many thanks Luis!
    gonna try it soon

    regards

  3. Briggs May 18, 2015 / 4:35 am

    I don’t know if this is a result of updates involved in the newest version of Unity, or just me not knowing how to do…a great many things, really, but I can’t seem to get this working. I’ve copy-pasted each script here shown into a C# script in Unity, to prevent ‘Oh, I miscased that one letter, no wonder it’s not working.’

    The current ‘error’ locations are:

    In Board: Cell c = cell.GetComponent();
    Gives the following error: “The type arguments for method ‘UnityEngine.GameObject.GetComponent’ cannot be inferred from the usage. Try specifying the type arguments explicitly.”

    and, also in Board: pathFinder.FindPath (origin, goal, board);
    Gives the following error: “No overload for method ‘FindPath’ takes ‘3’ arguments.”

    • LuisAnton May 18, 2015 / 3:19 pm

      Thanks a lot for pointing those errors out. So no, it’s not you, no it’s not Unity, it’s WORDPRESS (or, well, the browser), that takes away things between angles <> I thought I’d fixed all of them, but no 🙁 Thanks!

      cell.GetComponent() should be cell.GetComponent<Cell>();

      And we’ve fixed the second error too. It’s a parameter we added in a project, which should be false by default : )

      • Briggs May 18, 2015 / 6:29 pm

        Oh, cool, alright. Thanks for responding – especially so quickly! Plugged those in, and it seems to be working now.

  4. borshu January 29, 2016 / 3:56 am

    could you explain how to add 2 more Neighbours to get it work with hexagons?

    • LuisAnton February 10, 2016 / 8:38 am

      You just have to create a new function that traverses and adds a give hexagon’s neighbours. The use that one instead of the current one, FindValidFourNeighbours, which works on regular grids. How to do that depends on your implementation 😀 We have done something similar on an icosphere on a current project, where triangles just have three neighbours, and A* still works perfectly 🙂

  5. kennel February 2, 2016 / 6:59 pm

    Thank you for this code!

    You can greatly improve performance using Dictionary for _closeList and _openList and using it’s Contains() method for FindInCloseList(). I got something like this:
    _openList = new Dictionary<int, Dictionary>();
    _openListArray = new List();
    _closeList = new Dictionary<int, Dictionary>();

    In my tests it was about 30 times faster.

    • LuisAnton February 10, 2016 / 8:33 am

      Thanks for the tip! We’ll certainly test it 😀

  6. Tony February 20, 2016 / 12:12 pm

    Wonderful code! Works like a charm, and a pleasure to read 🙂
    I can’t thank you enough!

  7. jhice March 18, 2016 / 12:32 pm

    Hi and thanks !

    This is the more compact script I’ve found to use with Unity and managed to implement it correctly 🙂

    One question about shortest path : actually the script doesn’t find the shortest path, wich is not mandatory if I’ve understood the concept ? The “heuristic” seems to be the one in cause to find the shortest path, and in your implementation the heuristic is calculated with the square root, but on the other hand it doesnt use diagonals, as the square root is a diagonal by definition…

    Are you ok with that ? How can we improve the heuristic in that configuration ? (I dont want to use the diagonals either).

    • jhice March 18, 2016 / 12:57 pm

      I’ve done some tests with Manhattan distance and Diagonal distance according to http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

      Manhattan distance is the one we should use here => it gave strange results and follow the borders most of the time !

      In Heuristic (Node n) :

      // Manhattan distance
      float dx = Mathf.Abs(n.x – end.x);
      float dy = Mathf.Abs(n.y – end.y);
      return dx + dy;

      Diagonal distance seems to work better (for short path) than your pure square root, but sometimes not giving the shortest path (anyway I dont want to use diagonals but it gives better results although).

      // Diagonal distance
      float D = 1;
      float D2 = Mathf.Sqrt(2f);
      float d1 = Mathf.Abs(n.x – end.x);
      float d2 = Mathf.Abs(n.y – end.y);
      return (D * (d1 + d2)) + ((D2 – (2f * D)) * Mathf.Min(d1, d2));

      In the game I’m making I dont need absolutely the shortest path so I will go with the square root for now 🙂 Strange behavior of the Manhattan one ! (I used it in javascript and it works nice).

      • LuisAnton March 18, 2016 / 1:14 pm

        Indeed, if you don’t want to consider diagonals then Manhattan is the way to go. 4 neighbours are at distance 1, diagonal neighbours are at 2. I thought this version considered 8 neighbours, but it’s already using the 4 neighbours test – sorry!

      • LuisAnton March 18, 2016 / 1:16 pm

        Diagonal distance is, I guess, Euclidean distance: sqrt (dx*dx + dy*dy + dz*dz) (z if there’s a 3rd dimension) This one produces ‘discs’ instead of ‘diamonds’ if you plot distance values.

        • jhice March 18, 2016 / 2:11 pm

          Thanks for your answers, if I dig much more into this and find something I’ll tell you 😉

    • LuisAnton March 18, 2016 / 1:12 pm

      Thanks! It’s not precisely compact, but hopefully easy to read 😀

      Indeed, A* doesn’t have to find the shortest path, it depends on the heuristic. But if you don’t want to use diagonals simply check 4-neighbours instead of 8. All 4-neighbour distances equal 1 + whatever the heuristic considers to be important – slope, for instance, or dangers of some kind 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *