A* Pathfinding for 2D Grid-Based Platformers: Making a Bot Follow the Path

In this tutorial, we'll use the platformer pathfinding algorithm we've been building to power a bot that can follow the path by itself; just click on a location and it'll run and jump to get there. This is very useful for NPCs!

Demo

You can play the Unity demo, or the WebGL version (100MB+), to see the final result in action. Use WASD to move the character, left-click on a spot to find a path you can follow to get there, right-click a cell to toggle the ground at that point, middle-click to place a one-way platform, and click-and-drag the sliders to change their values.

Updating the Engine

Handling the Bot State

The bot has two states defined: the first is for doing nothing, and the second is for handling the movement. In your game, though, you'll probably need many more to change the bot's behaviour according to the situation.

public enum BotState
{
	None = 0,
	MoveTo,
}

The bot's update loop will do different things depending on which state is currently assigned to mCurrentBotState:

void BotUpdate()
{
    switch (mCurrentBotState)
    {
        case BotState.None:
            /* no need to do anything */
            break;
            
        case BotState.MoveTo:
            /* bot movement update logic */
            break;
    }
    
    CharacterUpdate();
}

The CharacterUpdate function handles all the inputs and updates physics for the bot.

To change the state, we'll use a ChangeState function which simply assigns the new value to mCurrentBotState:

1	public void ChangeState(BotState newState)
2	{
3	mCurrentBotState = newState;
4	}

Controlling the Bot

We'll control the bot by simulating inputs, which we'll assign to an array of Booleans:

1	protected bool[] mInputs;

This array is indexed by the KeyInput enum:

public enum KeyInput
{
    GoLeft = 0,
	GoRight,
	GoDown,
	Jump,
	Count
}

For example, if we want to simulate a press of the left button, we'll do it like this:

1	mInputs[(int)KeyInput.GoLeft] = true;

The character logic will then handle this artificial input in the same way that it would handle real input.

We'll also need an additional helper function or a lookup table to get the number of frames we need to press the jump button for in order to jump a given number of blocks:

int GetJumpFrameCount(int deltaY)
{
    if (deltaY <= 0)
        return 0;
    else
    {
        switch (deltaY)
        {
            case 1:
                return 1;
            case 2:
                return 2;
            case 3:
                return 5;
            case 4:
                return 8;
            case 5:
                return 14;
            case 6:
                return 21;
            default:
                return 30;
        }
    }
}

Note that this will only work consistently if our game updates with a fixed frequency and the character's starting jump speed is the same. Ideally, we'd calculate these values separately for each character depending on that character's jump speed, but the above will work fine in our case.

Preparing and Obtaining the Path to Follow

Constraining the Goal Location

Before we actually use the pathfinder, it'd be a good idea to force the goal destination to be on the ground. This is because the player is quite likely to click a spot that is slightly above the ground, in which case the bot's path would end with an awkward jump into the air. By lowering the end point to be right on the surface of the ground, we can easily avoid this.

First, let's look at the TappedOnTile function. This function gets called when the player clicks anywhere in the game; the parameter mapPos is the position of the tile that the player clicked on:

1	public void TappedOnTile(Vector2i mapPos)
2	{
3	}

We need to lower the position of the clicked tile until it is on the ground:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;
}

Finally, once we arrive at a ground tile, we know where we want to move the character to:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;

    MoveTo(new Vector2i(mapPos.x, mapPos.y + 1));
}

Determining the Starting Location

Before we actually call the FindPath function, we need to make sure that we pass the correct starting cell.

First, let's assume that the starting tile is the bottom-left cell of a character:

1	public void MoveTo(Vector2i destination)
2	{
3	Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
4	}

This tile might not be the one we want to pass to the algorithm as the first node, because if our character is standing on the edge of the platform, the startTile calculated this way may have no ground, as in the following situation:

In this case, we'd like to set the starting node to the tile that's on the left side of the character, not on its center.

Let's start by creating a function that will tell us if the character will fit a different position, and if it does, whether it's on the ground at that spot:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

First, let's see if the character fits the spot. If it doesn't, we can immediately return false:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }
}

Now we can see whether any of the tiles below the character are ground tiles:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }

    for (int x = pos.x; x < pos.x + mWidth; ++x)
    {
        if (mMap.IsGround(x, pos.y - 1))
            return true;
    }

    return false;
}

Let's go back to the MoveTo function, and see if we have to change the start tile. We need to do that if the character is on the ground but the start tile isn't:

Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
        
if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
}

We know that, in this case, the character stands on either the left edge or the right edge of the platform.

Let's first check the right edge; if the character fits there and the tile is on the ground, then we need to move the start tile one space to the right. If it doesn't, then we need to move it to the left.

if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
    if (IsOnGroundAndFitsPos(new Vector2i(startTile.x + 1, startTile.y)))
        startTile.x += 1;
    else
        startTile.x -= 1;
}

Now we should have all the data we need to call the pathfinder:

var path =  mMap.mPathFinder.FindPath(
            startTile, 
            destination,
            Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f), 
            Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f), 
            (short)mMaxJumpHeight);

The first argument is the start tile.

The second is the destination; we can pass this as-is.

The third and fourth arguments are the width and the height which need to be approximated by the tile size. Note that here we want to use the ceiling of the height in tiles—so, for example, if the real height of the character is 2.3 tiles, we want the algorithm to think the character is actually 3 tiles high. (It's better if the real height of the character is actually a bit less than its size in tiles, to allow a bit more room for mistakes from the path following AI.)

Finally, the fifth argument is the maximum jump height of the character.

Backing Up the Node List

After running the algorithm we should check whether the result is fine—that is, if any path has been found:

1	if (path != null && path.Count > 1)
2	{
3	}

If so, we need to copy the nodes to a separate buffer, because if some other object were to call the pathfinder's FindPath function right now, the old result would be overwritten. Copying the result to a separate list will prevent this.

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);
}

As you can see, we're copying the result in reverse order; this is because the result itself is reversed. Doing this means the nodes in the mPath list will be in first-to-last order.

Now let's set the current goal node. Because the first node in the list is the starting point, we can actually skip it and proceed from the second node onwards:

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);
        
    mCurrentNodeId = 1;
    ChangeState(BotState.MoveTo);
}

After setting the current goal node, we set the bot state to MoveTo, so an appropriate state will be enabled.

Getting the Context

Before we start writing the rules for the AI movement, we need to be able to find what situation the character is in at any given point.

We need to know:

the positions of the previous, current and next destinations
whether the current destination is on the ground or in the air
whether the character has reached the current destination on the x-axis
whether the character has reached the current destination on the y-axis

Note: the destinations here are not necessarily the final goal destination; they're the nodes in the list from the previous section.

This information will let us accurately determine what the bot should do in any situation.

Let's start by declaring a function to get this context:

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround, out bool reachedX, out bool reachedY)
2	{
3	}

Calculating World Positions of Destination Nodes

The first thing we should do in the function is calculate the world position of the destination nodes.

Let's start by calculating this for the previous destination. This operation depends on how your game world is set up; in my case, the map coordinates do not match the world coordinates, so we need to translate them.

Translating them is really simple: we just need to multiply the position of the node by the size of a tile, and then offset the calculated vector by the map position:

1	prevDest = new Vector2(mPath[mCurrentNodeId - 1].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId - 1].y * Map.cTileSize + mMap.transform.position.y);

Note that we start with mCurrentNodeId equal to 1, so we don't need to worry about accidentally trying to access a node with an index of -1.

We'll calculate the current destination's position in the same way:

1	currentDest = new Vector2(mPath[mCurrentNodeId].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId].y * Map.cTileSize + mMap.transform.position.y);

And now for the next destination's position. Here we need to check if there are any nodes left to follow after we reach our current goal, so first let's assume that the next destination is the same as the current one:

1	nextDest = currentDest;

Now, if there are any nodes left, we'll calculate the next destination in the same way that we did the previous two:

if (mPath.Count > mCurrentNodeId + 1)
{
    nextDest = new Vector2(mPath[mCurrentNodeId + 1].x * Map.cTileSize + mMap.transform.position.x,
                                  mPath[mCurrentNodeId + 1].y * Map.cTileSize + mMap.transform.position.y);
}

Checking Whether the Node is on the Ground

The next step is to determine whether the current destination is on the ground.

Remember that it is not enough to only check the tile directly underneath the goal; we need to consider the cases where the character is more than one block wide:

Let's start by assuming that the destination's position is not on the ground:

1	destOnGround = false;

Now we'll look through the tiles beneath the destination to see if there are any solid blocks there. If there are, we can set destOnGround to true:

for (int x = mPath[mCurrentNodeId].x; x < mPath[mCurrentNodeId].x + mWidth; ++x)
{
    if (mMap.IsGround(x, mPath[mCurrentNodeId].y - 1))
    {
        destOnGround = true;
        break;
    }
}

Checking Whether the Node Has Been Reached on the X-Axis

Before we can see if the character has reached the goal, we need to know its position on the path. This position is basically the center of the bottom-left cell of our character. Since our character is not actually built from cells, we are simply going to use the bottom left position of the character's bounding box plus half a cell:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

This is the position that we need to match to the goal nodes.

How can we determine whether the character has reached the goal on the x-axis? It'd be safe to assume that, if the character is moving right and has an x-position greater than or equal to that of the destination, then the goal has been reached.

To see if the character was moving right we'll use the previous destination, which in this case must have been to the left of the current one:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x);

The same applies to the opposite side; if the previous destination was to the right of the current one and the character's x-position is less than or equal to that of the goal position, then we can be sure that the character has reached the goal on the x-axis:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
2	\|\| (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x);

Snap the Character's Position

Sometimes, because of the character's speed, it overshoots the destination, which may result in it not landing on the target node. See the following example:

To fix this, we'll snap the character's position so that it lands on the goal node.

The conditions for us to snap the character are:

The goal has been reached on the x-axis.
The distance between the bot's position and current destination is greater than cBotMaxPositionError.
The distance between the bot's position and the current destination is not very far, so we don't snap the character from far away.
The character did not move left or right last turn, so we snap the character only if it's falling straight down.

if (reachedX && Mathf.Abs(pathPosition.x - currentDest.x) > Constants.cBotMaxPositionError && Mathf.Abs(pathPosition.x - currentDest.x) < Constants.cBotMaxPositionError*3.0f && !mPrevInputs[(int)KeyInput.GoRight] && !mPrevInputs[(int)KeyInput.GoLeft])
{
    pathPosition.x = currentDest.x;
    mPosition.x = pathPosition.x - Map.cTileSize * 0.5f + mAABB.HalfSizeX + mAABBOffset.x;
}

cBotMaxPositionError in this tutorial is equal to 1 pixel; this is how far off we let the character be from the destination while still allowing it to go to the next goal.

Checking Whether the Node Has Been Reached on the Y-Axis

Let's figure out when we can be sure that the character has reached its target's Y position. First of all, if the previous destination is below the current one, and our character jumps to the height of the current goal, then we can assume that the goal has been reached.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y);

Similarly, if the current destination is below the previous one and the character has reached the y-position of the current node, we can set reachedY to true as well.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.)
2	\|\| (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y);

Regardless of whether the character needs to be jumping or falling to reach the destination node's y-position, if it's really close, then we should set reachedY to true also:

reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)

    || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)

    || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);

If the destination is on the ground but the character isn't, then we can assume that the current goal's Y position has not been reached:

1	if (destOnGround && !mOnGround)
2	reachedY = false;

That's it—that's all the basic data we need to know to consider what kind of movement the AI needs to do.

Handling the Bot's Movement

The first thing to do in our update function is get the context that we've just implemented:

1	Vector2 prevDest, currentDest, nextDest;
2	bool destOnGround, reachedY, reachedX;
3	GetContext(out prevDest, out currentDest, out nextDest, out destOnGround, out reachedX, out reachedY);

Now let's get the character's current position along the path. We calculate this in the same way we did in the GetContext function:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

At the beginning of the frame we need to reset the fake inputs, and assign them only if a condition to do so arises. We'll be using only four inputs: two for movement left and right, one for jumping, and one for dropping off a one way platform.

1	mInputs[(int)KeyInput.GoRight] = false;
2	mInputs[(int)KeyInput.GoLeft] = false;
3	mInputs[(int)KeyInput.Jump] = false;
4	mInputs[(int)KeyInput.GoDown] = false;

The very first condition for movement will be this: if the current destination is lower than the position of the character and the character is standing on a one way platform, then press the down button, which should result in the character jumping off the platform downwards:

1	if (pathPosition.y - currentDest.y > Constants.cBotMaxPositionError && mOnOneWayPlatform)
2	mInputs[(int)KeyInput.GoDown] = true;

Handling Jumps

Let's lay out how our jumps should work. First off, we don't want to keep the jump button pressed if mFramesOfJumping is 0.

1	if (mFramesOfJumping > 0)
2	{
3	}

The second condition to check is that the character is not on the ground.

In this implementation of platformer physics, the character is allowed to jump if it just stepped off the edge of a platform and is no longer on the ground. This is a popular method to mitigate an illusion that the player has pressed the jump button but the character didn't jump, which might have appeared due to input lag or the player pressing the jump button right after the character has moved off the platform.

1	if (mFramesOfJumping > 0 && !mOnGround)
2	{
3	}

This condition will work if the character needs to jump off a ledge, because the frames of jumping will be set to an appropriate amount, the character will naturally walk off the ledge, and at that point it will also start the jump.

This will not work if the jump needs to be performed from the ground; to handle these we need to check these conditions:

The character has reached the destination node's x-position, where it's going to start jumping.
The destination node is not on the ground; if we are to jump up, we need to go through a node that's in the air first.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround)))
3	{
4	}

The character should also jump if it is on ground and the destination is on the ground as well. This will generally happen if the character needs to jump one tile up and to the side to reach a platform that's just one block higher.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround) \|\| (mOnGround && destOnGround)))
3	{
4	}

Now let's activate the jump and decrement the frames of jumping, so that the character holds the jump for the correct number of frames:

if (mFramesOfJumping > 0 &&
    (!mOnGround || (reachedX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

Note that we decrement the mFramesOfJumping only if the character is not on the ground. This is to avoid accidentally decreasing the jump length before starting the jump.

Proceeding to the Next Destination Node

Let's think about what needs to happen when we reach the node—that is, when both reachedX and reachedY are true.

1	if (reachedX && reachedY)
2	{
3	}

First, we'll increment the current node ID:

1	mCurrentNodeId++;

Now we need to check whether this ID is greater than the number of nodes in our path. If it is, that means the character has reached the goal:

if (mCurrentNodeId >= mPath.Count)
{
    mCurrentNodeId = -1;
    ChangeState(BotState.None);
    break;
}

The next thing we must do is calculate the jump for the next node. Since we'll need to use this in more than one place, let's make a function for it:

1	public int GetJumpFramesForNode(int prevNodeId)
2	{
3	}

We only want to jump if the new node is higher than the previous one and the character is on the ground:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
    }
}

To find out how many tiles we'll need to jump, we're going to iterate through nodes for as long as they go higher and higher. When we get to a node that is at a lower height, or a node that has ground under it, we can stop, since we know that there will be no need to go higher than that.

First, let's declare and set the variable that will hold the value of the jump:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
    }
}

Now let's iterate through the nodes, starting at the current node:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
        }
    }
}

If the next node is higher than the jumpHeight, and it's not on the ground, then let's set the new jump height:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight && !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
        }
    }
}

If the new node height is lower than the previous, or it's on the ground, then we return the number of frames of jump needed for the found height. (And if there's no need to jump, let's just return 0.)

public int GetJumpFramesForNode(int prevNodeId)
{
    int currentNodeId = prevNodeId + 1;

    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
                jumpHeight = mPath[i].y - mPath[prevNodeId].y;
            if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                return GetJumpFrameCount(jumpHeight);
        }
    }
    
    return 0;
}

We need to call this function in two places.

The first one is in the case where the character has reached the node's x- and y-positions:

if (reachedX && reachedY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;

    if (mCurrentNodeId >= mPath.Count)
    {
        mCurrentNodeId = -1;
        ChangeState(BotState.None);
        break;
    }

    if (mOnGround)
        mFramesOfJumping = GetJumpFramesForNode(prevNodeId);
}

Note that we set the jump frames for the whole jump, so when we reach an in-air node we don't want to change the number of jump frames that was determined before the jump took place.

After we update the goal, we need to process everything again, so the next movement frame gets calculated immediately. For this, we'll use a goto command:

1	goto case BotState.MoveTo;

The second place we need to calculate the jump for is the MoveTo function, because it might be the case that the first node of the path is a jump node:

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);

    mCurrentNodeId = 1;

    ChangeState(BotState.MoveTo);

    mFramesOfJumping = GetJumpFramesForNode(0);
}

Handling Movement to Reach the Node's X-Position

Now let's handle the movement for the case where the character has not yet reached the target node's x-position.

Nothing complicated here; if the destination is to the right, we need to simulate the right button press. If the destination is to the left, then we need to simulate the left button press. We only need to move the character if the difference in position is more than the cBotMaxPositionError constant:

else if (!reachedX)
{
    if (currentDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - currentDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Handling Movement to Reach the Node's Y-Position

If the character has reached the target x-position but we still it to jump higher, we can still move the character left or right depending on where the next goal is. This will just mean that the character does not stick so rigidly to the found path. Thanks to that, it'll be much easier to get to the next destination, because instead of simply waiting to reach the target y-position, the character will be naturally moving towards the next node's x-position while it's doing so.

We'll only move the character towards the next destination if it exists at all and it's not on the ground. (If it's on the ground, then we can't skip it because it's an important checkpoint—it resets the character's vertical speed and allows it to use the jump again.)

1	else if (!reachedY && mPath.Count > mCurrentNodeId + 1 && !destOnGround)
2	{
3
4	}

But before we actually move towards the next goal, we need to check that we won't break the path by doing so.

Avoiding Breaking a Fall Prematurely

Consider the following scenario:

Here, as soon as the character walked off the ledge where it started, it reached the x-position of the second node, and was falling to reach the y-position. Since the third node was to the right of the character, it moved right—and ended up in a tunnel above the one we wanted it to go into.

To fix this, we need to check whether there are any obstacles between the character and the next destination; if there aren't, then we are free to move the character towards it; if there are, then we need to wait.

First, let's see which tiles we'll need to check. If the next goal is to the right of the current one, then we'll need to check the tiles on the right; if it's to the left then we'll need to check the tiles to the left. If they are at the same x-position, there's no reason to make any pre-emptive movements.

int checkedX = 0;

int tileX, tileY;
mMap.GetMapTileAtPoint(pathPosition, out tileX, out tileY);

if (mPath[mCurrentNodeId + 1].x != mPath[mCurrentNodeId].x)
{
    if (mPath[mCurrentNodeId + 1].x > mPath[mCurrentNodeId].x)
        checkedX = tileX + mWidth;
    else
        checkedX = tileX - 1;
}

As you can see, the x-coordinate of the node to the right depends on the width of the character.

Now we can check whether there are any tiles between the character and the next node's position on the y-axis:

1	if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
2	{
3	}

The AnySolidBlockInStripe function checks whether there are any solid tiles between two given points on the map. The points need to have the same x-coordinate. The x-coordinate we are checking is the tile we'd like the character to move into, but we're not sure if we can, as explained above.

Here's the implementation of the function.

public bool AnySolidBlockInStripe(int x, int y0, int y1)
{
    int startY, endY;

    if (y0 <= y1)
    {
        startY = y0;
        endY = y1;
    }
    else
    {
        startY = y1;
        endY = y0;
    }

    for (int y = startY; y <= endY; ++y)
    {
        if (GetTile(x, y) == TileType.Block)
            return true;
    }

    return false;
}

As you can see, the function is really simple; it just iterates through the tiles in a column, starting from the lower one.

Now that we know we can move towards the next destination, let's do so:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Allowing the Bot to Skip Nodes

That's almost it—but there's still one case to solve. Here's an example:

As you can see, before the character reached the second node's y-position, it bumped its head on the floating tile, because we made it move towards the next destination to the right. As a result, the character ends up never reaching the second node's y-position; instead it moved straight on to the third node. Since reachedY is false in this case, it cannot proceed with the path.

To avoid such cases, we'll simply check whether the character reached the next goal before it reached the current one.

The first move towards this will be separating our previous calculations of reachedX and reachedY into their own functions:

public bool ReachedNodeOnXAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
        || (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x)
        || Mathf.Abs(pathPosition.x - currentDest.x) <= Constants.cBotMaxPositionError;
}

public bool ReachedNodeOnYAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)
        || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)
        || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);
}

Next, replace the calculations with the function call in the GetContext function:

1	reachedX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);
2	reachedY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

Now we can check whether the next destination has been reached. If it has, we can simply increment mCurrentNode and immediately re-do the state update. This will make the next destination become the current one, and since the character has reached it already, we will be able to move on:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;

    if (ReachedNodeOnXAxis(pathPosition, currentDest, nextDest) && ReachedNodeOnYAxis(pathPosition, currentDest, nextDest))
    {
        mCurrentNodeId += 1;
        goto case BotState.MoveTo;
    }
}

That's all for character movement!

Handling Restart Conditions

It's good to have a backup plan for a situation in which the bot is not moving through the path like it should. This can happen if, for example, the map gets changed—adding an obstacle to an already calculated path may cause the path to become invalid. What we'll do is reset the path if the character is stuck for longer than a particular number of frames.

So, let's declare variables that will count how many frames the character has been stuck and how many frames it may be stuck at most:

1	public int mStuckFrames = 0;
2	public const int cMaxStuckFrames = 20;

We need to reset this when we call MoveTo function:

public void MoveTo(Vector2i destination)
{
    mStuckFrames = 0;
    /*
    ...
    */
}

And finally, at the end of the BotState.MoveTo, let's check whether the character is stuck. Here, we simply need to check if its current position is equal to the old one; if so, then we also need to increment the mStuckFrames and check whether the character has been stuck for more frames than cMaxStuckFrames—and if it was, then we need to call the MoveTo function with the last node of the current path as the parameter. Of course, if the position is different, then we need to reset the mStuckFrames to 0:

if (mFramesOfJumping > 0 &&
    (!mOnGround || (reachedX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

if (mPosition == mOldPosition)
{
    ++mStuckFrames;
    if (mStuckFrames > cMaxStuckFrames)
        MoveTo(mPath[mPath.Count - 1]);
}
else
    mStuckFrames = 0;

Now the character should find an alternative path if it wasn't able to finish the initial one.

Conclusion

That's the whole of the tutorial! It's been a lot of work, but I hope you'll find this method useful. It is by no means a perfect solution for platformer pathfinding; the approximation of the jump curve for the character that the algorithm needs to make is often quite tricky to do and can lead to incorrect behaviour. The algorithm still can be extended—it's not very hard to add ledge-grabs and other kinds of extended movement flexibility—but we've covered the basic platformer mechanics. It is also possible to optimize the code to make it faster as well as use less memory; this iteration of the algorithm isn't perfect at all when it comes to those aspects. It also suffers from quite poor approximation of the curve when falling at large speeds.

The algorithm can be used in many ways, most notably to enhance the enemy AI or AI companions. It can also be used as a control scheme for touch devices—this would work basically the same way it does in the tutorial demo, with the player tapping wherever they want the character to move. This removes the execution challenge upon which many platformers have been built, so the game would have to be designed differently, to be much more about positioning your character in the right spot rather than learning to control the character accurately.

Thanks for reading! Be sure to leave some feedback on the method and also let me know if you've made any improvements to it!