Finding the way
Learning paths through this topic
Characters slip through the gap between two diagonal walls
Your hero finds a path, but it walks straight through a spot where two wall pieces only touch at their corners. Here is the one extra rule that stops this, and what it costs the route.
Make units walk around swamp and mud, but cross it when the detour is huge
Different ground should cost different effort, so roads get used and swamps get avoided. The catch is a shortcut in the search that quietly makes it return worse routes once the ground costs differ. Here is what to watch for.
One long route search freezes the whole game for a moment
On a big map a single search can take longer than a frame, and the screen hitches whenever someone clicks far away. Here is how to spread one search over many frames and still get exactly the same route at the end.
Let enemies smash through crates when that beats the long way round
A wooden barricade is either a solid wall to the search, so enemies walk around the whole level, or no obstacle at all, so they stand there. Here is how to price breaking through, which also tells the game when to smash and when to walk.
The player clicks on a wall or an island and the unit just stands there
When the target cannot be reached, most searches give up and nothing happens, which feels broken. Here is how to send the unit to the best spot it can really get to, and how to choose that spot fairly.
Route planning says there is no way, but the key is just behind you
Locked doors and keys make the same square worth visiting twice: once without the key, once with it. A normal search forbids that and gives up too early. Here is the small change that makes it find the real answer.
Make a patrolling enemy turn at the ledge instead of walking half off it
The guard marches along a platform and either drops off the end or hangs in the air with half its body over nothing. Here is where to look for the ground ahead, what happens on a platform too small for it, and why fast enemies can still skip a gap.
A fast patrolling enemy circles a waypoint it can never quite touch
The guard is meant to turn at each marker but overshoots, turns back, overshoots again and dances around it. Here is how to decide that a marker counts as reached, and how the route loops or swings back and forth without a hiccup.
The hook grabs an anchor behind a wall or one that pulls you backwards
When an AI character or an aim assist picks a grapple point, it takes the nearest one, even if a wall is in the way or it swings the character the wrong direction. Here is how to rate anchors by progress and by a line that is really clear.
The exit or boss room ends up right behind a wall from the start
A level generator puts the goal as far from the start as it can, and the player finds it a few steps through a door. Here is how to measure far in terms of walking, and how to place several things so they are spread out and not clumped.
Work out which platforms an enemy can jump to before it tries
Your chasing enemy leaps at ledges it can never reach, or ignores ones it easily could. Here is how to decide from the jump itself whether a gap is crossable, why a higher ledge is not simply a shorter jump, and how to leave room for error.
Find a way across a tile-based platformer level with jumps, ladders and drops
Ordinary pathfinding walks in four directions and knows nothing about gravity, so enemies float up walls or refuse to step off ledges. Here is a way to think about where a unit can stand, what moves lead from one standing spot to the next, and what each costs.