Using RVO for Game AI Pedestrian Steering

This article explores how game artificial intelligence engineers implement Reciprocal Velocity Obstacles (RVO) to achieve smooth, collision-free crowd navigation. It details the transition from traditional Velocity Obstacles to reciprocal formulations, the underlying mathematics of Optimal Reciprocal Collision Avoidance (ORCA), the step-by-step technical pipeline for game engine integration, and techniques for overcoming common edge cases such as static environment collisions and asymmetric agent behaviors.

The Limitation of Traditional Avoidance

Early game AI navigation relied heavily on Reynolds steering behaviors or standard Velocity Obstacles (VO). Under a standard VO framework, an agent predicts future collisions by mapping all relative velocities that will lead to an intersection with an obstacle within a specific time window.

However, standard VO assumes other dynamic entities maintain a constant velocity and do not actively evade. When two agents run VO simultaneously, both choose a new avoidance velocity at the same time. In the next frame, each observes the other's sudden movement and recalculates, resulting in rapid back-and-forth oscillations—often referred to as the "reciprocal dance."

The Core Concept of Reciprocity

Reciprocal Velocity Obstacles solve oscillations by introducing shared responsibility. AI engineers treat collision avoidance as a cooperative mathematical problem:

  • Equal Effort: If two agents are on a collision course, RVO mandates that each agent only changes its velocity by half of the amount required to avoid the collision.
  • Predictable Cooperation: Because Agent A assumes Agent B will take responsibility for 50% of the avoidance maneuver, Agent A does not overcompensate.
  • Velocity Selection: Instead of selecting a velocity completely outside the traditional velocity obstacle cone, an agent selects a velocity that averages its current velocity with a collision-free velocity, creating smooth trajectories.

Implementation via ORCA (Optimal Reciprocal Collision Avoidance)

In modern production environments, engineers typically deploy Optimal Reciprocal Collision Avoidance (ORCA), an optimized extension of RVO formulated around linear programming.

  1. Velocity Space Constraints: For each neighboring dynamic agent, ORCA computes the minimal velocity change needed to prevent a collision within a designated time horizon (\(\tau\)).
  2. Half-Plane Formulation: This avoidance vector defines a linear constraint—a half-plane in 2D velocity space. Any velocity inside this half-plane guarantees collision avoidance with that specific neighbor.
  3. Linear Programming Optimization: The agent has a desired velocity derived from high-level pathfinding (such as an A* search on a NavMesh). The system uses 2D linear programming to find a new velocity that is as close as possible to the desired velocity while respecting the intersection of all neighbor half-planes.
  4. Execution Speed: Because 2D linear programming can be solved in linear time \(O(n)\) relative to the number of neighbors, ORCA runs efficiently on main game threads, easily handling hundreds of simulated pedestrians per frame.

The Engineering Pipeline in Game Engines

Integrating RVO/ORCA into engines like Unreal Engine, Unity, or custom proprietary frameworks follows a structured per-frame execution pipeline:

  • Spatial Partitioning: Avoid checking every agent against every other agent (\(O(n^2)\) complexity). Engineers query nearby entities using spatial hashing, uniform grids, or k-d trees to identify relevant dynamic neighbors within an interaction radius.
  • Global Path Planning: Global navigation systems (NavMesh) compute the path waypoints, producing a raw, unconstrained target velocity directed toward the immediate waypoint.
  • Local Avoidance Execution: The RVO solver collects dynamic neighbor positions, velocities, and bounding radii, then executes linear programming to compute an optimal, collision-free local velocity.
  • Locomotion and Blending: The generated velocity vector is passed to character movement components or root-motion controllers. Acceleration limits and turning rates are applied to prevent agents from instantaneously snapping to new headings, ensuring animations remain physically plausible.

Handling Real-World Production Challenges

Standard RVO formulations assume identical, circular agents moving on a flat plane. Game engineers apply several practical modifications:

  • Asymmetric Responsibility: VIP characters, heavy vehicles, or aggressive enemies should not yield equally to standard pedestrians. Engineers assign weights to the reciprocal sharing factor, allowing an agent to take anywhere from 0% to 100% of the avoidance responsibility.
  • Static Obstacles: While RVO natively targets dynamic agents, static geometry (walls, props) cannot share avoidance. Engineers map static navigation mesh boundaries as non-reciprocal obstacles, forcing the agent to assume 100% of the avoidance burden when near environmental limits.
  • High-Density Deadlocks: In extremely dense crowds or narrow doorways, valid velocity half-planes can conflict completely, leaving no feasible solution. When the linear program fails, the solver drops into a fallback routine that minimizes constraint penetration, allowing agents to decelerate gracefully, slide along boundaries, or yield based on priority values until space opens up.