The worst pathfinding bug I ever dealt with involved a door. Just a regular door in a stealth game. Characters would calculate paths through it when it was open, start walking, and then the player would close it mid-route. The characters would stop, frozen in confusion, because their path suddenly intersected with a solid object that hadn’t existed when they planned their route. We needed dynamic pathfinding, and we needed it yesterday.
Dynamic pathfinding is navigation that adapts to changing environments in real-time. Unlike static pathfinding where the world stays the same, dynamic systems handle doors opening and closing, bridges collapsing, walls being destroyed, furniture being moved, and other AI characters blocking paths. It’s the difference between navigating a photograph and navigating actual reality.
Why Static Pathfinding Falls Short
Most pathfinding implementations assume a static world. You generate a navigation mesh or grid once, then characters find paths through it. This works beautifully for games where environments don’t change think classic RPGs or strategy games with fixed maps.
But modern games are increasingly dynamic. Players build structures, destroy walls, open shortcuts, trigger environmental hazards. NPCs themselves change the world by opening doors, moving objects, or just standing in doorways. None of this fits the static pathfinding model.
I learned this working on a third-person action game where players could knock over heavy objects to create barricades or clear paths. We’d initially done all pathfinding on a static navmesh generated at level load. The first time a player toppled a bookshelf to block pursuing enemies, those enemies ran straight into the bookshelf trying to follow their pre-calculated paths. They looked incredibly stupid, and playtesters rightfully called it out.
The Core Challenges
The fundamental problem is that pathfinding is expensive. Running A* across a navigation mesh for one character might take 0.5-2ms depending on path length and complexity. Do that for ten characters every frame and you’ve blown your entire performance budget. Now imagine recalculating all active paths every time anything changes in the environment.
Invalidation detection is the first hurdle. How do you know when a path is no longer valid? The naive approach is checking every path against every environmental change, which scales terribly. You need spatial data structures grids, quadtrees, or similar to quickly identify which characters’ paths are affected by a specific change.
Re-pathing frequency becomes a balancing act. Re-calculate too often and performance tanks. Re-calculate too rarely and characters walk into obstacles. The sweet spot varies by game type. A fast-paced shooter might need aggressive re-pathing; a slower tactical game can afford delays.
The moving obstacle problem is particularly nasty. Other AI characters are obstacles, but they’re constantly moving. Treat them as navigation obstacles and you’re updating the navmesh dozens of times per second, which is completely impractical. Ignore them and characters path through each other.
Practical Approaches That Work
Temporary navmesh obstacles are my go-to for most dynamic elements. Instead of regenerating the entire navigation mesh when a door closes, you place a temporary obstacle that marks that area as unwalkable. Most engines (Unity, Unreal) support this with minimal performance cost.
The workflow looks like: door closes → place navmesh obstacle → mark nearby paths as potentially invalid → affected characters request re-paths. This is fast because you’re not rebuilding geometry, just flagging regions as blocked.
I’ve used this successfully for doors, destructible props, and temporary hazards. The limitation is that obstacles only block existing navmesh areas they don’t add new walkable space. For that, you need actual navmesh regeneration.
Runtime navmesh updates are necessary when the environment fundamentally changes geometry. A wall gets destroyed, creating a new passage. A bridge collapses, removing a path. These require rebuilding parts of the navmesh.
Modern engines support tiled navmeshes where the world divides into regions that can be rebuilt independently. Destroy a wall and you rebuild just the affected tiles rather than the entire level. On a good day, this completes in 50-200ms. Still expensive, but manageable if it doesn’t happen constantly.
I worked on a tower defense game where players built walls and towers, fundamentally changing pathfinding for enemy waves. We used tiled navmeshes with aggressive caching if a player built the exact same wall configuration we’d seen before, we reused the cached navmesh for that tile. This cut update times by 60% in practice.
Path validation and repair is a lighter-weight alternative. Characters periodically check if their current path is still valid. If a section is blocked, they try local path repairs find a nearby waypoint that’s still reachable and path from there. Only if repair fails do they request a full re-path.
This works surprisingly well for minor obstacles. A character’s path gets partially blocked, they route around the obstacle locally, and continue toward their goal without expensive full pathfinding.
Handling Moving Characters
Other AI characters are the most common dynamic obstacles, and treating them specially makes sense. Most games use local avoidance separate from pathfinding. Characters follow their navigation paths but apply steering forces to avoid others in real-time.
RVO (Reciprocal Velocity Obstacles) and ORCA (Optimal Reciprocal Collision Avoidance) are popular algorithms for this. Characters predict where others will be based on current velocities and adjust their movement to avoid collisions. It’s not perfect you get occasional bunching and jittering but it’s far cheaper than treating every character as a navmesh obstacle.
For critical bottlenecks like doorways or narrow corridors, I’ve implemented path reservation systems. Characters “claim” these choke points, and others wait for them to clear. This prevents the realistic but annoying scenario where four characters try to squeeze through a door simultaneously and get stuck.
The reservation system adds complexity what if a character dies while holding a reservation? What if they get distracted and never reach the reserved area? You need timeout and fallback logic. But when tuned properly, it makes navigation through tight spaces look coordinated rather than chaotic.
Smart Invalidation and Priority
Not all paths need immediate recalculation when something changes. A character following a path 100 meters from a closed door doesn’t need to re-path right away. They won’t reach that door for 30+ seconds plenty of time to defer the recalculation.
I use priority queuing for re-path requests. High priority: characters near the player, characters in active combat, characters whose paths are completely blocked. Low priority: background characters far from the player, characters who haven’t started moving yet.
Process high-priority re-paths immediately (within a frame or two). Low-priority ones get processed when CPU budget allows, potentially taking several seconds. Players rarely notice if a distant character takes a while to react to environmental changes.
Spatial queries keep invalidation checks efficient. When a door closes, query which paths pass through that spatial region. Only those paths get invalidated. This requires maintaining spatial indices of active paths, which adds overhead, but it’s worth it to avoid checking every path against every change.
Performance Reality Check
Even with optimization, dynamic pathfinding costs more than static. You’re trading CPU time for behavioral flexibility. This is fine if your game needs it, but don’t add dynamic pathfinding just because it sounds cool.
A stealth game where guards patrol between rooms with doors that open and close? Absolutely needs it. A platformer where enemies follow simple patrol patterns? Static pathfinding is probably enough.
I’ve seen teams add dynamic pathfinding “just in case” and then wonder why AI performance is mediocre. The overhead isn’t just in the pathfinding itself it’s in the invalidation checks, priority queues, spatial indices, and all the bookkeeping required to make it work smoothly.
Profile before and after. Measure the actual cost. Make informed decisions.
Debugging Dynamic Systems
Dynamic pathfinding is significantly harder to debug than static. The bugs are often timing-dependent they happen when a character is exactly here when a door closes at exactly this moment. Non-deterministic and frustrating.
Replay systems saved my sanity more than once. Record all environmental changes and character positions, then replay problematic scenarios step-by-step. This makes the non-deterministic deterministic and lets you actually debug it.
Visualization is even more critical than with static pathfinding. I draw paths, mark invalid waypoints in red, show re-path requests as they happen, and display spatial query regions. Without this, you’re flying blind.
Keep metrics on re-pathing frequency. If characters are re-calculating paths every few frames, something’s wrong either your invalidation is too aggressive or your environment is changing too chaotically for pathfinding to keep up.
Where Things Are Headed
We’re seeing more sophisticated dynamic pathfinding as hardware improves. Some games are experimenting with continuous re-planning where characters always have slightly stale paths but are constantly recalculating in the background at low priority.
Machine learning approaches are being researched for dynamic environments, training networks to navigate around unforeseen obstacles. Still mostly academic research rather than shipped games, but interesting to watch.
The push toward destructible environments in AAA games means dynamic pathfinding is becoming less optional. If your marketing shows players blowing holes in walls to create shortcuts, your AI needs to navigate that same dynamic world credibly.
Wrapping Up
Dynamic pathfinding transforms game AI from navigating a static maze to navigating a living world. It’s more complex, more expensive, and harder to debug than static pathfinding. But when your game world changes—whether through player actions, scripted events, or emergent gameplay it’s absolutely necessary.
Start with static pathfinding and add dynamic capabilities only where needed. Use temporary obstacles for simple cases and reserve full navmesh updates for substantial changes. Prioritize re-pathing ruthlessly and profile constantly.
When it works well, players don’t notice it. Characters just naturally navigate whatever situation emerges, making the AI feel competent and believable. That’s worth the implementation effort.
Frequently Asked Questions
What’s the difference between static and dynamic pathfinding?
Static pathfinding assumes the environment doesn’t change after initial setup. Dynamic pathfinding handles changing environments doors, destruction, moving obstacles by updating navigation data and recalculating paths.
How expensive is dynamic pathfinding?
Significantly more expensive than static. Expect 2-5x overhead from invalidation checks, re-pathing, and navmesh updates. Exact cost depends on how frequently the environment changes.
How often should paths be recalculated?
Depends on game pace and how critical the character is. Important characters near the player might re-path every 0.5-1 second. Background characters can defer re-pathing for several seconds.
Can dynamic pathfinding handle destructible environments?
Yes, but it requires runtime navmesh regeneration which is expensive. Tiled navmeshes help by only rebuilding affected areas. Expect 50-200ms updates for moderate complexity.
How do you handle other characters as obstacles?
Usually through local avoidance algorithms (RVO/ORCA) separate from pathfinding rather than treating them as navmesh obstacles. This is much more performant for moving obstacles.