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!

Roulette wheel selection for procedural content generation

There are times when you need to give your code the ability to choose among many options that have different frequencies or probabilities of being selected. Whether you need to create a random power-up or decide the next enemy encounter, here’s a tool that you will find useful: the Roulette Wheel selection algorithm, or Fitness Proportionate Selection. While it is a common operator in Genetic Algorithms, it is also very handy for videogame programmers!

First of all, an example

In Sound Juggler, the Roulette Wheel selection algorithm was used to choose which powerup would appear next. There were seven of them: three were ‘good’, three were ‘bad’ and one caused ‘sudden death’. Initially, all of them have the same probability of being chosen except for the sudden death one, which is quite rare (See Fig. 1.a, where probabilities are represented as icon sizes). However, as the game continues, negative powerups (in red) become increasingly more frequent (Fig. 1.b-1.c).  With Roulette Wheel selection, choosing the next powerup is really easy.

As the game advances, powerup probabilities change (size is proportional to probability)

Size does matter

Quoting Wikipedia: “The analogy to a roulette wheel can be envisaged by imagining a roulette wheel in which each candidate solution represents a pocket on the wheel; the size of the pockets are proportionate to the probability of selection of the solution.”

On a given wheel all pockets may have equal size and thus equal probability of being chosen: 1 / n, being n the number of pockets (see the left roulette in Fig.2).  Now, imagine that one of the pockets occupies half the space (right roulette in Fig.2). It is easy to see that the roulette will stop inside it many more times than in any other pocket. Statistically, its probability is exactly 0.5, although you don’t really need to know it if you understand how this works.

In the left wheel, all pockets have the same size. In the right wheel, the orange pocket is seven times bigger than any other pocket (and thus, seven times more probable!)

So, whenever you have a set of choices with different probabilities, you simply have to assign them the right pocket size and spin the wheel!  Of course, the algorithm does not use a ‘wheel’ per se.

Programming the Roulette

We will use Unity Script, which is similar to Javascript. First of all, we need a roulette, a place to store probabilities. It will be defined by an array of floats.

var roulette: float[];

Then we initialize it with each pocket probability. Say we have four items to be chosen. If they are equiprobable, our roulette should look like this:

roulette = new float[4];
roulette[0] = 1.0;
roulette[1] = 1.0;
roulette[2] = 1.0;
roulette[3] = 1.0;

Ok, we call them ‘probabilities’ although they do not sum 1.0. We could simply normalize values dividing each one by the sum of all of them. But we can ignore that part safely.

Now, if we wanted the first item to be two times more probable than any other, we simply have to set values this way:

roulette = new float[4];
roulette[0] = 2.0; <-- 2.0 / 5.0 = 0.4
roulette[1] = 1.0; <-- 1.0 / 5.0 = 0.2
roulette[2] = 1.0;
roulette[3] = 1.0;

Easy! See how it works? Those numbers can be understood as the region that each pocket occupies in the roulette. The first pocket is two times bigger than any other, increasing its probability of being chosen. Now, how do we spin the wheel? First of all, we sum all pocket values:

var total : float = 0;
var i : int = 0;
for (i = 0; i < roulette.length; i++)
    total = total + roulette[i];

Done. Then, we chose a random number between 0 and total.

var goal_value: float = Random.Range(0, total);

Why? Well, here’s the tricky part.  In order to choose a pocket, we traverse the roulette accumulating pocket values. When this accumulated value is greater than our random goal_value, we have our pocket!

var sum : float = 0;
for (i = 0; i <= roulette.length-1; i++) {
   sum += fortune_wheel[i];
   if (sum > goal_value)
   break;
}

And that’s it! After that last for loop, i contains the index of the chosen pocket. Then it’s up to you what to do with it. In Sound Juggler, we used it to choose the next powerup (note that you can alter roulette values whenever you want). In our next game, Oddy Smog’s Misadventure, we use it to select which gear will be placed next (however, not all gears are available at the beginning, so we traverse our roulette from zero to the last allowed gear index).

Choosing the right values

That’s the best part of this algorithm. If you want to sit down and use your knowledge of statistics, you can do it. But if you just want those pesky kobolds to appear inside the Huge Caverns of Dispair five times more frequently than goblins, and the black dragon to be seen around once in a month, you can simply play with numbers until you feel comfortable with results. Graphically, it would look like Fig.3.

Dwellers of the Huge Cavern of Dispair. Kobolds are everywhere!

Our code would look like this:

roulette = new float[3];
roulette[KOBOLDS] = 50;
roulette[GOBLINS] = 10;
roulette[BLACKDRAGON] = 1;

In this case, total would sum 61. Most of the time, a random number between 0 and 61 will fall between 0 and 50, and thus a new Kobold will be spawned. But, from time to time, a Dragon will appear to spice up the game. And feast on your corpse.

Use with caution! 🙂