A* Pathfinding in 2D Games: From Top-Down to Side-View

Introduction

In the last two articles of this series we looked at how the A* search algorithm can be applied to a simple top-down scenario. Now let’s finally look at what needs to change for a side-view platformer game. We will implement an example application in MonoGame / KNI. For this, we will update the code from the last post.

Note

You don’t have to manually copy code snippets around. The complete project is available on GitHub.

What Seems to Be the Problem with Side-View?

First of all, in a typical side-view platformer scenario, gravity is involved, pulling every game object down to the ground. This means that, unlike in a top-down view, a character can’t just keep going up cells until they reach the ceiling. (Unless the character has the ability to fly, of course. But we’re limiting ourselves to humanoid bipeds without wings, or a jetpack, or a magic potion that defies gravity.) The only way to move upwards would be to jump or to climb a ladder. Another limitation is that the character needs ground under their feet to walk sideways.

In summary the following can be said:

There is gravity involved, which limits how a character can move.
The character may or may not have certain capabilities such as walking, jumping, climbing ladders and using hanging bars.
Certain cell types can help the character to overcome specific restrictions, such as ladders and hanging bars with which the character can defy gravity.

Cell Types and Capabilities

We’ll start with the cell types. Before, in the top-down world, we only had two types of cells: free and blocked. Now, in our little side-view world, we have the following four cell types: empty, blocked, ladder and hanging bar. Here’s an example of what this might look like:

Here are the properties of the different cell types:

An empty cell can obviously be occupied by the game character
A block, on the other hand, cannot. The character cannot pass through it.
A ladder can be used to climb up or down
Hanging bars can be used to move sideways

Let’s further assume that the character has the following capabilities:

Walk sideways
Climb ladders up and down and maybe even sideways
Swing along hanging bars
Jump sideways

Furthermore, certain capabilities could be switched on and off. For example, the character might not be able to jump at the beginning. This ability could be unlocked later, e.g. through a power-up.

Walking, Climbing, Swinging (and Falling)

Let’s take a closer look on how we can move without jumping and what that means in terms of neighborhood:

When the cell below is empty, then gravity takes over and the character is pulled down to the ground, which can be interpreted as ’the character can go down a cell if that cell is empty'.

When there is ground below and the laterally adjoining cell is free, a ladder or a hanging bar, the character can walk in that direction.

When the character is on a ladder, they can walk up and down and can also walk to the side, if the respective side is empty (or also a ladder or a hanging bar).

When the character has grabbed the hanging bars, they can move sideways or they can let loose and fall down.

Integrating Jumps

Note

Jumping can be implemented very differently in terms of height, distance, speed, etc. This results in individual jump paths depending on the specific implementation. In addition, jumps of different heights and distances or even double jumps could also be possible. The goal of this article is to explain the basic principle in a simple way, so we’ll keep things as straightforward as possible. It’s even possible that, based on the colliders you’ve implemented, the trajectory we’ve used here, which is a bit idealized, doesn’t allow a jump at all because the character bounces off the edge of a block, for example. We will generously ignore this here and leave it to the reader to find a jump trajectory that works for their use case.

To simplify things a bit, let’s limit the jump capability to the following: the character can jump two cells high and three cells to the side. Here are three example obstacles the character can overcome by jumping:

Jump onto a platform that’s no more than two cells higher.

Jump over a wall that’s no more than two cells high.

Jump over a pit that’s no more than three cells wide.

Looking at the example of a jump over a pit, we can see how the neighboring cells and the costs of reaching them are determined.

Each cell the jump trajectory is going through …

… is considered a neighboring cell which is reachable.

The cost is calculated by applying the accumulated manhattan distance.

If there is a block in the jump trajectory, the jump ends there:

As you can see the number of neighbors is less compared to a “full” jump.

Let’s Code!

Now that we have an idea of how the concept of neighboring cells needs to change, we can cast that in code.

Updating the `Cell` Class

First of all, the Cell class from the last post needs another update. Instead of the walkabilty flag we now need a cell type which will be implemented with an enum:

public enum CellType
{
    Empty,
    Block,
    Ladder,
    HangingBar
}

Here is the first update to the Cell class:

public class Cell(int x, int y, CellType type)
{
    // ...
    
    private CellType _type = type;

    public CellType Type {
        get => _type;
        set {
            if (value == _type) return;
            CellTypeChanged?.Invoke();
            _type = value;
        }
    }
    
    public bool IsEmpty => Type == CellType.Empty;
    public bool IsBlock => Type == CellType.Block;
    public bool IsLadder => Type == CellType.Ladder;
    public bool IsHangingBar => Type == CellType.HangingBar;
    
    public event Action? CellTypeChanged;
}

We added a public property Type for getting and also setting the cell type. Setting of a cell type is going to happen via the level editor. When the cell type changes, we invoke a CellTypeChanged event.

In addition we added a few convenience properties for easily checking if the cell is empty or a block and so on.

Now, let’s take another look at the example diagrams above. You will notice that compared to the simpler top-down case it is no longer sufficient to just look at the cells that are direct neighbors of the current cell. We need a way to traverse through the grid from a specific cell so we’re able to look at a neighbor’s neighbor and then at the neighbor of the neighbor’s neighbor and so on.

Instead of fiddling with the grid in the find-neighbor-logic, we will extend the Cell class even further and add some properties that let us go easily into a certain direction from that cell. The fiddling will then be done and hidden in these properties. For this, the Cell needs to be aware of the Grid it is part of.

public class Cell(int x, int y, CellType type, Grid grid)
{
    // ...

    public Cell? NeighborAt(int deltaX, int deltaY) => grid[X + deltaX, Y + deltaY];

    public Cell? Up => NeighborAt(0, -1);
    public Cell? Down => NeighborAt(0, 1);
    public Cell? Left => NeighborAt(-1, 0);
    public Cell? Right => NeighborAt(1, 0);
    public Cell? DownRight => NeighborAt(1, 1);
    public Cell? DownLeft => NeighborAt(-1, 1);
    public Cell? UpRight => NeighborAt(1, -1);
    public Cell? UpLeft => NeighborAt(-1, -1);
    
    // ...
}

As you can see we added a Grid parameter to the primary constructor. Then, there are a handful of properties for going up, down, left, right, etc. from the cell and get the adjoining cell, if there is one, in the respective direction. If we leave the grid, null is returned.

Updating the `Grid` Class

The Grid class also needs an update. Here is the class boiled down to the changes needed to add support for the new cell types:

public class Grid
{
    // ...
    
    private readonly Cell[,] _cells;

    public event Action? GridChanged;

    public Grid(char[,] map)
    {
        if (map.Length == 0) {
            throw new ArgumentException($"{nameof(map)} must contain at least 1 element");
        }

        _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, CellTypeFromChar(map[y, x]), this);
                _cells[x, y].CellTypeChanged += () => GridChanged?.Invoke();
            }
        }
    }

    private static CellType CellTypeFromChar(char c)
    {
        return c switch {
            ' ' => CellType.Empty,
            'B' => CellType.Block,
            'L' => CellType.Ladder,
            'H' => CellType.HangingBar,
            _ => throw new ArgumentException($"Invalid cell type: {c}")
        };
    }
    
    // ...
}

First of all we got rid of the static constructor CreateFromArray and instead made the constructor public. You’ll also see that the map array now contains chars instead of ints, and we need to map certain characters to certain cell types, which is implemented in CellTypeFromChar. This allows us to instantiate the example grid like so:

public class Pathfinding
{
    // ...
    
    private readonly char[,] _map = {
        { ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', 'B', 'B' },
        { ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'H', 'H', 'L' },
        { ' ', ' ', ' ', ' ', 'B', 'B', 'B', ' ', ' ', 'L' },
        { 'B', 'B', ' ', ' ', ' ', 'B', 'B', ' ', ' ', 'L' },
        { ' ', ' ', ' ', ' ', ' ', 'B', 'B', 'B', 'B', 'L' },
        { ' ', ' ', ' ', 'B', 'B', 'B', 'H', 'H', 'H', 'L' },
        { ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', 'B', 'L' },
        { 'B', 'B', ' ', ' ', ' ', 'B', 'B', ' ', 'B', 'L' },
        { ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', 'L' },
        { ' ', ' ', 'B', 'B', ' ', ' ', ' ', ' ', 'B', 'L' },
        { ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'L' },
        { 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B' }
    };
    private readonly Grid _grid;

    // ...

    public Pathfinding()
    {
        _grid = new Grid(_map) {
            StartPosition = new Point(0, 10),
            TargetPosition = new Point(5, 1)
        };

        // ...
    }

    // ...
}

Updating the Find-Neighbors Logic

Now that we have that out of the way, we can update the logic that finds neighbor cells. Because the find-neighbors code will be a bit more complicated compared to the top-down case, it seems a good idea to put this into its own class. Also, let’s define an interface, because why not (actually, that let’s you easily implement different neighbor finders and also makes unit testing easier, because you can mock the neighbor finder interface):

public interface INeighborFinder
{
    public IEnumerable<CellCostPair> FindNeighbors(Cell cell, bool hasJumpCapability, GetDistanceDelegate getDistance);
    public delegate float GetDistanceDelegate(Cell from, Cell to);
}

The interface contains the following:

A method FindNeighbors which takes the current cell, whether the game character has jump capability, and a delegate with which the distance between two cells can be calculated (which in our case will be the good old manhattan distance).
A delegate called GetDistanceDelegate which takes two cells and returns the distance in between.

You’ll have noticed that FindNeighbors returns an IEnumerable<CellCostPair>. Why not return Cells? Because now, that we’re not only looking at adjoining cells but also at neighbors of neighbors, it seems sensible to calculate the cost to reach a certain neighboring cell right when we’re looking at them, especially in the jumping context. Thus, we create a simple DTO which contains a cell and the cost to reach that cell:

public struct CellCostPair(Cell cell, float cost)
{
    public Cell Cell { get; private set; } = cell;
    public float Cost { get; private set; } = cost;
}

Let’s continue with implementing the FindNeighbors method. This task can be split up into finding neighboring cells reachable with and without jumping.

Cells Reachable without Jumping

Here is how to find cells that are reachable without jumping:

public class NeighborFinder : INeighborFinder
{
    // ...
    
    public IEnumerable<CellCostPair> FindNeighbors(
        Cell sourceCell, 
        bool hasJumpCapability, 
        INeighborFinder.GetDistanceDelegate dist
    )
    {
        foreach (var cell in FindCellsWithoutJumping(sourceCell, dist)) {
            yield return cell;
        }
   
        // ...
    }

    private static IEnumerable<CellCostPair> FindCellsWithoutJumping(
        Cell cell, 
        INeighborFinder.GetDistanceDelegate dist
    )
    {
        if (cell.Down is { IsBlock: false }) {
            var cost = dist(cell, cell.Down);
            yield return new CellCostPair(cell.Down, cost);
        }

        if (cell is { IsLadder: true, Up.IsBlock: false }) {
            var cost = dist(cell, cell.Up);
            yield return new CellCostPair(cell.Up, cost);
        }

        var canMoveSideways = cell.Down is { IsEmpty: false } || cell.IsLadder || cell.IsHangingBar;
        if (!canMoveSideways) yield break;
        
        if (cell.Right is { IsBlock: false }) {
            var cost = dist(cell, cell.Right);
            yield return new CellCostPair(cell.Right, cost);
        }

        if (cell.Left is { IsBlock: false }) {
            var cost = dist(cell, cell.Left);
            yield return new CellCostPair(cell.Left, cost);
        }
    }
    
    // ...
}

A nice thing we can do now is instead of fiddling with grid coordinates, we just use speaking property names like cell.Down, which we can also combine with property patterns to check if certain conditions are met.

The first bit deals with going down one cell. If the cell below isn’t a block then we can descend:

if (cell.Down is { IsBlock: false }) {
    var cost = dist(cell, cell.Down);
    yield return new CellCostPair(cell.Down, cost);
}

The next part handles whether we can go up one cell. If the current cell is a ladder (i.e. we’re standing on a ladder) and there is no block in the cell above, then we can ascend:

if (cell is { IsLadder: true, Up.IsBlock: false }) {
    var cost = dist(cell, cell.Up);
    yield return new CellCostPair(cell.Up, cost);
}

The final sections focus on moving sideways. Here’s how we can determine whether the character can move to the right: If the cell below isn’t empty, we’re on a ladder, or we’re hanging from bars, then we’re able to move sideways. However, if the aforementioned condition isn’t met, then we can stop evaluating more neighbors.

var canMoveSideways = cell.Down is { IsEmpty: false } || cell.IsLadder || cell.IsHangingBar;
if (!canMoveSideways) yield break;

But, if we can move sideways in principle and the cell to the right isn’t a block, we can move one cell to the right:

if (cell.Right is { IsBlock: false }) {
    var cost = dist(cell, cell.Right);
    yield return new CellCostPair(cell.Right, cost);
}

It’s the same in the other direction, just the other way around (no kidding):

if (cell.Left is { IsBlock: false }) {
    var cost = dist(cell, cell.Left);
    yield return new CellCostPair(cell.Left, cost);
}

Now we’re ready to look at how to evaluate additional neighboring cells with jumping incorporated.

Add Jumping to the Mix

Without further ado, here’s the additional code:

public class NeighborFinder : INeighborFinder
{
    private static readonly Point[] JumpRightTrajectoryDeltas = [
        new(0, -1), new(0, -2), new(1, -2), new(2, -2), 
        new(3, -2), new(4, -2), new(4, -1), new(4, 0)
    ];
    private static readonly Point[] JumpLeftTrajectoryDeltas = [
        new(0, -1), new(0, -2), new(-1, -2), new(-2, -2), 
        new(-3, -2), new(-4, -2), new(-4, -1), new(-4, 0)
    ];

    public IEnumerable<CellCostPair> FindNeighbors(
        Cell sourceCell, 
        bool hasJumpCapability, 
        INeighborFinder.GetDistanceDelegate dist
    )
    {
        // ...
        
        if (!hasJumpCapability || sourceCell.Down is not { IsBlock: true }) {
            yield break;
        }

        foreach (var cell in FindCellsWithJumping(sourceCell, dist)) {
            yield return cell;
        }
    }

    // ...

    private static IEnumerable<CellCostPair> FindCellsWithJumping(
        Cell cell, 
        INeighborFinder.GetDistanceDelegate dist
    )
    {
        if (cell.DownRight is { IsEmpty: true }
            || cell.Right?.Right is { IsBlock: true }
            || cell.Right?.UpRight is { IsBlock: true }
        ) {
            foreach (var cellCostPair in FindCellsOnJumpPath(cell, dist, JumpRightTrajectoryDeltas)) {
                yield return cellCostPair;
            }
        }

        if (cell.DownLeft is { IsEmpty: true }
            || cell.Left?.Left is { IsBlock: true }
            || cell.Left?.UpLeft is { IsBlock: true }
        ) {
            foreach (var cellCostPair in FindCellsOnJumpPath(cell, dist, JumpLeftTrajectoryDeltas)) {
                yield return cellCostPair;
            }
        }
    }

    private static IEnumerable<CellCostPair> FindCellsOnJumpPath(
        Cell cell,
        INeighborFinder.GetDistanceDelegate dist,
        IEnumerable<Point> deltaDirection
    )
    {
        var cost = 0f;
        var previousCell = cell;
        foreach (var delta in deltaDirection) {
            var potentialNeighbor = cell.NeighborAt(delta.X, delta.Y);
            if (potentialNeighbor is null or { IsBlock: true }) {
                yield break;
            }

            cost += dist(previousCell, potentialNeighbor);

            yield return new CellCostPair(potentialNeighbor, cost);

            previousCell = potentialNeighbor;
        }
    }
}

What’s happening here? First of all, we define the jump trajectories in form of deltas from the source cell, one for a jump to the right and another one for a jump to the left. Looking at the trajectory definitions

private static readonly Point[] JumpRightTrajectoryDeltas = [
    new(0, -1), new(0, -2), new(1, -2), new(2, -2), 
    new(3, -2), new(4, -2), new(4, -1), new(4, 0)
];
private static readonly Point[] JumpLeftTrajectoryDeltas = [
    new(0, -1), new(0, -2), new(-1, -2), new(-2, -2), 
    new(-3, -2), new(-4, -2), new(-4, -1), new(-4, 0)
];

we see that applying these deltas to the start cell of a jump will unfold the jump path from earlier:

Next, in the FindNeighbors method we check if the character has jumping capability as well as if the cell below is a block. If that’s not the case, then jumping is impossible and we stop:

if (!hasJumpCapability || sourceCell.Down is not { IsBlock: true }) {
    yield break;    
}

Next, we’ll jump in the FindCellsWithJumping method and look at the first case, which is jumping to the right:

    private static IEnumerable<CellCostPair> FindCellsWithJumping(
        Cell cell, 
        INeighborFinder.GetDistanceDelegate dist
    )
    {
        if (cell.DownRight is { IsEmpty: true }
            || cell.Right?.Right is { IsBlock: true }
            || cell.Right?.UpRight is { IsBlock: true }
        ) {
            foreach (var cellCostPair in FindCellsOnJumpPath(cell, dist, JumpRightTrajectoryDeltas)) {
                yield return cellCostPair;
            }
        }

        // ...
    }

First, we do a simple check if it makes “sense” to try jumping from the current position:

        if (cell.DownRight is { IsEmpty: true }
            || cell.Right?.Right is { IsBlock: true }
            || cell.Right?.UpRight is { IsBlock: true }
        ) {
            // ...
        }

If you look at the three conditions above you might notice that these map to the three example obstacles from earlier (though in a different order):

If cell.DownRight is { IsEmpty: true } is true then there’s a pit to the right.
If cell.Right?.Right is { IsBlock: true } holds true then there’s an obstacle to the right.
Finally, if cell.Right?.UpRight is { IsBlock: true } happens to evaluate to true then there’s a platform we might be able to hop onto.

Again, these are only simple checks to avoid “unnecessary” jumps. In the following step we make use of the trajectory deltas.

private static IEnumerable<CellCostPair> FindCellsOnJumpPath(
    Cell cell,
    INeighborFinder.GetDistanceDelegate dist,
    IEnumerable<Point> deltaDirection
)
{
    var cost = 0f;
    var previousCell = cell;
    foreach (var delta in deltaDirection) {
        var potentialNeighbor = cell.NeighborAt(delta.X, delta.Y);
        if (potentialNeighbor is null or { IsBlock: true }) {
            yield break;
        }

        cost += dist(previousCell, potentialNeighbor);

        yield return new CellCostPair(potentialNeighbor, cost);

        previousCell = potentialNeighbor;
    }
}

Basically, it’s nothing more than a loop over the trajectory deltas, adding each delta to the source cell, checking to see if it’s a cell at all, and if it is, if it’s not a block either, accumulating the cost to reach each respective cell, and yield-returning each cell and the cost. And that’s pretty much it.

As you can already imagine, jumping to the left is the same as jumping to the right, just with a different set of trajectory deltas.

Updating the Rest

We also need to update the pathfinding code a bit so we can use the new neighbor finder class. Here’s the updated code:

public class AStarPathfinder(Grid grid, INeighborFinder neighborFinder)
{
    private List<Cell> _openSet = [];

    public IEnumerator FindPathCoroutine(bool hasJumpCapability)
    {
        grid.Start.CostFromStart = 0;
        grid.Start.CostToTarget = GetDistance(grid.Start, grid.Target);
        _openSet = [grid.Start];

        while (_openSet.Count > 0) {
            var current = _openSet
                .OrderBy(c => c.CostToTarget)
                .ThenBy(c => GetDistance(c, grid.Target))
                .First();

            if (current == grid.Target) {
                ReconstructPath(current);
                yield break;
            }

            _openSet.Remove(current);
            current.IsInOpenSet = false;
            current.IsCurrentlyBeingExamined = true;
            yield return null;

            foreach (var neighbor in neighborFinder.FindNeighbors(current, hasJumpCapability, GetDistance)) {
                if (!IsNeighborWorthTrying(current, neighbor)) continue;
                _openSet.Add(neighbor.Cell);
                neighbor.Cell.WasInspected = true;
                neighbor.Cell.IsInOpenSet = true;
                yield return null;
            }

            current.IsCurrentlyBeingExamined = false;
        }
    }

    private bool IsNeighborWorthTrying(Cell current, CellCostPair neighbor)
    {
        var tentativeCost = current.CostFromStart + neighbor.Cost;
        if (tentativeCost >= neighbor.Cell.CostFromStart) return false;
        neighbor.Cell.Parent = current;
        neighbor.Cell.CostFromStart = tentativeCost;
        neighbor.Cell.CostToTarget = tentativeCost + GetDistance(neighbor.Cell, grid.Target);
        return !_openSet.Contains(neighbor.Cell);
    }

    private static void ReconstructPath(Cell current)
    {
        current.IsOnPath = true;

        var walkingCell = current;
        while (walkingCell.Parent != null) {
            walkingCell.Parent.IsOnPath = true;
            walkingCell = walkingCell.Parent;
        }
    }

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

In addition to the Grid object we pass an instance of INeighborFinder to the primary constructor. So far so good. The next thing that should not go unnoticed is that the method FindPathCoroutine now, besides receiving a boolean parameter for whether jumping is enabled, returns an instance of the IEnumerator interface. But, if you take a look at the yield return statements, you will see that only null is returned. So what is this?

This is what might be called a coroutine, which is a component whose execution can be suspended and resumed later. As you may recall, the previous version of this method performed a single step of the algorithm and then returned a boolean to indicate whether the algorithm had finished. The version presented here does something similar, but instead of returning after a single step, it yields null, suspends execution, and then returns control to the consumer of the enumerator.

Here’s how this thing is used, boiled down to just using the AStarPathfinder:

public class Pathfinding
{
    // ...
    
    private readonly ControlPanel _controlPanel;
    private readonly AStarPathfinder _pathFinder;
    private readonly Grid _grid;

    // ...

    private IEnumerator _findPathCoroutine;
    private bool _hasJumpCapability;

    // ...

    public Pathfinding()
    {
        _pathFinder = new AStarPathfinder(_grid, new NeighborFinder());
        _findPathCoroutine = _pathFinder.FindPathCoroutine(_hasJumpCapability);

        _controlPanel = new ControlPanel(/* ... */);
        // ...
        _controlPanel.StepButtonClicked += Step;
        _controlPanel.ResetButtonClicked += Reset;
        _controlPanel.JumpingButtonToggled += hasJumpCapability => {
            _hasJumpCapability = hasJumpCapability;
            Reset();
        };
    }

    // ...

    public void Update(GameTime gameTime)
    {
        // ...
        Step();
    }

    private void Step()
    {
        if (_isPathfindingFinished) return;
        _isPathfindingFinished = !_findPathCoroutine.MoveNext();
    }

    private void Reset()
    {
        _grid.Reset();
        _findPathCoroutine = _pathFinder.FindPathCoroutine(_hasJumpCapability);
        _isPathfindingFinished = false;
    }
}

At the beginning and whenever we need to start over (e.g. because the grid changed) we call

_findPathCoroutine = _pathFinder.FindPathCoroutine(_hasJumpCapability);

which returns an IEnumerator over which we can iterate a single step by calling

_findPathCoroutine.MoveNext()

which in turn returns true if the enumerator could be moved to the next element or false when we reached the end.

Interactive Example

At last, here’s the interactive example you’ve been waiting for:

Click to load app

This example lets you step through the algorithm step by step or watch it do its work. You can also manipulate the grid by changing the cell types.

Compared to the other interactive example from one of the top-down posts, there’s an additional toggle switch which let’s you control whether the character has jump capability. Here are the buttons explained:

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.
Toggle Jumping: When switched on, jumping is enabled.

Furthermore, you can edit the game world. By clicking one cell you can cycle through the different cell types. If you click and hold, you can “paint” the world with the new cell type. Plus, you can drag the start (A) and target (B) cells around.

When the algorithm is running, the cells change color:

Red: This is the cell currently being examined.
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 2, and the estimated cost from the start to the target via this cell is 14.

Conclusion

In a nutshell, making the switch from a top-down approach to a side-view platformer brings a few challenges, because of the involvement of gravity and the limited movement options. Characters can’t just go up and down in the same way they would in a top-down scenario. Instead, they use ladders, hanging bars, and jumping to overcome obstacles in the game world. We looked at how we could tweak the A* pathfinding algorithm and the neighbor-finding logic in particular to make it work with these constraints.