Advertisement
  1. Game Development
  2. Pathfinding
Gamedevelopment

A* Pathfinding for 2D Grid-Based Platformers: Ledge Grabbing

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called How to Adapt A* Pathfinding to a 2D Grid-Based Platformer.
A* Pathfinding for 2D Grid-Based Platformers: Making a Bot Follow the Path

In this part of our series on adapting the A* pathfinding algorithm to platformers, we'll introduce a new mechanic to the character: ledge grabbing. We'll also make appropriate changes to both the pathfinding algorithm and the bot AI, so they can make use of the improved mobility.

Demo

You can play the Unity demo, or the WebGL version (16MB), to see the final result in action. Use WASD to move the character, left-click on a spot to find a path you can follow to get there, right-click a cell to toggle the ground at that point, middle-click to place a one-way platform, and click-and-drag the sliders to change their values.

Ledge Grabbing Mechanics

Controls Overview

Let's first take a look at how the ledge grabbing mechanic works in the demo to get some insight into how we should change our pathfinding algorithm to take this new mechanic into account.

The controls for ledge grabbing are quite simple: if the character is right next to a ledge while falling, and the player presses the left or right directional key to move them towards that ledge, then when character is at the right position, it will grab the ledge.

Once the character is grabbing a ledge, the player has two options: they can either jump up or drop down. Jumping works as normal; the player presses the jump key and the jump's force is identical to the force applied when jumping from the ground. Dropping down is done by pressing the down button (S), or the directional keyn that points away from the ledge.

Implementing the Controls

Let's go over how the ledge grab controls work in the code. The first thing here to do is to detect whether the ledge is to the left or to the right of the character:

We can use that information to determine whether the character is supposed to drop off the ledge. As you can see, to drop down, the player needs to either:

  • press the down button,
  • press the left button when we're grabbing a ledge on the right, or
  • press the right button when we're grabbing a ledge on the left.

There's a small caveat here. Consider a situation when we're holding the down button and the right button, when the character is holding onto a ledge to the right. It'll result in the following situation:

The problem here is that the character grabs the ledge immediately after it lets go of it. 

A simple solution to this is to lock movement towards the ledge for a couple frames after we dropped off the ledge. That's what the following snippet does:

After this, we change the state of the character to Jump, which will handle the jump physics:

Finally, if the character didn't drop from the ledge we check whether the jump key has been pressed; if so, we set the jump's vertical speed and change the state:

Detecting a Ledge Grab Point

Let's look at how we determine whether a ledge can be grabbed. We use a few hotspots around the edge of the character:

The yellow contour represents the character's bounds. The red segments represent the wall sensors; these are used to handle the character physics. The blue segments represent where our character can grab a ledge.

To determine whether the character can grab a ledge, our code constantly checks the side it is moving towards. It's looking for an empty tile at the top of the blue segment, and then a solid tile below it which the character can grab onto. 

Note: ledge grabbing is locked off if the character is jumping up. This can be easily noticed in the demo and in the animation in the Controls Overview section.

The main problem with this method is that if our character falls at a high speed, it's easy to miss a window in which it can grab a ledge. We can solve this by looking up all the tiles starting from the previous frame's position to the current frame's in search of any empty tile above a solid one. If one such tile is found, then it can be grabbed.

Now we've cleared up how the ledge grabbing mechanic works, let's see how to incorporate it into our pathfinding algorithm.

Pathfinder Changes

Make It Possible to Turn Ledge Grabbing On and Off

First of all, let's add a new parameter to our FindPath function that indicates whether the pathfinder should consider grabbing ledges. We'll name it useLedges:

Detect Ledge Grab Nodes

Conditions

Now we need to modify the function to detect whether a particular node can be used for ledge grabbing. We can do that after checking whether the node is an "on ground" node or an "at ceiling" node, because in either case it cannot be used for ledge grabbing.

All right: now we need to figure out when a node should be considered a ledge grabbing node. For cliarity, here's a diagram that shows some example ledge grabbing positions:

...and here's how these might look in-game:

The top character sprites are stretched to show how this looks with characters of different sizes.

The red cells represent the checked nodes; together with the green cells, they represent the character in our algorithm. The top two situations show a 2x2 character grabbing ledges on the left and right respectively. The bottom two show the same thing, but the character's size here is 1x3 instead of 2x2.

As you can see, it should be fairly easy to detect these cases in the algorithm. The conditions for the ledge grab node will be as follows:

  1. There is a solid tile next to the top-right/top-left character tile.
  2. There is an empty tile above the found solid tile.
  3. There is no solid tile below the character (no need to grab ledges if on the ground).

Note that the third condition is already taken care of, since we check for the ledge grab node only if the character is not on ground.

First of all, let's check whether we actually want to detect ledge grabs:

Now let's check whether there is a tile to the right of the top-right character node:

And then, if above that tile there is an empty space:

Now we need to do the same thing for the left side:

There's one more thing we can optionally do, which is disable finding the ledge grab nodes if the falling speed is too high, so the path doesn't return some extreme ledge grabbing positions which would be hard to follow by the bot:

After all this, we can be sure that the found node is a ledge grab node.

Adding a Special Node

What do we when we find a ledge grab node? We need to set its jump value. 

Remember, the jump value is the number which represents which phase of the jump the character would be, if it reached this cell. If you need a recap on how the algorithm works, take another look at the theory article.

It seems that all we'd need to do is to set the jump value of the node to 0, because from the ledge grabbing point the character can effectively reset a jump, as if it were on the ground—but there are a couple points to consider here. 

  • First, it would be nice if we could tell at a glance whether the node is a ledge grab node or not: this will be immensely helpful when creating a bot behaviour and also when filtering the nodes. 
  • Second, usually jumping from the ground can be executed from whichever point would be most suitable on a particular tile, but when jumping from a ledge grab, the character is stuck to a particular position and unable to do anything but start falling or jump upwards.

Considering those caveats, we'll add a special jump value for the ledge grab nodes. It doesn't really matter what this value is, but it's a good idea to make it negative, since that will lower our chances of misinterpreting the node.

Now let's assign this value when we detect a ledge grab node:

Making cLedgeGrabJumpValue negative will have an effect on the node cost calculation—it will make the algorithm prefer to use ledges rather than skip them. There are two things to note here:

  1. Ledge grab points offer a greater possibility of movement than any other in-air nodes, because the character can jump again by using them; from this point of view, it is a good thing that these nodes will be cheaper than others. 
  2. Grabbing too many ledges often leads to unnatural movement, because usually players don't use ledge grabs unless they are necessary to reach somewhere.

In the animation above, you can see the difference between moving up when ledges are preferred and when they are not.

For now we'll leave the cost calculation as it is, but it is fairly easy to modify it, to make ledge nodes more expensive.

Modify the Jump Value When Jumping or Dropping From a Ledge

Now we need to adjust the jump values for the nodes that start from the ledge grab point. We need to do this because jumping from a ledge grab position is quite different than jumping from a ground. There's very little freedom when jumping from a ledge, because the character is fixed to a particular point. 

When on the ground, the character can move freely left or right and jump at the most suitable moment.

First, let's set the case when the character drops down from a ledge grab:

As you can see, the new jump length is a bit bigger if the character dropped from a ledge: this way we compensate for the lack of manoeuvrability while grabbing a ledge, which will result in a higher vertical speed before the player can reach other nodes.

Next is the case where the character drops to one side from grabbing a ledge:

All we need to do is to set the jump value to the falling value.

Ignore More Nodes

We need to add a couple of additional conditions for when we need to ignore nodes. 

First of all, when we're jumping from a ledge grab position, we need to go up, not to the side. This works similarly to simply jumping from the ground. The vertical speed is much higher than the possible horizontal speed at this point, and we need to model this fact in the algorithm:

If we want to allow dropping from the ledge to the opposite side like this:

Then we need to edit the condition that doesn't allow horizontal movement when the jump value is odd. That's because, currently, our special ledge grab value is equal to -9, so it's only appropriate to exclude all negative numbers from this condition.

Update the Node Filter

Finally, let's move on to node filtering. All we need to do here is to add a condition for ledge grabbing nodes, so that we don't filter them out. We simply need to check if the node's jump value is equal to cLedgeGrabJumpValue:

The whole filtering looks like this now:

That's it—these are all the changes that we needed to make to update the pathfinding algorithm.

Bot Changes

Now that our path shows the spots at which a character can grab a ledge, let's modify the bot's behaviour so that it makes use of this data.

Stop Recalculating reachedX and reachedY

First of all, to make  things clearer in the bot, let's update the GetContext() function. The current problem with it is that reachedX and reachedY values are constantly recalculated, which removes some information about the context. These values are used to see whether the bot has already reached the target node on its x- and y-axes, respectively. (If you need a refresher on how this works, check out my tutorial about coding the bot.)

Let's simply change this so that if a character reaches the node on the x- or y-axis, then these values stay true as long as we don't move on to the next node.

To make this possible, we need to declare reachedX and reachedY as class members:

This means we no longer need to pass them to the GetContext() function:

With these changes, we also need to reset the variables manually whenever we start moving towards the next node. The first occurrence is when we've just found the path and are going to move towards the first node:

The second is when we've reached the current target node and want to move towards the next:

To stop recalculating the variables, we need to replace the following lines:

...with these, which will detect whether we've reached a node on an axis only if we haven't already reached it:

Of course, we also need to replace every other occurence of reachedX and reachedY with the newly declared versions mReachedNodeX and mReachedNodeY.

See If the Character Needs to Grab a Ledge

Let's declare a couple variables which we will use to determine whether the bot needs to grab a ledge, and, if so, which one:

mGrabsLedges is a flag that we pass to the algorithm to let it know whether it should find a path including the ledge grabs. mMustGrabLeftLedge and mMustGrabRightLedge will be used to determine whether the next node is a grab ledge, and whether the bot should grab the ledge to the left or to the right.

What we want to do now is create a function that, given a node, will be able to detect whether the character at that node will be able to grab a ledge. 

We'll need two functions for this: one will check if the character can grab a ledge on the left, and the other will check whether the character can grab a ledge on the right. These functions will work the same way as our pathfinding code for detecting ledges:

As you can see, we check whether there's a solid tile next to our character with an empty tile above it.

Now let's go to the GetContext() function, and assign the appropriate values to mMustGrabRightLedge and mMustGrabLeftLedge. We need to set them to true if the character is supposed to grab ledges at all (that is, if mGrabsLedges is true) and if there is a ledge to grab onto.

Note that we also don't want to grab ledges if the destination node is on the ground.

Update the Jump Values

As you may notice, the character's position when grabbing a ledge is slightly different to its position when standing just below it:

The ledge grabbing position is a bit higher than the standing position, even though these characters occupy the same node. This means that grabbing a ledge will require a slightly higher jump than just jumping on a platform, and we need to take this into account.

Let's look at the function which determines how long the jump button should be pressed:

First of all, we'll change the initial condition. The bot should be able to jump, not just from the ground, but also when it is grabbing a ledge:

Now we need to add a few more frames if it's jumping to grab a ledge. First of all, we need to know if it can actually do that, so let's create a function which will tell us whether the character can grab a ledge either to the left or right:

Now let's add a couple frames to the jump when the bot needs to grab a ledge:

As you can see, we prolong the jump by 4 frames, which should do the job fine in our case.

But there's one more thing we need to change here, which doesn't really have much to do with ledge grabbing. It fixes a case when the next node is the same height as the current one, but is not on the ground, and the node after that is in higher up, meaning a jump is necessary:

Implement the Movement Logic for Grabbing Onto and Dropping Off Ledges

We'll want to split the ledge grabbing logic into two phases: one for when the bot is still not near enough to the ledge to start grabbing, so we simply want to continue movement as usual, and one for when the boy can safely start moving towards it to grab it.

Let's start by declaring a Boolean which will indicate whether we have already moved to the second phase. We'll name it mCanGrabLedge:

Now we need to define conditions that will let the character move to the second phase. These are pretty simple:

  • The bot has already reached the goal node on the X axis.
  • The bot needs to grab either the left or right ledge.
  • If the bot moves towards the ledge, it will bump into a wall instead of going further.

All right, the first two conditions are very simple to check now because we've done all the work necessary already:

Now, the third condition we can separate into two parts. The first one will take care of the situation where the character moves towards the ledge from the bottom, and the second from the top. The conditions we want to set for the first case are:

  • The bot's current position is lower than the target position (it's approaching from the bottom).
  • The top of the character's bounding box is higher than the ledge tile height.

If the bot is approaching from the top, the conditions are as follows:

  • The bot's current position is higher than the target position (it's approaching from the top).
  • The difference between the character's position and the target position is less than the character's height.

Now let's combine all these and set the flag which indicates that we can safely move towards a ledge:

There's one more thing we want to do here, and that is to immediately start moving towards the ledge:

OK, now before this huge condition let's create a smaller one. This will basically be a simplified version for the movement when the bot is about to grab a ledge:

That's the main logic behind the ledge grabbing, but there's still a couple of things to do. 

We need to edit the condition in which we check whether it is OK to move to the next node. Currently, the condition looks like this:

Now we need to also move to the next node if the bot was ready to grab the ledge and then actually did so:

Handle Jumping and Dropping From the Ledge

Once the bot is on the ledge, it should be able to jump as normal, so let's add an additional condition to the jumping routine:

The next thing the bot needs to be able to do is gracefully drop off the ledge. With the current implementation it is very simple: if we're grabbing a ledge and we are not jumping, then obviously we need to drop from it!

That's it! Now the character is able to very smoothly leave the ledge grab position, no matter whether it needs to jump up or simply drop down.

Stop grabbing ledges all the time!

At the moment, the bot grabs every ledge it can, regardless of whether it makes sense to do so. 

One solution to this is to assign a large heuristic cost to the ledge grabs, so the algorithm prioritises against using them if it doesn't have to—but this would require our bot to have a bit more information about the nodes. Since all we pass to the bot is a list of points, we don't know whether the algorithm meant a particular node to be ledge grabbed or not; the bot assumes that if a ledge can be grabbed, the it surely should! 

We can implement a quick workaround for this behaviour: we will call the pathfinding function twice. The first time we'll call it with the useLedges parameter set to false, and the second time with it set to true.

Let's assign the first path as the path found without using any ledge grabs:

Now, if this path is not null, we need to copy the results to our path1 list, because when we call the pathfinder the second time, the result in the path will get overwritten.

Now let's call the pathfinder again, this time enabling the ledge grabs:

We'll assume that our final path is going to be the path with ledge grabs:

And right after this, let's verify our assumption. If we've found a path without ledge grabs, and that path is not much longer than the path using them, then we'll make the bot disable the ledge grabs.

Note that we measure the "length" of the path in node count, which can be quite inaccurate because of the node filtering process. It'd be much more accurate to calculate, for example, the Manhattan length of the path (|x1 - x2| + |y1 - y2| of each node), but since this whole method is more of a hack than a real solution, it's OK to use this kind of heuristic here.

The rest of the function follows as it was; the path is copied to the bot instance's buffer and it starts following it.

Summary

That's all for the tutorial! As you can see, it's not so difficult to extend the algorithm to add additional movement possibilities, but doing so definitely increases complexity and adds a few troublesome issues. 

Again, the lack of accuracy can bite us here more than once, especially when it comes to the falling movement—this is the area that needs the most improvement, but I've tried to make the algorithm match the physics as well as I can with the current set of values. 

All in all, the bot can traverse a level in a manner that would rival a lot of players, and I'm very pleased with that result!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.