In part one, I gave a brief run down of the A* algorithm and how to implement for 2d, top-down pathfinding within a grid. I mentioned what a global solver is and how they differ from their counterpart, the local solver. Our A* algorithm will basically just provide us with our global solver. In a sense, it connects the dots, and our enemy AI will have differing local solvers that allow them to move between dots.

For part two, I am simply going to rework the way that we have our nodes setup so that they make more sense in a platformer context. The first thing that you’ll notice is that a platformer needs far less nodes. The enemies don’t need information for every single empty tile in the room. They just need markers that tell them when their paths are interrupted by pits, ladders, and other obstacles which may require them to do anything other than walk/run.

The graph is created by posting nodes at key locations across the map. Those locations are as follows:
-Ladder (top)
-Ladder (bottom)
-Platform (edge)
-Floor (jump launch point)
-Floor (jump land point)

We can add more variety later, if needed.

And honestly, that’s ALL we need to do. If the A* algorithm is still in place and we hand-stitch our list(s) of neighboring nodes together, everything should still work just fine. Here are a few examples.

Here you can see that an object needs to get from the top-left node to the node on the right side of a pit. In this case, the algorithm chose to move right along the platform and then jump down to the node below. We could change this by adjusting our heuristic. Perhaps the enemy is afraid of heights or takes fall damage. By adjusting our ‘H’ value, we could have that object decide to take the ladder down and hop across.

Again, the algorithm is pretty ballsy and is hopping across gaps and off of high platforms. This was intended, but could easily be changed if we didn’t like this maneuver. The simplest way to change this would be to remove that neighbor altogether. That way, the enemy wouldn’t even know that it could jump off of the platform. It would have to find a ladder.

Also note that on the second example the algorithm skips a node on the floor. This is because the neighbor to its left doesn’t need to know about it. It only needs to know how to jump down to the left or how to get to the ladder to its right. That skipped node only exists for jumping down from the far-right platform.

This is a super simple update, but it’s progress. We can now see where we’re headed. Next time we will adjust the heuristic so that objects can decide when to jump across pits versus when to use a ladder. Maybe we’ll balance urgency with risk of fall damage. Then onto the tough stuff: the local solver(s) and dynamically pairing neighbors.

Here is more of the top-left node searching for the node closest to the mouse cursor.

-Z