Demystifying 2D Platformer Pathfinding, Part 3

This part will expand upon the last by adding cross-platform edges for our AI agent to traverse. We are going to continue handling all of our Node and edge creation at runtime so that our pathfinding solution is flexible and can work with procedurally generated content. It should be noted that you can of course do all of the graph creation at build time as well as long as your levels are not procedurally generated.

Strategic Overview

The strategy we are going to use as we move forward is the following:

  1. we will simulate agent movement in various ways to gather data on how the agent moves in various situations (jumping, running off a ledge, etc)
  2. we then playback the data checking for solid tiles along the way to link Nodes with new edges based on how the data was obtained (again, jumping, running off a ledge, etc)

By generating our graph like this we can extend our pathfinding setup to cover all sorts of different agent types. If one agent has a different move speed or gravity the movement simulation will create unique data that matches the agent specs and when we play it back to link Nodes it will create edges that fit that specific movement type. Different agents can also have their own unique abilities such as wall jumps. As long as we have simulated movement data we can pathfind for any type of movement.

Before we jump into adding the new edges we have to do some modification to our data structures. Currently, our edges are all just Node to Node. That works fine for walkways, which is all we currently have in our graph. Once we start adding different kinds of edges (such as jumps) we are going to need some more information so that our agent knows how to act when it is moving from Node to Node.

To keep things simple we will just extend the Node class and add a new EdgeType enum to specify what action is required by the agent to traverse the edge. The Edge will also contain a reference to the Node that it links to via the targetNode field. If we ever have more complex edges that need some extra data to assist the agent while traversing them we can always subclass Edge and add it.

enum EdgeType:  
    JumpDownOneWay
    RunOff
    Jump


struct Edge extends Node:  
    Node targetNode
    EdgeType type

One Way Platforms

We'll start with the easiest of all edges: jumping down through one way platforms. This is the one type that doesn't require any simulated movement so we'll get it out of the way before chasing down the big dogs.

// loop through all of our Nodes
foreach node in nodeList:  
    // ensure we have a one way platform below the Node
    if !tileIsOneWayPlatform( node.x, node.y + 1 ):
        continue;

    // fetch the next Node below the one way platform if present and add an Edge
    targetNode = getNodeBelow( node.x, node.y + 2 )
    if targetNode is not null:
        node.edges.add( new Edge( targetNode, EdgeType.JumpDownOneWay ) )

That's all there is to it. We now have edges linking up all the one way platforms with the Nodes below.

Simulating Agent Movement

Now we can finally get into the meat of 2D platformer pathfinding. When we do our agent simulation it is best handled by using the same code that actually handles moving your agent. That will ensure we get accurate data that can be reproduced properly when following the path later. The algorithm for getting the simulated movement data is the same for any type of movement so we will illustrate it in pseudo code by simulating running off a ledge. The general algorithm is the following:

  • get all movement speeds in terms of tiles. For example, if the tile size is 16px divide by 16.
  • simulate movement frame by frame using a reasonable delta time (1/60 will do the trick when targeting 60 fps)
  • each time we simulate movement check to see if we have travelled 1 tile in any direction (up, down, left or right). If so, record that data point.
  • keep doing this until we reach some predefined maximum fall height
// choose a sensible deltaTime for the simulation
deltaTime = 1 / 60  
// running off a ledge we start with no vertical velocity and at our agents horizontal speed
velocity = new Vector2( horizontalSpeed, 0 )


// dataBin: stores the delta tile movements of the simulation
// vSpeed: max fall speed of the agent
// gravitySpeed: agent gravity acceleration * deltaTime to get a velocity
// velocity: starting velocity of the agent
// motion: accumulates frame-by-frame movement
def simulate( Point[] dataBin, float vSpeed, float gravitySpeed, float deltaTime, Vector2 velocity, Vector2 motion ):  
    // keep track of our fallHeight so that we stop when we reach maxFallHeight
    var fallHeight = 0;
    while( fallHeight <= maxFallHeight ):
        // simulate movement until we travel 1 tile in either the x or y direction. Y can go up
        // or down so we use abs whereas x can only increment.
        while( motion.X < 1 && Math.Abs( motion.Y ) < 1 ):
            velocity.Y = approach( velocity.Y, vSpeed, gravitySpeed )
            motion += velocity * deltaTime;

        // did we move a tile in the x direction?
        if( motion.X > 1 ):
            // bookkeeping. Increment motion and keep the remainder
            var xIncr = truncateToInt( motion.X )
            motion.X -= xIncr
            dataBin.Add( new Point( xIncr, 0 ) )

        // did we move a tile in the y direction?
        if( Math.Abs( motion.Y ) > 1 ):
            var yIncr = truncateToInt( motion.Y )
            motion.Y -= yIncr
            dataBin.Add( new Point( 0, yIncr ) )

            // only increment our fallHeight when we are falling
            if( yIncr > 0 )
                fallHeight++

The simulation results in a list of points that represent the path in tiles that the agent will move through. That data can then easily be looped through and played back. The fall data might look something like the following:

Run-off Connections

We can put our simulated data to work for us here. There will only be minor differences depending on the simulated data we are working with so most of this code will be identical for all simulated data types. One example of how the code would differ is the following: in the case of a run-off, we are only concerned with starting locations that are ledges. If this were jump data we would not want to limit it to just ledges since an agent can jump from any ground position.

Here is the algorithm we will use for adding run-off edges. Only the first step is specific to run-off edges. The rest is exactly the same for jumping:

  • loop through our Nodes and find any ledge Nodes
  • ensure that we have clearance and no solid tiles in the way of our starting Node
  • "playback" our simulated data step-by-step
    • check directly below for a solid tile to land on. Add an Edge and bail out if we hit ground.
    • we didn't land yet so check further down up to our maximum fall height for a Node to land on. Add an Edge if we find one.
foreach node in nodeList:  
    // we can only run off of ledges so check for all ledge Nodes
    if node.type == LedgeLeft or node.type == NodeType.LedgeBoth:
        // ensure we have clearance to walk off the ledge
        if isTilePassable( node.x - 1, node.y ) and getClearanceForTile( node.x - 1, node.y ) >= agentHeight:
            checkForRunoffConnections( node, -1 )

    if node.type == LedgeRight or node.type == NodeType.LedgeBoth:
        // ensure we have clearance to walk off the ledge
        if isTilePassable( node.x + 1, node.y ) and getClearanceForTile( node.x + 1, node.y ) >= agentHeight:
            checkForRunoffConnections( node, 1 )


def checkForRunoffConnections( Node node, int direction ):  
    x = node.x + direction
    y = node.y

    foreach point in runoffData:
        x += point.x * direction
        y += point.y

        // see if we hit a wall or if we dont have clearance
        if !isTilePassable( x, y ) or getClearanceForTile( x, y ) < agentHeight
            return

        // check below to see if we have a tile to land on
        if !isTilePassable( x, y + 1 ):
            targetNode = getNode( x, y )
            node.edges.add( new Edge( targetNode, EdgeType.RunOff ) )
            return

        // we did not land yet based on our fall trajectory. If we have ground below we can
        // still fall to it so check for ground below
        targetNode = getNodeBelow( node.x, node.y + 2 )
        if targetNode is not null:
            node.edges.add( new Edge( targetNode, EdgeType.RunOff ) )

To visualize what we are doing with this code we'll take the fall trajectory image above and add blue lines showing all the fall checks that we do while walking through our simulated movement. A run-off edge should be added for each unique position that we can fall to. We are not limited to just the trajectory that we simulated (the red line). An agent can stop moving forward at any point while running off the ledge and fall straight down.

Conclusion (so far)

Our pathfinding is starting to take shape. We can generate paths that connect platforms now thanks to our run-off edges (only downward so far!) Hopefully, the overall concept of how to generate the graph is starting to become clear. In the next part we will drill this further by adding jump edges. The final piece of the puzzle will be actually using the path that our graph search algorithm generates to move an agent to the goal destination.