Demystifying 2D Platformer Pathfinding, Part 5

The final piece of the puzzle! We built up a nice navigation graph with ledge run-offs, one-way platforms and various types of jumps. We can query the data using our graph search algorithm and get back a path from our agent to the goal. Now we need to put that path to use and make our agent follow it.

The way I like to build my agents is to write the code entirely as if it would be controlled by a human. The only difference being that the controller/keyboard input is abstracted so that it can come from either the controller/keyboard or via code directly. This is a very flexible approach that lets you swap the agent control with ease.

Trim the Fat

The first thing we need to do with the navigation data we get back from the graph search algorithm is to trim the crud that isn't interesting. We will end up with a Node for each and every step along the way. For example, see the image below which is a path from the left-most Node to the right-most Node.

Notice that we have 7 navigation points on the first platform. We really only need the final Node in that series. We already know the start Node since that is where our agent is located and we really don't care about the 6 intermediate Nodes leading up to the end of the platform. They are all just connected Walkway Nodes in the direction of that final Node on the platform.

So, what we will want to do to clean up our path and provide us with an actionable list is to remove all Walkway Nodes that have a Walkway Node next in the path.

fixedPath = []

// we can skip the first node when cleaning the path since we are already there
for i in range( 1, navPath.length ):  
    // ignore any Walkways that are adjacent to other Walkways and the final Node.
    // We need the final Node just in case it happens to be a Walkway.
    if i < navPath.length - 1 and navPath[i].type == NodeType.Walkway:
        continue
    fixedPath.add( navPath[i] )

What we would end up with given the path in the image above is the following Nodes:

LedgeRight(11,6) -> Jump(14,4) -> Walkway(15,3)  

Now we have an actionable list of Nodes that we can follow. This path amounts to the following steps/actions:

  • run right to tile 11,6
  • jump to tile 14,4
  • run right to tile 15,3

Making Smarter Paths

In this series we kept things simple and went with a breadth first search. Breadth first search may work great for your game or it may not depending on the level layout and how you want your agent to move. For example, if you have jump Edges or other more complex movements all over the place you may want to upgrade your graph search algorithm to a weighted variant such as Dijkstra's algorithm. The change is trivial and just adds a weight factor to the Node.

struct Node:  
    int x
    int y
    int clearance
    NodeType type
    Node[] edges
    // weight/cost for this Node
    int weight = 0

This allows you to weight Nodes/Edges differently which will in turn make the graph search algorithm favor different paths. For example, Jump Edges can be given a higher weight which will cause the algorithm to prefer using Walkways. You can then play with the weights to shape the path the way you want them to be.

Using the Navigation Path

How you actually use the navigation path will highly depend not only on the data you put in the Nodes/Edges (remember that you can always stuff any data you want into a Node/Edge for use during navigation) but also how you setup your agent. The preprocessing we have done gives us a nice action list to work with. Each remaining Node/Edge lets us know what we need to do to get to it based on the NodeType/EdgeType. A pretty standard and flexible approach is to do the following:

  • generate a path. You can do this at any point which will depend entirely on your game. A fast paced game with smallish levels may generate new paths every second or two whereas a large, slower-paced level might only need to reevaluate the path every 5 - 10 seconds. You may even want to watch the target (usually the player) and whenever the target moves a certain distance generate a fresh path.
  • set the currentNode on your agent where currentNode is the first Node in the generated path. This will be the target that your agent will move towards.
    • if the currentNode is a simple Walkway apply input in the direction of the Node
    • if the currentNode is a JumpDownOneWay apply down input and jump input
    • if the currentNode is a RunOff apply input in the direction of the Node
    • if the currentNode is a JumpUpAndOver apply jump input and then at the peak of the jump (when y velocity switches sign) apply horizontal input
    • if the currentNode is a Jump apply jump and horizontal input
    • you get the idea by now what to do with your Nodes
  • check to see if the agent has reached Node.x. If so, release horizontal input.
  • check to see if the agent reached both Node.x and Node.y and that we are grounded. If so, set currentNode to be the next Node in the path if there is one else generate a fresh path.

Hmm. That looks a lot like a finite state machine, doesn't it? As it turns out an FSM is a fantastic way to consume a path. My personal preference is to have one state for each agent animation. It turns out the animations almost always map well to the actions an agent can perform: idle, run, jump, fall, etc. Before ticking the FSM the navigation checks above can be run and then the FSM can use the input just as if this were a living player controlling the agent.

But What if I'm Not Using a Tilemap?

We kept things simple here by using a tilemap for the explanation. If you have a free-flowing layout for your level the song remains the same. There are a few key bits that need to be tweaked to account for a non-tilemap environment but the algorithms are all nearly identical:

  • platform Nodes can be defined as just a LedgeLeft and a LedgeRight initially. This will give you one Node on each end of every platform. The line connecting them is all considered fair game but you'll notice it's a bit sparse. See below for how we remedy that.
  • when you simulate movement instead of getting an array of single-tile movement points use the minimum of your agents bounding box width/height. If you have particularly small obstacles (smaller than the bounding box width/height) then chop that number in half until your simulated movement size is smaller than your smallest obstacle.
  • when playing back the movement we can't just check to see if there is a solid tile present so instead query your level colliders for an overlap each time you step your simulated movement data.
  • once we get a collision below (i.e. we landed from a jump/fall) we do a check to see which two Ledge Nodes we landed between.
    • add a new Walkway Node at the landing point
    • kill the old Edge between the LedgeLeft and LedgeRight Nodes
    • add new Edges to link everything up. This is easiest visualized so see the image below for adding a new FallOff connection.

Conclusion

This series has a lot of data to digest, especially if you are new to graph search algorithms and more advanced navigation. We detailed a flexible way to generate a navigation graph that can be expanded upon to add any unique movement characteristics of your agents. We briefly touched on optimizing the path that the graph search algorithm returns and then wrapped it all up with one way to use the path. Despite this taking 5 posts, we have merely scratched the surface of 2D platformer pathfinding. From here on out the best way to take a deeper dive is to implement it and see what questions come up in the process then solve them one by one.