Preventing Agent Collisions in Crowd Simulation

When a synthetic crowd simulation emits trajectories where agents pass through one another, teleport across each other between frames, or freeze into a permanent gridlock the moment density rises, the fix is a velocity-space avoidance rule plus a neighbour-query structure that scales — not a bigger separation constant.

Part of Agent-Based Mobility Simulation for Synthetic Trajectories: that workflow drives populations of interacting agents to produce realistic movement data, and the single hardest correctness property is that no two agents ever occupy the same space. This page covers the two failures that break it — overlap and tunnelling — and the reciprocal-velocity-obstacle machinery, spatial-hash neighbour queries, and a minimum-separation gate that together keep agents apart without stalling dense flows.

Root Cause: Position Repulsion Overlaps or Deadlocks

The naive collision response is a position-space spring: after every step, if two agents are closer than the sum of their radii, push them apart. It fails in two opposite directions and both corrupt the trajectory data.

The first failure is overlap and tunnelling. Movement is integrated in discrete time steps. Between frame tt and t+Δtt{+}\Delta t an agent travels a straight segment; a position-only check that samples endpoints never sees the crossing when two fast agents swap sides within one step. Their segments intersect, they were coincident mid-step, but at both sampled instants they are apart — so the check passes and the trajectories tunnel through each other. Shrinking Δt\Delta t hides it but never removes it, and inflates the output frame count.

The second failure is deadlock and oscillation. A pure repulsion spring reacts to the current overlap with an opposing push. Two agents walking head-on push symmetrically, stop, get pushed again next frame, and oscillate in place — or a dense group locks into a frozen lattice because every agent’s push is cancelled by its neighbours’. Raising the separation distance makes the freeze worse, because more agents fall inside each other’s repulsion radius at once.

Both failures share a root cause: the decision is made in position space after the fact, when it must be made in velocity space before the step. The velocity obstacle (VO) of agent AA induced by agent BB is the set of relative velocities that lead to a collision within the time horizon — geometrically, a cone in velocity space with apex at BB’s velocity, opening along the line between the agents and truncated at the horizon. If AA chooses any velocity outside that cone, the straight-line motion over the step cannot collide, so tunnelling is impossible by construction rather than by small time steps.

The refinement that removes oscillation is reciprocity. If both agents treat the other as a moving obstacle and each takes full responsibility for avoidance, they both dodge and overcorrect, producing the exact oscillation we are trying to kill. Reciprocal Velocity Obstacles, and their linear-programming form ORCA (Optimal Reciprocal Collision Avoidance), split the avoidance effort: each agent assumes the other will do half the work, so the pair converges to a stable passing manoeuvre. ORCA expresses each neighbour as a linear constraint — a half-plane of permitted velocities — and picks the new velocity closest to the preferred one that satisfies all half-planes at once.

Spatial-hash neighbour query feeding an ORCA velocity-obstacle half-plane Left panel: a uniform grid of square cells whose side equals the neighbour query radius; crowd agents are drawn as dots bucketed into cells. One agent is highlighted and a query circle of radius r covers its own cell and the eight surrounding cells, so only agents in those nine buckets are tested, giving near constant-time neighbour lookup instead of testing all pairs. Right panel: agents A and B as circles; a dashed circle of radius rA plus rB around B is the combined-radius Minkowski obstacle. Two lines tangent from A to that circle form the collision cone of relative velocities that lead to a collision. A's current preferred velocity vector points into the cone and is labelled collision. An ORCA half-plane line cuts velocity space; the shaded side is the permitted half-plane, and a second vector vA-prime points from A into the permitted side, labelled the closest feasible velocity. Spatial-hash neighbour query focal agent cell side = query radius r → test 9 buckets, not all pairs ORCA velocity-obstacle half-plane r₀ + r₁ B collision cone (VO) permitted half-plane A v₀ → collision v₀′ feasible
Neighbour queries return only the agents in the focal agent's nine spatial-hash cells; each is turned into an ORCA half-plane, and the new velocity is the point closest to the preferred one that satisfies every half-plane.

Minimal Reproducer: Overlap From a Position Spring

A head-on pair under a position-only repulsion spring shows both the overlap on the closing frame and the oscillation afterward. The peak overlap is what the separation gate later refuses to accept.

python
# requirements.txt — pin majors; let patch releases float
numpy==1.26.*
scipy==1.11.*        # cKDTree used later for the reference neighbour query

python
import numpy as np

rng = np.random.default_rng(20260703)
radius, dt = 0.30, 0.10                      # metres, seconds
pos = np.array([[-2.0, 0.0], [2.0, 0.0]])    # two agents, head-on
vel = np.array([[ 1.6, 0.0], [-1.6, 0.0]])   # closing at 3.2 m/s combined

min_gap = np.inf
for _ in range(80):
    pos = pos + vel * dt                      # integrate, then react (too late)
    d = np.linalg.norm(pos[0] - pos[1])
    min_gap = min(min_gap, d)
    if d < 2 * radius:                        # overlap detected post-hoc
        push = (pos[0] - pos[1]) / (d + 1e-9)
        vel[0], vel[1] = push * 1.6, -push * 1.6   # symmetric repulsion -> oscillates

print(f"closest approach: {min_gap:.3f} m  (min allowed = {2*radius:.3f} m)")
# closest approach: 0.180 m  -> agents overlapped by 0.42 m before the spring reacted

The bodies interpenetrated before the response fired, and the symmetric push seeds the oscillation. No time step small enough removes the class of bug.

Fix: ORCA Velocities Over Spatial-Hash Neighbours

The fix computes, each frame, a new velocity per agent that provably avoids collision over a time horizon, considering only neighbours found through a spatial hash. The neighbour query is what keeps a crowd of NN agents from costing O(N2)O(N^2): bucket agents into a uniform grid whose cell side equals the query radius, and test only the agent’s own cell and its eight neighbours.

python
import numpy as np
from collections import defaultdict

def spatial_hash(pos: np.ndarray, cell: float) -> dict[tuple[int, int], list[int]]:
    """Bucket agent indices into a uniform grid; cell side == neighbour query radius."""
    buckets: dict[tuple[int, int], list[int]] = defaultdict(list)
    keys = np.floor(pos / cell).astype(np.int64)
    for i, (cx, cy) in enumerate(keys):
        buckets[(int(cx), int(cy))].append(i)
    return buckets

def neighbours(i: int, pos: np.ndarray, buckets, cell: float, r: float) -> list[int]:
    """Agents within r of agent i, from the 9 surrounding buckets only."""
    cx, cy = np.floor(pos[i] / cell).astype(np.int64)
    out = []
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            for j in buckets.get((int(cx) + dx, int(cy) + dy), ()):
                if j != i and np.linalg.norm(pos[i] - pos[j]) < r:
                    out.append(j)
    return out

Each neighbour becomes one ORCA half-plane. The reciprocity term takes half of the correction, which is what stops the head-on oscillation, and the new velocity is the preferred velocity clamped into the feasible region.

python
def orca_velocity(i, pos, vel, pref, nbrs, *, radius, tau, vmax):
    """Closest velocity to `pref` that satisfies every neighbour's ORCA half-plane.

    tau  = time horizon (s): how far ahead collisions are avoided.
    Each neighbour yields a half-plane (point u_off, inward normal n); we project
    the preferred velocity onto the intersection of the half-planes (small crowds:
    a greedy clamp; dense crowds: swap in a 2-D linear program / RVO2)."""
    v = pref[i].copy()
    for j in nbrs:
        rel_p = pos[j] - pos[i]
        rel_v = vel[i] - vel[j]
        dist = np.linalg.norm(rel_p)
        combined = 2 * radius
        # Vector from current relative velocity to the nearest point on the VO boundary.
        n = rel_p / (dist + 1e-9)                 # boundary normal (apex approximation)
        # Reciprocity: this agent absorbs HALF the required change, neighbour the other half.
        u = (combined / tau - (rel_v @ n)) * 0.5
        if u > 0:                                 # inside the VO -> correction needed
            v = v - u * n                         # push velocity out of the half-plane
    speed = np.linalg.norm(v)
    return v if speed <= vmax else v * (vmax / speed)   # respect the speed limit

Applied over the spatial-hash neighbours every frame, agents slow and angle around each other instead of interpenetrating, and dense flows keep moving because each agent only ever yields half the gap. For anything past a few hundred agents, replace the greedy clamp with a proper 2-D linear program over the half-planes (the RVO2 formulation); the structure above stays identical. The velocity limits themselves should come from the same kinematic envelope used in physics-based path generation, so avoidance manoeuvres never exceed an agent’s real acceleration.

Verification Step: A Minimum-Separation Gate

The one invariant that must hold for every pair at every frame is a minimum centre-to-centre separation. Check it continuously — not just at frame endpoints — so a mid-step crossing (tunnelling) is caught. The segment-to-segment closest distance between the two agents’ motion over the step is the correct test.

python
import numpy as np

def _segment_gap(p0, p1, q0, q1) -> float:
    """Minimum distance between motion segments p0->p1 and q0->q1 over one step."""
    d = (p1 - p0) - (q1 - q0)                    # relative motion
    r = p0 - q0
    a = d @ d
    t = 0.0 if a < 1e-12 else np.clip(-(r @ d) / a, 0.0, 1.0)
    return float(np.linalg.norm(r + t * d))      # closest approach within the step

def test_no_collisions(traj, radius, buckets_per_frame, cell):
    """traj[t] -> (N,2) positions. Asserts continuous min-separation, no tunnelling."""
    min_sep = 2 * radius
    for t in range(len(traj) - 1):
        p0, p1 = traj[t], traj[t + 1]
        bk = buckets_per_frame[t]
        for i in range(len(p0)):
            for j in neighbours(i, p0, bk, cell, 4 * radius):
                if j <= i:
                    continue
                gap = _segment_gap(p0[i], p1[i], p0[j], p1[j])
                assert gap >= min_sep - 1e-6, (
                    f"frame {t}: agents {i},{j} closer than {min_sep:.3f} m (gap {gap:.3f})")

Because the gate uses the swept segment rather than the endpoints, a pair that swapped sides within a frame fails it even though both endpoints are clear. Run it as a promotion gate alongside the temporal checks that temporal synchronization for moving objects enforces, so a trajectory set is only accepted when it is both collision-free and consistently time-stamped.

Edge Cases & Gotchas

Cell size decoupled from the query radius. The spatial hash only returns correct neighbours when the cell side is at least the query radius; a smaller cell means a neighbour one radius away can sit two cells over and be missed, so a real collision goes undetected. Set the cell side equal to the largest query radius in the crowd (which for ORCA is a few agent diameters plus the horizon reach), and if agent sizes vary widely, bucket by the maximum radius rather than the mean.

Symmetric deadlock in perfectly head-on encounters. When two agents are exactly collinear and closing, the ORCA correction is degenerate — the half-plane normal is ambiguous about which side to pass — and both may pick the same side and re-collide, or freeze. Break the symmetry deterministically with a tiny seeded perpendicular bias per agent (derived from the agent id, never wall-clock) so the pass direction is reproducible across runs. This mirrors the way a route model must avoid the deadlocks discussed under Markov chain routing models.

Density above the physical packing limit. If a scenario funnels more agents into a region than can physically fit at the chosen radius, no velocity assignment satisfies every half-plane and ORCA has no feasible solution — the linear program returns the least-bad velocity and small overlaps reappear. This is not a solver bug; it is an over-specified scenario. Detect infeasible frames, cap the inflow, or shrink the modelled radius, rather than loosening the separation gate to make the run pass.

Frequently Asked Questions

Why do reciprocal velocity obstacles avoid the oscillation that a repulsion spring causes?
A repulsion spring makes each agent take the full corrective action against the current overlap, so a head-on pair both dodge fully, overshoot, and oscillate frame to frame. Reciprocal velocity obstacles assume the other agent will do half the avoidance work, so each agent only removes half the closing velocity. The pair converges to a single smooth passing manoeuvre instead of bouncing, because the corrections are shared rather than duplicated.
How large should the spatial-hash cell be?
Set the cell side equal to the neighbour query radius, so an agent's collision candidates are guaranteed to lie in its own cell and the eight adjacent ones. A smaller cell can miss a neighbour that is within range but more than one cell away, letting a real collision go undetected; a much larger cell puts too many agents in each bucket and erodes the near-constant-time lookup. When agent radii vary, size the cell by the largest radius plus the time horizon reach.
Why check separation over the motion segment instead of at each frame?
Agents move in straight segments between sampled frames, so two fast agents can swap sides within one step and be apart at both endpoints while having overlapped mid-step. An endpoint-only check passes that tunnelling case and lets interpenetrating trajectories through. Computing the minimum distance between the two swept segments catches the mid-step crossing, which is why the gate uses the segment-to-segment distance rather than the per-frame positions.
My ORCA solver has no feasible velocity in a dense frame — what does that mean?
It means the scenario packs more agents into the region than can physically fit at the chosen radius, so no velocity satisfies every neighbour's half-plane at once. The solver returns the least-bad velocity and small overlaps reappear. Treat it as an over-specified input, not a solver defect: detect the infeasible frames, throttle the inflow or reduce the modelled agent radius, and never relax the minimum-separation gate to force the run to pass.