How to build a platformer AI: From low-level trajectories to high-level behaviors

• Part 1: Basic movement
• Part 2: AI, graphs, and surfaces
• Part 3: Calculating jump trajectories
• Part 4: The platform graph and navigation
• Part 5: Character behaviors

Overview

In this series of posts, I describe techniques for implementing AI, pathfinding, and character movement in 2D platformers. I start out by covering some general mechanics of platformers. Then I describe a series of powerful abstraction layers built on top of these basics.

I make references to the Surfacer framework for real-world examples of these techniques. Surfacer is a procedural pathfinding 2D-platformer framework for Godot. It makes it easy to create point-and-click platformer games and to define high-level NPC behaviors.

Although Surfacer is written for Godot, the techniques we discuss in this series are not specific to Godot, and will work in any game engine of your choice!

tl;dr:

This AI works by pre-parsing a level into a "platform graph". The nodes are represented by points along the different surfaces in the level (floors, walls, and ceilings). The edges are represented by possible movement trajectories between points along surfaces. There are different types of edges for different types of movement (e.g., jumping from a floor to a floor, falling from a wall, walking along a floor). At run time, A* search is used to calculate a path to a given destination.

But why?

Because there aren't many other tools out there for intelligent pathfinding in a platformer.

The vast majority of platformers use pretty simple NPC AI for movement. For example:

• Walk to edge, turn around, repeat.
• Jump continuously, moving forward.
• Move with a regular bounce or surface-following pattern.
• Move horizontally toward the player character, "floating" vertically as needed in order to move around obstacles and platforms.

Most examples of more sophisticated AI pathfinding behavior are still pretty limited. One common technique uses machine-learning and is trained by hundreds to thousands of human-generated jumps on an explicit pre-fabricated level. This makes level-generation difficult and is not flexible to dynamic platform creation/movement.

There are two key reasons why good path-finding AI isn't really used in platformers:

1. It's hard to implement right; there is a lot of math involved, and there are a lot of different edge cases to account for.
2. Dumb AI is often effective on its own to create compelling gameplay. The player often doesn't really notice or care how simple the behavior is.

But there are use-cases for which we really benefit from an AI that can accurately imitate the same movement mechanics of the character. One example is if we want to be able to control the character by tapping on locations that they should move toward through the level. Another example is if we want to have a flexible game mode in which an NPC can swap-in for a player character depending on how many players are present.

What makes this strategy different?

The AI strategy uses an algorithmic approach to calculate trajectories for movement between surfaces. The algorithms used rely heavily on the classic one-dimensional equations of motion for constant acceleration. These trajectories are calculated to match the same abilities and limitations that would be exhibited by corresponding player-controlled movement. After the trajectory for an edge is calculated, it is translated into a simple instruction start/end sequence that will reproduce the calculated trajectory. These instructions emulate what would be triggered by a human player with controller input.

Trade-offs

Pros

• Being able to use graph-traversal algorithms gives us a lot of control for making intelligent NPC behaviors.
• Otherwise, we might have to resort to naïve heuristics, like jumping in the intended direction and hoping that there will be a reachable surface.
• This emulates the same movement mechanics that a human player could produce.
• This means that we could do things like swap-in an AI for a co-op game, when the player doesn't have a friend to play with.
• This also lets us simplify many parts of our codebase, since player-controls and AI-controls can be treated the same way.
• This gives us more control, predictability, and editability than would be possible with a machine-learning approach.

Cons

• Each edge in the level must be calculated ahead of time.
• And there can be quite a lot of edges in a level!
• For every pair of surfaces, we could calculate up to eight edges.
• Although, we ignore edge pairs that are too far apart.
• And most close-enough edge-pairs would only consider a couple potential edges.
• And, this means that we can't move platforms around or make changes to the level terrain at runtime!
• Although, we can at least get some of this flexibility back with a dynamic surface-exclusion list.
• Edges are expensive to compute.
• For each potential edge, we need to call our game engine's collision-detection API for each frame of the edge's proposed trajectory.
• This is compounded by the fact that each type of character might need to have different movement parameters (such as jump height and walk speed), and an additional platform graph must be calculated and stored for each different set of movement parameters.
• The platform graph can potentially be quite large.
• This can take a lot of RAM to load at runtime, which can have an impact on performance on some devices or browsers.
• We can work around this by pruning potential branches of our graph when we design our levels.
• This is quite complex to implement!

Contents

Part 1: Basic movement

• How an animation frame loop and physics engine work.
• General platformer mechanics.
• Surfacer's extensible action-handler system.

Part 2: AI, graphs, and surfaces

• How AI movement usually works.
• How to represent a platformer level as a graph.
• How to parse Godot tile-maps into their constituent surfaces—floors, walls, ceilings.

Part 3: Calculating jump trajectories

• Some trade-offs of this approach.
• How to decide on "good" jump and land positions for a pair of surfaces.
• How to handle start velocity.
• Separating the vertical component of motion from the horizontal component.
• Detecting collisions with intermediate surfaces.
• Calculating "waypoints" to move around intermediate surfaces.
• Backtracking to consider a higher max jump height.

Part 4: The platform graph and navigation

• How to construct a platform graph.
• Nodes as positions along surfaces.
• Edges as movement from one position to another.
• Handling platform immutability.
• Navigating through the platform graph to an arbitrary position.
• Optimizing edge trajectories at run-time for a more organic composite trajectory.
• Executing playback of edge instructions.
• Correcting for runtime vs build-time trajectory discrepancies.

Part 5: Character behaviors

• General-purpose behavior types
• Wander
• Move back-and-forth
• Climb adjacent surfaces
• Run away
• Collide
• Follow
• Choreography
• Return
• A behavior's "move target"
• General behavior parameters
• Bounciness
• Don't move too far away
• Pause between navigations
• Return afterward
• Transitioning between behaviors

Part 1: Basic movement →