PreambleIf you're writing a "jump and run" style platformer game, you're probably thinking about adding some AI. This might constitute bad guys, good guys, something the player has to chase after etc... All too often, a programmer will forego intelligent AI for ease of implementation, and wind up with AI that just gives up when faced with a tricky jump, a nimble player, or some moving scenery. This article presents a technique to direct AI to any arbitrary static location on a map. The path an AI takes may utilize many well-timed jumps or moving scenery pieces, as long as it starts and ends in a stationary location (but this doesn't always have to be true). We'll cover the basic idea and get an implementation up and running. We'll cover advanced cases including moving platforms/destructible walls in a future article. This Technique is used in the game Nomera, at www.dotstarmoney.com or @DotStarMoney on Twitter.
Getting ReadyBefore we begin, it's good to have a working knowledge of mathematical graphs and graph traversal algorithms. You'll also need to be comfortable with vector maths for pre-processing and finding distances along surfaces. This technique applies to levels that are composed primarily of static level pieces with some moving scenery, and not levels that are constantly morphing on the fly. It's important to have access to the static level collision data as line segments; this simplifies things though this technique could easily be extended to support any geometric objects you use for collision.
The Big IdeaIn layman's terms: As a developer, you jump around in the level between platforms, and the engine records the inputs you use from the point you jump/fall off of a platform, until the time you stand on the next one. It counts this as an "edge," saving the recorded inputs. When an AI wants to path through the level, he treats the series of platforms (we'll call them nodes from here on out) as vertices, and the recorded edges between them as a graph. The AI then takes a path by alternating walking along nodes, and taking the recorded input along edges to reach a destination. There are many important distinctions we'll need to make, but for now, just focus on the broad concepts. The technique we'll use is a combination of two algorithms. These are, creating the pathing graph, or "creating the data structure AI will utilize to path through the level" and traversing the pathing graph, or "guiding the enemy through the level given a destination". Obviously the latter requires the former. Creating the pathing graph is summarized as follows as follows:
- Load the level static collision data and compute from it a series of nodes.
- Load any recorded edges (paths) for the level and add these to their respective start nodes.
- Using the enemy collision model and movement parameters, record paths between nodes and add these to the graph.
- When exiting the level, export the recorded edges for the level.
- Recieve a destination in the form of a destination node, and distance along that node; Calculate similar parameters for the source (starting) node.
- Compute a path, using any graph traversal algorithm from source to destination where the path is a series of nodes and edges.
- Guide the AI across a node to an edge by walking (or running, whatever the AI knows how to do) to reach the correct starting speed of the next edge in the path.
- Once the AI has reached the start location of the next edge in the path to some tolerance in both position and velocity, relinquish automatic control of the AI and begin control through the edges frame by frame recorded input.
- When recorded input ends, give control back to the automatic movement for whichever node upon which the AI stands.
- Repeat the last three steps until the destination has been reached
Implementing Pathfinding Step by Step
Creating the Pathing GraphThe pathing graph is made up of platforms/nodes, and connecting nodes to nodes are recordings/edges. It is important to first write hard definitions for what constitutes a platform, and what constitutes a recording. A node/platform has the following properties:
- It is a subset of the line segments forming the level geometry.
- Assuming normal gravity, all segments in the node are oriented such that their first vertex has a strictly smaller x coordinate than their second. (this would be reversed for inverted gravity)
- Each subsequent segment in the node starts where the last segment ended.
- Each segment in the node is traversable by an AI walking along its surface
- An edge has a start position, and destination position on two different nodes (though it could be the same node if you want to create on-platform jump shortcuts!)
- An edge has a series of recorded frame inputs that, provided to an AI in the edge starting position and starting velocity, will guide the AI to the position specified by the destination position