Finding the way
Learning paths through this topic
Teleporters break the route search and enemies walk past the shortcut
You add a pair of teleporters and the enemies still take the long walk, even though the portal is far quicker. The search was told a rule that portals break. Here is which one, and the one-line change that lets the shortcut win.
Units think about their route every moment and keep changing their mind
Searching again every moment wastes time and makes characters shuffle back and forth when something moves in their way. Here is a calm rule for when to keep walking, when to wait, and when a new search is really worth it.
Plan a trip to the item and back when the floor crumbles behind you
Two shortest routes put together, to the key and then to the door, will lead over tiles that have already fallen away. Here is how to plan one whole trip that never steps on the same tile twice, and when there is simply no such trip.
Choose the fastest route that does not kill the enemy with fall damage
Dropping down is quick, but every long fall costs health, and several small drops add up. Here is how to let characters take shortcuts only as long as they live through them, and why the cheapest total is not found by simply avoiding the worst fall.
Find the way across a whole building without searching every single tile
On a map made of many rooms joined by doors, searching tile by tile is wasteful, and the obvious shortcut of counting rooms picks the wrong route. Here is how to plan at the level of doors, and why that wins.
Make enemies search the places a vanished player could have reached
After losing sight of the player, the enemy either stands still or checks a perfect circle that includes the other side of walls. Here is how to work out the real set of hiding places from the time passed, and the order that looks natural.
In a wrap-around arena the enemy flies the long way round to reach you
When the left edge of the screen leads to the right edge, a chaser at one side still races across the whole screen to a player who is just past the other edge. Here is how to find the short direction, and what to do at exactly half way.
Pick the dodge direction that keeps the most distance from incoming bullets
A dodging enemy runs from a bullet and straight into the next one, or runs along the bullet's line and gets hit anyway. Here is how to score each possible move by how close the shots will come, with one calculation per bullet and no simulation.
Pick spawn points for enemy waves that are out of view but not far away
Enemies pop into existence in front of the player, or at a spot that is close on the map but a long trek through the level. Here is how to choose where a new wave appears so it is unseen, arrives in a sensible time, and never feels unfair.
Walking along a route looks like a staircase instead of a straight line
A route found on a grid turns at every cell, so characters wobble along it like they are on rails made of steps. Here is how to remove the needless turns without ever cutting through a wall.
Check where a rotated house may stand and tell the player every reason it may not
A ghost of the house follows the cursor and should turn red with a clear reason, not just refuse. Odd shapes turn around a corner, parts can hang over the edge, and the ground may not be flat. Here is a check that returns all the reasons at once.
Generate caves that look natural and still leave every tunnel reachable
Scattering stone at random and smoothing it gives pleasing caves, but also sealed pockets the player can never enter, with ore inside. Here is the smoothing rule, why it has to change all cells at once, and the final step that fixes the pockets.