Introduction

Pathfinding can be a crucial aspect of game development, for example, when you want enemy characters to chase the player and kick their butts defeat them in a challenging and satisfying manner, or when an enemy is supposed to patrol through a series of checkpoints. To achieve this, you need to find a path between two points in the game world. But how do you find a way from one point to another? Well, there are algorithms for this, one of which is the famous A* search algorithm.

The A* search algorithm is a popular choice for this purpose. It not only finds a path between two points (if there is such a path), it finds the shortest path possible. While applying this algorithm to a game with a top-down perspective is straight-forward, it can become a challenge in a side-scrolling platformer scenario.

We will start the series by having a look at the simple case of a top-down game and how the A* algorithm is applied. Later in the series we’ll look into adapting the algorithm such that it also works in a side-scrolling situation.

A* Pathfinding in a top-down game

Let’s assume we have a grid of square tiles and that the character can move freely in 4 directions being up, down, left and right.

The character can go up, down, left and right.

In addition some of the cells are blocked and hence are not walkable by the character which means a path needs to go around those blocked cells. These are typically obstacles such as walls, trees, water, or … pyramids:

A grid with free and blocked cells.

Let’s further assume the character is at a certain position named A on the grid (i.e. in a particular cell or tile) and they need to go to some other position B.

We need to find a path from A to B.

The A* algorithm’s input is basically the grid with all its blocked and non-blocked cells, position A and position B. Its output is the shortest path (if such a path exists) from A to B which is basically a list of cells.

Setting Up the Environment

First, we need to represent our game world in a way that the A* algorithm can process. This involves creating a grid where each cell corresponds to a tile and therefore to a position in the game world. Each cell can be walkable or unwalkable. Here’s a possible implementation in C# for a Cell class - To make it easier to deal with coordinates, we throw a struct Point into the mix and add a property to Cell accordingly:

public struct Point(int x, int y)
{
    public int X = x;
    public int Y = y;
}

public class Cell(int x, int y, bool isWalkable)
{
    public Point Position { get; } = new(x, y);
    public int X => Position.X;
    public int Y => Position.Y;
    public bool IsWalkable { get; } = isWalkable;
}

The properties are pretty much self-explanatory: Position, X, Y and IsWalkable store the cell position in the grid and if the cell is walkable.

Now a grid can simply be represented by a 2-dimensional array of Cell objects. First we create a 2-dimensional array of int, where 0 means walkable and 1 means blocked. That way we can define the game world in a simpler and more concise way:

// 0 = walkable, 1 = blocked
int[,] map = {
        { 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 },
        { 0, 0, 1, 0, 1, 1, 1, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0, 1, 0, 1, 1 },
        { 1, 1, 1, 1, 0, 1, 1, 0, 1, 0 },
        { 0, 0, 0, 0, 0, 1, 1, 0, 1, 0 },
        { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
    };

We then turn this into an array of Cell objects. Since the first index is the y-coordinate but we’d like it to be the x-coordinate for convenience reasons we need to transpose the map matrix:

var grid = new Cell[map.GetLength(1), map.GetLength(0)];
for (var y = 0; y < map.GetLength(0); y++) {
   for (var x = 0; x < map.GetLength(1); x++) {
       grid[x, y] = new Cell(x, y, isWalkable: map[y, x] == 0);
   }
}

To make sure we don’t end up with Cell objects with invalid coordinates with respect to the grid they’re in, let’s whip up a Grid class with a static constructor which incorporates the transpose magic as well as a method for getting a cell at a certain position following the Try-Parse Pattern:

public class Grid
{
    public required Cell[,] Cells { get; init; }

    private Grid() { }

    public static Grid CreateFromArray(int[,] map)
    {
        var cells = new Cell[map.GetLength(1), map.GetLength(0)];
        for (var y = 0; y < map.GetLength(0); y++) {
            for (var x = 0; x < map.GetLength(1); x++) {
                cells[x, y] = new Cell(x, y, isWalkable: map[y, x] == 0);
            }
        }

        return new Grid { Cells = cells };
    }

    /// <summary>
    /// Try get the cell at the given position
    /// </summary>
    /// <param name="pos">The position to get the cell at from the grid</param>
    /// <param name="cell">The cell at the position if it exists</param>
    /// <returns>true on success, false on failure</returns>
    public bool TryGetCellAtPosition(Point pos, out Cell cell)
    {
        if (pos.X < 0 || pos.X >= Cells.GetLength(0) ||
            pos.Y < 0 || pos.Y >= Cells.GetLength(1)
           ) 
        {
            cell = new Cell(0, 0, false);
            return false;
        }

        cell = Cells[pos.X, pos.Y];
        return true;
    }
}

A* Algorithm Implementation

Now that we have the grid we can move on to the algorithm itself.

The A* algorithm is a generalization and extension of Dijkstra's algorithm. It belongs to the class of so-called informed search algorithms which use an estimation function (heuristic) to search in a targeted way and thus reduce the runtime. The A* algorithm always looks at the cells that are likely to lead quickly to the destination first. To figure out which cell is the best bet, we assign each known cell a cost value based on a metric. This gives us an idea of how long the path from the start to the destination would be in the best case if we used that cell. Then, we look at the cell with the lowest value.

For that we need to extend the Cell class from earlier:

public class Cell(int x, int y, bool isWalkable)
{
    public Point Position { get; } = new(x, y);
    public int X => Position.X;
    public int Y => Position.Y;
    public bool IsWalkable { get; } = isWalkable;
    public float CostToTarget { get; set; } = float.PositiveInfinity;
    public float CostFromStart { get; set; } = float.PositiveInfinity;
    public Cell? Parent { get; set; }
}

Let’s have a brief look at the added properties.

  • We already looked at isWalkable as well as X, Y and Position.
  • CostFromStart is the cost (in our case cost is the same as distance) from the start cell to this cell. It’s initialized with float.PositiveInfinity, because we don’t know the distance yet.
  • CostToTarget is the heuristic estimated cost (or distance) of the path from the start cell to the target cell passing through this cell. This is also initialized with float.PositiveInfinity.
  • Parent is used to track from which cell we came from. This is later used to reconstruct the path.

Here’s the core of the A* pathfinding algorithm. We assume the cost for going from one cell to an adjacent cell is 1. What the algorithm basically does is the following:

  1. Initialization: Set the starting cell’s cost to reach itself (CostFromStart) to 0 and add it to openSet, a set of cells to evaluate.
  2. Main Loop: Run while openSet has cells. Get the cell with the lowest estimated cost from the start to the target via that cell (CostToTarget) from openSet.
  3. Check for Target: If this cell is the target, then we’ve found the path and the algorithm stops.
  4. Process Neighbors: Otherwise, for each neighbor of the cell calculate the cost to reach the cell plus one (tentativeCost). If it’s is less than the neighbor’s current cost (which is +∞ for all cells initially), then we’ve found a shorter path to the neighbor. Set the neighbor’s CostFromStart = tentativeCost and CostToTarget = tentativeCost + GetDistance(n, target), and update its parent cell. Then add the neighbor to openSet if not already present.
  5. Repeat until the target is found or openSet is empty in which case the target isn’t reachable and thus there is no path.

What is the GetDistance(n, target) method in step 4 above? This is the so-called heuristic whose purpose is to estimate the distance between the current cell and the target. The typical choice in a case like ours is the Manhattan distance. The Manhattan distance between two points in a grid is basically the sum of the absolute differences of their coordinates:

Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y)

It’s also known as the Taxicab distance, because it represents the shortest path a taxi would take in a city with a rectangular grid of streets. Unlike Euclidean distance, it only considers horizontal and vertical movements, not diagonal ones.

Here’s a flowchart visualizing the algorithm:

A flowchart showing the algorithm

And here’s an implementation of the algorithm outlined above:

public class AStarPathfinder
{
    public List<Cell> FindPath(Point startPos, Point targetPos, Grid grid)
    {
        // If startPos or targetPos is out of bounds, return an empty path
        if (!grid.TryGetCellAtPosition(startPos, out var start)) return [];
        if (!grid.TryGetCellAtPosition(targetPos, out var target)) return [];

        start.CostFromStart = 0;
        start.CostToTarget = GetDistance(start, target);

        List<Cell> openSet = [start];
        while (openSet.Count > 0) {
            var current = openSet.OrderBy(c => c.CostToTarget).First();
            if (current == target) return ReconstructPath(current);

            openSet.Remove(current);

            var tentativeCost = current.CostFromStart + 1;
            foreach (var n in Neighbors(current, grid.Cells)
                         .Where(n => tentativeCost < n.CostFromStart)) {
                n.Parent = current;
                n.CostFromStart = tentativeCost;
                n.CostToTarget = tentativeCost + GetDistance(n, target);
                if (!openSet.Contains(n)) openSet.Add(n);
            }
        }

        return [];
    }

    private static List<Cell> ReconstructPath(Cell current)
    {
        List<Cell> path = [current];

        var walkingCell = current;
        while (walkingCell.Parent != null) {
            path.Insert(0, walkingCell.Parent);
            walkingCell = walkingCell.Parent;
        }

        return path;
    }

    private static float GetDistance(Cell a, Cell b)
    {
        return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
    }

    private static List<Cell> Neighbors(Cell cell, Cell[,] grid)
    {
        List<Cell> neighbors = [];

        int[] dx = [-1, 1, 0, 0];
        int[] dy = [0, 0, -1, 1];

        for (var i = 0; i < 4; i++) {
            var checkX = cell.X + dx[i];
            var checkY = cell.Y + dy[i];

            if (checkX >= 0
                && checkX < grid.GetLength(0)
                && checkY >= 0
                && checkY < grid.GetLength(1)
                && grid[checkX, checkY].IsWalkable
               ) {
                neighbors.Add(grid[checkX, checkY]);
            }
        }

        return neighbors;
    }
}

Example Grid Setup

Let’s put everything together and whip up a console program with our example grid:

public static class Program
{
    public static void Main(string[] _)
    {
        int[,] map = {
            { 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 },
            { 0, 0, 1, 0, 1, 1, 1, 0, 0, 0 },
            { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 1, 0, 0, 0, 0, 1, 0, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 0, 1, 0 },
            { 0, 0, 0, 0, 0, 1, 1, 0, 1, 0 },
            { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
        };

        var grid = Grid.CreateFromArray(map);

        var pathFinder = new AStarPathfinder();
        var path = pathFinder.FindPath(new Point(1, 1), new Point(4, 2), grid);
        if (path.Count == 0) {
            System.Console.WriteLine("No path found!");
            return;
        }

        System.Console.OutputEncoding = System.Text.Encoding.UTF8;
        System.Console.WriteLine("Path found:");
        System.Console.WriteLine(StringFromPath(path));
    }

    private static string StringFromPath(IEnumerable<Cell> path)
    {
        var steps = path.Select(cell => $"[{cell.X},{cell.Y}]").ToList();
        return string.Join("\u2192", steps);
    }
}

When we start this program it will calculate the path from start to target and print it to the console:

Path found:
[1,1]→[1,2]→[1,3]→[1,4]→[2,4]→[3,4]→[4,4]→[5,4]→[6,4]→
[7,4]→[8,4]→[8,3]→[8,2]→[7,2]→[6,2]→[5,2]→[4,2]

Note

By the way, you can find all of the above code at GitHub.

Here is the path visualized (the upper left cell’s coordinates are (0, 0)):

A pathfinding diagram showing a grid with green cells representing a path.

Bonus: Interactive Example

Let’s take the algorithm outlined above and assemble an app that lets you watch the A* algorithm at work:

Click to load app

The interactive example lets you step through the algorithm step by step or watch it do its work. You can also manipulate the grid by changing cells to be free or blocked.

Walkthrough

Note

When we say “click” we also mean “touch” interactions on touchscreen devices. You can use both mouse clicks and touch events to interact with the app.

When you load the app, you see the same map with cells and obstacles as before. Below the map there are a few buttons:


  • Play/Stop: When first clicked, the algorithm will automatically run at a relatively slow pace so you can watch it in all its beauty; when clicked again, it will stop.
  • Step: Click to execute a single step of the algorithm.
  • Reset: Click to reset the algorithm.

  • Show/Hide Parent: When switched on, shows the relationship of the cells to their parent cells.

You can even manipulate the cells:

  • Click and hold the start cell (A) or target cell (B) to move them around.
  • Click and hold a free or a blocked cell to “paint” or “erase” walls.

When the algorithm is running, the cells change color:

  • Orange: These cells are in the openSet and are about to be examined.
  • Yellow: These cells have their parent cell set.
  • Green: These cells are part of the path from A to B.

Additionally, cells that are being checked by the algorithm display two numbers. The first number in the upper left corner displays the cost from the start cell to this cell. The second number below shows the estimated cost from the start to the destination via that cell.

Example: The cost from the start to this cell is 7, and the estimated cost from the start to the target via this cell is 10.

A note about the example application

The application is made with KNI, a MonoGame derivative with support for WebGL. This may be overkill for the task at hand, but I always wanted to try KNI and its WebGL capabilities, and this seemed like a small enough project to give it a try.

Conclusion

In this article, we looked at the basics of using A* pathfinding in a 2D top-down game. We set out the basics of how the A* algorithm can find the shortest path between two points on a grid. Next, we’ll look at how to apply A* pathfinding in a 2D side-scrolling platformer. This will involve adapting the algorithm to account for additional challenges like gravity.

Resources