Finding the way
Learning paths through this topic
Fifty enemies chase the player and the game stutters from searching
Searching a route for every enemy every moment gets slow fast, yet they all want the same place. Here is how to do the heavy work once and let any number of units read their next step from it.
A vehicle or boss cuts corners or jitters when it follows a route
Steering at the next route point gives wobbling and sharp turns, steering at the nearest point never moves forward. Here is the aim point that gives smooth curves, and the one mistake that makes a route that passes near itself send the unit back.
Spread attackers around the player so they do not stack on one spot
Five enemies run at you and end up as one blob, shooting from the same pixel. Here is how to give each a place of its own around the target, how to keep them from crossing paths on the way, and what to do when the blob arrives from one side.
Pathfinding on a board of six-sided tiles gives odd distances and lopsided routes
Boards made of six-sided tiles do not work with the usual up, down, left, right thinking, and the distance rule you remember from squares gives wrong answers. Here is a coordinate system where counting steps just works.
A homing missile circles the target forever instead of hitting it
The missile turns toward you as fast as it can and still never lands, spinning around you like a moth. Here is why it happens, a quick test that says in advance whether a hit is even possible, and what the game can do about it.
An enemy keeps switching between two players at equal distance
With two possible targets about equally near, the enemy turns left, then right, then left again, and gets nowhere. Here is the small rule that makes it commit, when it is allowed to change its mind, and when it must drop a target for good.
Enemies hug the wall and get snagged on every corner they pass
The shortest route runs along the very edge of the walls, where bodies get stuck on corners and the player cannot see them coming. Here is how to make routes drift to the middle of a room while narrow passages still work.
Players get laps by driving over the line back and forth or the wrong way
A racing level counts a lap each time the car crosses the finish line, so wiggling over it, skipping half the track or driving backwards all count. Here is a rule for counting progress that cannot be gamed, and a warning for going the wrong way.
Find the throwing angle that lands a grenade exactly on the target
A thrown grenade falls short, flies over, or lands in front of the enemy on a ledge. Here is how to calculate the angle for a given throwing speed, why there are usually two good answers, and how a low ceiling decides between them.
An enemy runs for the health pack that is closest by air, behind a wall
Several pickups lie around and the units head for the one that looks nearest, then have to go all the way around. Here is how to choose by the real walk, how two enemies avoid fighting over the same one, and what happens when none can be reached.
Gunshots wake guards on the other side of a wall that no sound could pass
A shot goes off and every enemy within a circle turns around, including the ones in a sealed room next door. Here is how to let sound follow the corridors, get dulled by doors, and fade out, so only the guards that could hear it react.
Many routes are equally short, and the game picks the one with the most zigzags
On open ground there are hundreds of equally short ways to the same spot, and a plain search picks any of them, often a wobbly one. Here is how to make it prefer the neat, straight one without making the walk longer.