Finding a path to an arbitrary point in a platformer

tl;dr: I talk about some graph theory and how I calculate a path to an arbitrary point.

Finding a path to a given point

A common task in the Surfacer framework is to find a path to a given destination. More specifically, to find a path through the platform graph that starts at the character's current position and ends at a position-along-a-surface that is reasonably close to some arbitrary 2D position.

The complicated bit I'm looking at right now is how to choose the destination point—that is, the "reasonably close position-along-a-surface."

The problem: Can we get to there from here?

Up 'til now, I've just been iterating through all possible surfaces and using whichever surface was closest. However, that has a big problem. What if there is no possible path from the character's current position to that surface?

Also, I'm now starting to think about scenarios where I want to be able to ensure that the character can also return to their starting position afterward, which means that I also need to be able to check that there will be a valid path through the platform graph from the intended destination back to the origin (e.g., if you have to fall a long way to reach the target, you might not be able to jump back up).

To fix this problem, I thought of three approaches.

Another problem: Dynamically excluding a surface

But first, let's talk about another problem I need to handle. I want to support toggling whether a given surface is active. This lets me make much more interesting levels and gameplay with surfaces that appear, disappear, "move", or need to be avoided due to some obstacle.

However, any time a surface is added or removed, it can completely change whether we can get from A to B. So I need to make sure my solution can handle dynamic surface exclusion.

Approach #1: "Brute force"

A "brute force" algorithm looks at all possible options in order to find the best one. This is usually very inefficient.

With this approach, I wouldn't have to change too much from what I'm doing now. Mostly, I would need to first sort all surfaces by their distance to the target position. Then I would iterate through each surface, from closest to furthest, check whether each surface is reachable, and return the first one that is.

This would be very inefficient! This would involve an expensive sort for the surface collection, as well as an expensive platform-graph traversal to check for each surface's connectivity ("reachability" from our starting surface).

Approach #2: Keep track of all the surfaces that can reach each other

With this approach, in graph-theory lingo, I would partition the platform graph into strongly-connected disjoint sets. This means that I would break the graph apart into separate groups, and each surface in a group would have some possible path to each other surface in that group.

I would do the partitioning of the graph at the start, when loading the level. It shouldn't be too expensive in time or space.

However, any time I changed the dynamic-surface-exclusion set, I would need to re-compute the entire graph partitioning. If the game doesn't toggle surfaces very often, then this might not be too big of a deal. But if surfaces are toggled often, then this would probably impact performance too much.

Also, even if surfaces aren't toggled often, when they are, it's possible we'd see jitter/lag on those frames.

Also, this strongly-connected partitioning doesn't handle the scenario when we might want to navigate to a surface and not care whether we can get back from it. In order to support this scenario, I'd probably need to maintain a separate set of weakly-connected surfaces from each individual surface. This would be expensive to compute and store.

Approach #3: Use a separate localized set for each character

With this approach, I'd store two separate sets for each character:

1. All the surfaces, within a given distance, that can be reached from the character's current surface.
2. All the surfaces, within a given distance, that can be reached reversibly from the character's current surface. That is, all the surfaces that can be reached and returned from.

I'd need to maintain separate sets for each character instance. And I'd need to update each set every time the character lands on a new surface. But this shouldn't be too expensive, since I'd use a distance threshold to limit the number of surfaces considered.

This approach would also require re-computing the sets any time a surface-exclusion is toggled. But again, this shouldn't be too expensive, since the sets are limited in scope.

In the end, I implemented this last approach.

🎉 Cheers!