Blog

The purpose of this tutorial is to add A* pathfinding to Scavengers 2, the Unity 2D roguelike example.

The 2D roguelike project is the basis upon which this tutorial is built, and is required to follow through. If you’re unfamiliar with the project, you can follow the tutorial. Make sure you have it imported into a project.

You will also need my modified code for the A* pathfinding can be found here. The A* code is a modified version of the code that can be found here.

If you have played Scavengers 2, you may have noticed the enemies are quite stupid. Here is the code governing the enemy movements, in Enemy.cs:

public void MoveEnemy ()
{
    int xDir = 0;
    int yDir = 0;

    if(Mathf.Abs (target.position.x - transform.position.x) < float.Epsilon)

    yDir = target.position.y > transform.position.y ? 1 : -1;

    else
    xDir = target.position.x > transform.position.x ? 1 : -1;

    AttemptMove <Player> (xDir, yDir);
}

As you can see from this code, the enemy checks if the player is in the same column. If it is, then it will move up or down towards the player. If it isn’t, it will move left or right towards the player.
In case the player is 4 down and 1 to the left of the enemy, and to the left of the enemy is a wall, the enemy will not move, as it will attempt to move left, fail due to the wall, and end its movement.

Now there are many ways to improve this logic, a simple one would be to try and move down in the event that left is blocked, but in that case the enemy still wouldn’t move if there was another wall right below it. We would really prefer if the enemy moved around the wall even in that position. Here is where A* can help. A* will find the shortest path from the enemy to the player, and walk that way.

The method I present here is not ideal. I will be using a lot of linecasts in order to find a good path. This is computationally intensive. However, this is also the easiest way to add A* pathfinding to Scavengers 2, with the least modifications to the project.

The ideal way would be to record the position of every entity and wall, and then check the new positions against a record rather than line casting.

The files are:
AStar.cs – The core logic of the pathfinding, and the class you call to start.
AStarNode.cs – Define the core of a path node, extend if you want to implement 3D pathfinding for example.
AStarNode2D.cs – The 2D implementation of AStarNode.cs.
AStarCost.cs – A base class to calculate cost of moving between two points and if it is at all possible, extend this if you want a different way to use a different method of checking for passable nodes. The aforementioned recorded positions, rather than linecasting, for example.
LineCastAStarCost.cs – A raycast implementation of checking if a position is accessible.
Heap.cs – A heap data structure, generic and unrelated to pathfinding.
SpaceConstants.cs – The constant cost of orthogonal and diagonal movements.

I will not go over the entire code, but rather only go over important parts. I encourage you to read over the entire code on your own.

AStar.cs has two methods you should pay attention to:

public void findPath () {
    openList.Add (startNode);
    while (openList.Count > 0) {
        AStarNode current = (AStarNode)openList.Pop();
        if (current.isGoal()) {
            recordSolution(current);
            break;
        }
        processSuccessors(current.getSuccessors());
        closedList.Add (current);
    }
}

This method manages the opened and closed lists using the heap. It iterates over the open list, and calls getSuccessors, which essentially populates all the nodes you can move to from that node. If the node has reached the goal, then the solution has been found.
The heap is sorted by the heuristic cost of the nodes, the heuristic cost is the cost of reaching the point of the node so far, plus the distance to the goal. This way we explore the node with the best potential first.
The cost calculation can be found in AStarNode2D.cs CalculateGlobalCost(). In the case of no diagonal movement, the calculation is manhattan distance:

return Mathf.Abs(xd) + Mathf.Abs(yd);

And in the case of diagonal movement, we use euclidian distance:

return Mathf.Sqrt((xd*xd) + (yd*yd));

The original author recommended a different method of calculating diagonal distance:

return Mathf.Max(Mathf.Abs(xd),Mathf.Abs(yd))*10;

But honestly, I don’t understand it. It is commented out in the code, feel free to test it.

The closed list is a list of all the nodes that already has children. A node in the closed list does not need to be iterated over again. A node in the open list needs to be iterated over.

private void processSuccessors(List<AStarNode> successors) {
    foreach (AStarNode successor in successors) {

        AStarNode nodeOpen = getFromHeap(successor, openList);
        if (successorWorseThanExisting(successor, nodeOpen)) {
            continue; //Throw away
        }

        AStarNode nodeClosed = getFromHeap(successor, closedList);
        if (successorWorseThanExisting(successor, nodeClosed)) {
            continue; //Throw away
        }

        openList.Remove (nodeOpen);

        closedList.Remove (nodeClosed);

        openList.Add (successor);
    }
}

This method is called after the children nodes are added to the node. If you allow only orthogonal move, that would be up, down, left and right. The method will iterate over all successor nodes of a node and getFromHeap any node that represents the same position as the current successor (means that it was reached through a different path). If the cost of reaching that point is worse than the current successor, we throw the current successor away. If the current successor is better, then we remove the old identical nodes from both lists, and add the current one to the open heap, so we can explore it further.

Next I’d like to go over LineCastAStarCost.cs, since this is where some of the scavengers 2 specific code happens, and you’d want to write your own AStarCost in your projects.

public override float getCost(int toX, int toY, int fromX, int fromY)
{
    if (toX != fromX && toY != fromY)
    {
    //Diagonal, so check if can move in both orthogonal directions.
        if (isPassable(toX,fromY,fromX,fromY) && isPassable(fromX, toY, fromX, fromY))
        {
            return SpaceConstants.GRID_DIAG;
        }
    }
    else if (isPassable(toX,toY,fromX,fromY))
    {
        return 1;
    }
    return -1;
}

This method is fairly generic. In case of diagonal movement (movement in both X and Y), we check to see if a movement only in X and only in Y is possible. This is very dependent on the game. In some games, you would want to allow diagonal movement, even if an adjacent tile is blocked. In others, you may want to force two steps around a corner. The cost of a diagonal move is square root of 2.
If it is not a diagonal move, then simply check if it is possible to move in that direction.
If a move is not possible, return -1.

private bool isPassable(int toX, int toY, int fromX, int fromY)
{
    Vector2 start = new Vector2(fromX, fromY);
    Vector2 end = new Vector2(toX, toY);
    RaycastHit2D hit = Physics2D.Linecast(start, end, _blockingLayer);
    return hit.transform == null;
}

Here you can see the method of testing if the movement is possible. Similarly to how MovingObject.cs does the move check, we’re using a linecast. This is why you will notice later we will disable the enemy and target collider before pathfinding. If we do not disable the enemy collider, no path will be found, as the enemy position will always be unreachable.

Lastly, we would like to make changes to Enemy.cs, in order to use the pathfinding. The method we would like to change, is the method we saw earlier, MoveEnemy(…), that governs the Enemy movement logic.

public void MoveEnemy ()
{
    int currentX = Mathf.RoundToInt(transform.position.x);
    int currentY = Mathf.RoundToInt(transform.position.y);
    GetComponent<BoxCollider2D>().enabled = false;
    target.GetComponent<BoxCollider2D>().enabled = false;
    AStar astar = new AStar(new LineCastAStarCost(blockingLayer), currentX, currentY, Mathf.RoundToInt(target.position.x), Mathf.RoundToInt(target.position.y));
    astar.findPath();
    AStarNode2D nextStep = (AStarNode2D)astar.solution[1];

    //GetComponent<BoxCollider2D>().enabled = true;
    target.GetComponent<BoxCollider2D>().enabled = true;

    int xDir = nextStep.x - currentX;
    int yDir = nextStep.y - currentY;

    AttemptMove <Player> (xDir, yDir);
}

We would like to keep the AttemptMove<Player>(xDir, yDir) at the end, but replace all the rest.
First we would round the position of the enemy to ints. We do not use casts because a 0.999 would be cast down to 0. Then we remember to disable both the collider of the enemy and the collider of the target.
We instantiate a new AStar object, giving it a LineCastAStar, with our blocking layer, a start and and end position for our pathfinding algorithm.
We tell it to find a path, and then simply get the 1 index of the path found. We don’t get 0 index, because that would be the current position of the enemy. In more complex games you may want to make a check here to see if the size of the path is at least 2 before moving, but in Scavengers 2 it is nearly impossible for there to be no path between an Enemy and the player.
Lastly, we subtract the current position of the enemy from the next position, in order to pick a direction to move in.

That’s it, your enemies should now be much smarter, and since they don’t walk into walls, much more predictable.
If you’d like to allow diagonal movement, have a look at AStarNode2D.cs, and simply change allowDiagonal to true. You can also look over the calculateGoalEstimate and GetSuccessors methods to see what changes when you change this boolean.

Again, credit to Sune Trudslev, from which I took the base code, and learned A*.