Overlapping path finding regions

I found myself wanting to have stairs and walkways that appear on top of other walkable areas. I had avoided this up to this point because of issues with pathfinding.

While the A* algorithm I use for the actual path finding isn’t limited by two dimensions (it works with any node graph), the game world and base polygons I work with are 2d, and the library I’m using to combine and clip the polygons is 2d. You can find more information on this here.

Background

Consider the following room with a upper level walkway that appears in front of the stairs:

The player can be on the stairs or on the walkway. In the room script I need to track where they are based on where they entered the room and how they have crossed through the area near the top of the stairs. It’s reasonably straightforward to do this and ensure that the player character has the correct depth value (so he/she appears in front of behind the walkway).

If I want to describe the walkway areas for pathfinding, however, I end up with something like this:

If this were true 3d, this would probably work fine. However, in 2d a point where the polygon overlaps itself doesn’t really make sense. Is it on the walkway or on the stairs? Related, my clipping library turns this polygon into this:

Now it’s no longer ambiguous. However, we can freely walk between the stairs and the walkway without going through the upper stair landing.

I could possibly selectively place blockers depending if I detect the player is on the stairs or walkway. But that’s a lot of manual work, and I want a slightly more rigorous solution I can use in many rooms.

Pathfinding zones

My solution is to split the room into multiple pathfinding zones. Visually, this looks like:

Note that these have a small overlapping section near the top of the stairs. This is where we’ll transition between the two zones.

Along with this, I added the following functionality:

• Rooms no longer have a single set of polygons that define their boundaries. Instead, they have a set for each pathfinding “zone”
• Each actor (moving sprite) has a pathfinding zone number associated with it
• I introduced a “pathfinding triggers” concept – these define small regions of the room that actors can pass through that will take them into a new pathfinding zone (this is how the actor’s pathfinding zone number is kept up-to-date). In the example we’re using, these would lie on the edges of the small transition area between the zones.

In terms of movement, the room’s polygon boundaries are used for two functions:

1. To answer the question “can I be here?” for an actor. This is used when moving the player with the keyboard (or controller). In this case, I can simply choose the polygon for the pathfinding zone the actor is in, and make the query.
2. To be able to find a path from point A to point B. This is used for “click to move”, for moving NPCs from place to place, and also (importantly) when typing in a command that causes you to interact physically with an object (the game needs to move the player to the object).

For the second case, we have the problem that the target pathfinding zone might be different from the one we’re currently in.

To solve this, I extended the pathfinding logic like so:

• If the target position is in the same zone as the start, do things just as before.
• If the target position is in a different zone (B) than the start zone (A), find a transition point T between A and B. Then find a path from A to T, and then T to B. Combine the paths and use this as the result.

The transition point should be inside the overlapping areas of the two zones. To avoid unnatural paths, the transition area should be as small as possible.

So the manual work to support multiple pathfinding zones in a room is:

• Define the sets polygons for each zone (of course) – they must overlap a bit.
• Create triggers on each side of the overlapping transitions between zones – these could be anything (manual coordinate checks, polygons, or control colors). Currently I’m just using control colors, which is a bitmask built into the background. Associated with the triggers in code is the pathfinding zone number they assign to any actor passing through them.
• A transition point for transitions between any two zones.

I should in theory be able to support any number of zones per room, but currently I just support two. With a little bit of extra work, the pathfinding algorithm mentioned in case (2) above could be extended to n zones (in case you need to transition to an intermediate zone separate from the start and end zones).

Note also that “click to move” is still ambiguous, because all you have is a 2d point, and you are making assumptions about which zone it’s in. In practice this isn’t an issue though. It’s completely reasonable just to make it use the zone that the actor is currently in.