Demystifying 2D Platformer Pathfinding, Part 1

The amount of information on the web about 2D platformer pathfinding is dismal. This blog post series aims to fill the gap and provide enough information in enough detail to get you up and running. Part 1 will cover some required background information, mainly graph search algorithms.

Graph Search Algorithms

This is an area that I have found often really scares people. "Graph Search Algorithms" just sounds daunting. A* is by far the most popular of the algorithms and it's very name strikes fear into the hearts of those who hear it. This series isn't going to go deep into graph search algorithms but it will hopefully unhinge any fear of them.

With the prevalence of A* in the game dev world many don't even know other graph search algorithms exist. There are 3 main algorithms that I find myself using listed below in the order of complexity. I always use the least complex algorithm that will get the job done.

  • Breadth first search: also called flood fill because it works just like the flood fill tool in painting programs starting at a location and fanning out as far as it can in all directions
  • Dijkstra’s Algorithm: basically the same as breadth first search but with an added movement cost (think terrain, walking over pavement (low cost) vs grass (mid cost) vs mud (high cost))
  • A*: adding to Dijkstra's algorithm, A* not only takes into account cost but also uses a heuristic to help determine which node to visit next which often results in far less nodes needing to be searched

It is important to understand that graph search algorithms don't give a crap what the data they are operating on represents. The most common case being terrain/locations but they work equally well for random waypoints, dialogue trees, AI planners or any data at all that can be represented by a series of nodes and connections between them. Keep this in mind as you may find that graph search can be applied in many places that you would have never thought to use it.

Graph Search Algorithm Data

Let's take a look at the data structure required for graph search algorithms. We will keep things simple and stick to breadth first search here. It is a powerful and surprisingly simple algorithm. Once you understand it expanding to Dijkstra or A* is quite simple (adding a cost int for Dijkstra and then a heuristic to get to A*).

Nodes and Edges

Nodes and edges. That is all that graph search cares about. A dead simple example node that represents a char could look like this:

struct Node:  
    // the char that this Node represents
    char data;
    // all of the chars that we can get to from this Node
    char[] edges;

Using the Node structure you can create nodes for different chars and then create edges that connect the chars. You might end up with a series of chars that have edges between them as seen below (assume that a - or | means that there is an edge in both directions for simplicity. In reality edges can be either one way or both ways):

a - b - e  
|   |
c   d

nodeList = []  
nodeList.push( 'c', ['a'] ) // c -> a  
nodeList.push( 'a', ['c', 'b'] ) // a -> c and a -> b  
nodeList.push( 'b', ['a', 'd', 'e'] ) // b -> a, b -> d and b -> e  
nodeList.push( 'e', ['b'] ) // e -> b  
nodeList.push( 'd', ['b'] ) // d -> b  

With just this data a graph search algorithm can take in a starting location (char in this case) and a goal location and it will let you know how to get from start to goal. In pseudo code, a breadth first search implementation would look like this (and in C# it looks like this):

// create a queue to hold the nodes we will be searching and add the start node
frontier = Queue()  
frontier.enqueue( start )

// the cameFrom dictionary provides a way to trace from any node to the goal node
cameFrom = {}

// while we still have a node to search from
while !frontier.empty():  
    // dequeue the node and see if it is our goal
    currentNode = frontier.dequeue()

    // Success. found the goal.
    if currentNode == goal:
        return cameFrom

    // its not our goal so add all of the nodes edges/neighbors to the frontier so we can search them
    foreach nextNode in currentNode.edges:
        if not cameFrom.containsKey( nextNode ):
            frontier.enqueue( nextNode )
            cameFrom.add( nextNode, currentNode )

// didnt reach the goal, no valid solution
return null  

To reiterate: the data in a node is completely arbitrary. It could be chars, strings, ints, floats, tiles in a tilemap, waypoints, street corners or anything else that you want it to be. All the algorithm cares about is that there is some way to get the neighbors of a node (i.e. the edges).

We'll end this post with a real world example of what a node list could look like for a 2D platformer visualized in-game. In the image below nodes are represented by x,y tile coordinates. Each red/yellow/blue box is a node and it contains the letter 'E' followed by a number which is the number of edges that node connects to. The lines represent the edges (edges between two adjacent nodes are omitted for clarity). The colors of the lines represent the type of the edge:

  • dark green: jump from the source node to the destination
  • light green: jump down through a one way platformer
  • yellow: step off from the source node to the destination
  • blue: run off the ledge from the source node to the destination