Demystifying 2D Platformer Pathfinding, Part 4

In the previous 3 parts of this series, we built up a knowledge of graph search algorithms and started to generate our platformer pathfinding graph. In this post we will add jump connections to the graph.

Nothing here should be much of a surprise to readers who read part 3. The strategy for adding jump edges is exactly the same as run-offs: simulate a jump to get the jump path data then play it back starting at any relevant Nodes in our graph. Which Nodes that is would be chosen based on the level design and how agents should traverse it. For example, for an infinite runner all jumps would only occur from the end of ledges so jumps would only be simulated from NodeType.LedgeRight. Other level designs would have different goals and it may be that you want to simulate jumps from every Node or every other Node. This is where you get to experiment to see what works best for your specific setup.

// just like a run-off except we also set the y velocity to our jumpSpeed
velocity = new Vector2( horizontalSpeed, jumpSpeed )

// call our simulate method as defined in part 3

Jump Connections

Unsurprisingly, we will also be playing back the data in pretty much the exact same fashion as for run-offs:

  • playback the jump 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.

Jump data playback with straight-down, early exit checks

There are a couple little things we can do to get some better and more flexible results. We'll add our run-off Edges before our jump Edges. The reason for this is that we want run-offs to take precedence. When we do our straight-down checks (the blue lines in the image above) before adding the Edge we should check to see if we already have an Edge to the same Node. If there is already an Edge (it would be a run-off Edge) then don't add it. This prioritizes run-offs which feels more human-like. Another trick we can do is that during jump data playback if we hit our head instead of bailing out on the check we can fast-forward through the jump data until it starts to fall. This lets us keep any connections that have a head bonk instead of discarding them. What we end up with is very similar to the checkForRunoffConnections method from part 3:

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

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

        // see if we hit a wall
        if !isTilePassable( x, y )
            return

        // ensure we have clearance
        if getClearanceForTile( x, y ) < agentHeight:
            // if we were moving up and hit our head fast forward jump data until it is falling down
            if point.y < 0:
                fastForwardDataToFall( jumpData )
                continue
            // if we got here, we hit our head moving horizontally so we are done
            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.Jump ) )
            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 )
        // ensure we don't already have a run-off Edge before adding it
        if targetNode is not null and !node.edges.containsEdgeAtNode( targetNode ):
            node.edges.add( new Edge( targetNode, EdgeType.Jump ) )

Expanding on Jump Connections

Right now, we are simulating only one jump: a full-height jump. For some games that is all that you will need. Other games may have levels that require more precision doing half-height or quarter-height jumps. We now have the framework to easily add these. For example, we can do jump simulations for various jump heights like so:

// alter jumpSpeed to simulate different jump heights
velocity = new Vector2( horizontalSpeed, jumpSpeed / 2 )  
// call our simulate method as defined in part 3

velocity = new Vector2( horizontalSpeed, jumpSpeed / 4 )  
// call our simulate method as defined in part 3

One other jump type that gives agents a more human feel and (depending on the level layout) can provide more navigation options to an agent is the jump-up-and-over type. This is basically a jump straight up and then at the peak of the jump pressing left/right to move horizontally.

We can again simulate this quite easily by calculating the max jump height and then reusing the run-off data we already have. We would end up with something like this:

// figure out the maximum number of tiles we can jump up
jumpHeight = calculateMaxJumpHeightInTiles( jumpVelocity )

// add data for each tile
for i in range( 0, jumpHeight ):  
    jumpUpAndOverData.add( new Point( 0, -1 ) );

// add in the run-off data we already calculated
jumpUpAndOverData.addRange( runoffData );  

Playback of the data is identical to the checkForJumpConnections above.

The blueprint for adding new jump types should be pretty clear by now. Get some simulated data for the jump type and the play it back from any interesting Nodes to find the possible connections to other Nodes. This strategy will work for just about any type of movement. If you agents have dashes, double-jumps, floaty jumps, heavy-gravity jumps, etc you should now be able to get that data into your navigation graph and get back a valid path that connects any two points.

In the next (and final) post in the series we'll put it all together and discuss some strategies to actually use the navigation data that we get back from the graph search algorithm.