How to Prevent NPC Gridlocks at Doorways

In game development, non-player characters (NPCs) frequently create unnatural bottlenecks and deadlocks when simultaneously trying to pass through narrow doorways or tight choke points. This article explores the standard industry solutions used to resolve these pathfinding conflicts, detailing techniques such as spatial reservation systems, dynamic pathfinding costs, local steering avoidance, and structured queueing behaviors to keep agent movement fluid and believable.

Spatial Reservation and Mutex Volumes

A spatial reservation system treats the doorway as a mutually exclusive resource (a mutex) or limits it to a strict capacity. When an agent approaches a doorway, it must query the doorway's controller to claim a passage token. If another agent is already traversing the threshold, incoming agents are denied entry and must pause at a predefined wait node, yield, or select an alternative path until the active agent clears the exit volume.

Dynamic NavMesh Cost Modifiers

Static navigation meshes often cause multiple agents to calculate the exact same shortest path through a single door. By dynamically placing high-cost zones or temporary obstacles over doorways currently occupied by an agent, the pathfinding engine forces trailing agents to perceive the doorway as an expensive route. This encourages surrounding NPCs to either wait naturally further back or path around through adjacent rooms and corridors.

Reciprocal Velocity Obstacles (RVO) and ORCA

Global pathfinding only provides long-range waypoints; local steering behaviors handle real-time spatial negotiation. Implementing algorithms such as Reciprocal Velocity Obstacles (RVO) or Optimal Reciprocal Collision Avoidance (ORCA) allows agents to anticipate collisions frames in advance. In tight spaces, these algorithms compute a shared velocity adjustment, allowing agents traveling in opposite or perpendicular directions to smoothly bias their movement to the right or left without halting entirely.

Priority and Yield Hierarchies

Deadlocks commonly occur when two opposing agents face each other in an opening and neither yields. Assigning dynamic or static priority levels solves this problem. Factors like agent speed, health, role, or distance to the threshold determine priority. When a conflict is detected within a designated threshold zone:

• The lower-priority agent halts and enters a "sidestep" or "step-back" behavior.
• The higher-priority agent proceeds unimpeded.
• Once the zone is clear, the yielding agent resumes its path.

Lane Systems and One-Way Alternating Traffic

For areas with high traffic volumes, doorways can be divided into virtual lanes or programmed with alternating flow states:

• Directional Lanes: Splitting a doorway into "in" and "out" sub-paths ensures agents entering do not collide head-on with agents exiting.
• Traffic Light States: In extremely narrow single-file doors, the doorway alternates permission states based on demand, letting an entire group travelling in one direction clear out before reversing flow for opposing traffic.

Ghosting and Soft Collision Fallbacks

Even with robust logic, edge cases can cause agents to become physically wedged. As a fallback mechanism, developers frequently implement soft collisions or temporary depenetration forces. If an agent detects that its forward velocity has been zero for a prolonged period while attempting to navigate a choke point, collision checks between agents can be temporarily relaxed or an impulse force can be applied to nudge the agents apart until normal traversal resumes.