The armies at Helm's Deep in The Lord of the Rings were not ten thousand actors and not ten thousand hand-keyed characters. They were agents: each an autonomous little brain that knew where it wanted to go, could see its neighbours, chose a footstep, and played a walk cycle — all of it computed, not animated. Multiply one such brain by tens of thousands and you have a crowd simulation: the art of animating hundreds, thousands, sometimes millions of characters that no human could ever pose by hand.
The trick that makes this tractable is layering. You never solve "animate a crowd" in one go. You split it into a tall stack — navigation decides where each agent should head, local collision avoidance stops agents from walking through one another on the way, and the animation layer turns those decisions into moving legs. This page walks the whole stack, then zooms in on the beautiful idea at its heart: how two strangers on a collision course each turn a little bit and pass smoothly, instead of doing that awkward pavement dance forever.
Think of each agent as a person crossing a busy railway station. Two utterly different questions are being answered at once, on two different timescales, and a crowd engine keeps them separate:
Above both sits the animation layer: given the velocity the steering layer chose, play and blend locomotion clips so the character actually looks like it is walking at that speed. So the flow each frame is roughly:
Keeping these layers apart is not tidiness for its own sake —
The navigation layer needs a model of where an agent may walk. Three families dominate, ordered roughly by how dense the crowd is:
| Method | Idea | Best for |
|---|---|---|
| Navigation mesh + A* | Cover the walkable floor with convex polygons (the navmesh); run
|
Games, sparse-to-medium crowds, complex level geometry. |
| Roadmaps / waypoint graphs | A hand- or auto-placed graph of nodes and links; agents route along edges. A precomputed probabilistic roadmap is the classic robotics version. | Fixed environments where the same routes are reused constantly. |
| Continuum / flow fields | Solve one field over the whole map (like a fluid potential) so every cell stores a direction toward the goal; every agent just reads its local arrow. One solve serves the whole crowd. | Very dense crowds all heading for the same goal (stadium exits, marching armies). |
The key move with flow fields is that cost is shared: computing a per-agent
Now the hard part. An agent has its preferred velocity
So avoidance becomes: "find the velocity nearest to what I wanted, that isn't inside the forbidden cone." That is a tiny, fast geometry problem you can solve tens of thousands of times per frame.
Plain velocity obstacles have a nasty flaw. If
Jur van den Berg's fix (2008) is Reciprocal Velocity Obstacles (RVO): assume the
other agent is equally smart and will take half the avoidance. Instead of dodging by the full
amount, each agent dodges by half and trusts its partner to cover the rest. The oscillation vanishes.
Its refinement, ORCA (Optimal Reciprocal Collision Avoidance, 2011), replaces each
cone with a single half-plane of allowed velocities per neighbour; the safe region is the intersection
of all those half-planes, and the best velocity is found by a fast
Agent
1. Navigation gives each a preferred velocity straight through the other —
2. Avoidance. For
3. The result. Each veers by a small, symmetric amount, they slide past shoulder to shoulder, and then navigation reasserts and both curve back onto their original lines. No stopping, no wobble. Crucially, because the rule is shared and half-and-half, they never both jump to the same side and re-collide — the deadlock that a naïve "assume the other stands still" avoider produces.
RVO/ORCA is defined pairwise, but each agent simply intersects the constraints from all its near neighbours at once (ORCA's half-plane intersection). In a dense plaza this can over-constrain an agent until no safe velocity exists — the linear program is infeasible. Production implementations then fall back to the "least-bad" velocity (the one that minimises the worst penetration), so agents slow and shuffle rather than freeze. And for genuinely packed crowds — a crushing stadium exit — engines switch models entirely and treat the crowd as a continuum, solving flow like a fluid where individual dodging no longer makes sense. Density models and agent models are two ends of one spectrum.
When agents are packed shoulder to shoulder, tracking pairwise cones is both expensive and wrong —
nobody in a crush is picking an "optimal velocity," they are being carried by the mass around them. So
the dense regime borrows from
Steering hands the animation layer a speed and heading; the layer must make the character
look like it moves that way. Each agent runs a locomotion
| Variation trick | What it breaks up |
|---|---|
| Random clip start-time / phase offset | Everyone stepping on the same frame. |
| Slight per-agent speed & height scaling | Identical stride length and size. |
| Swappable meshes, textures, colours ("variants") | Identical costumes and faces. |
| Small random idle fidgets & look-ats | Frozen, robotic stillness. |
Getting this layer wrong is subtle: an agent can navigate and avoid perfectly and still ruin the shot if its feet slide or a hundred copies blink at once. The believability of a crowd lives as much here as in the maths of the steering.
The idea of an agent-with-a-brain was industrialised by Massive (Stephen Regelous), built to fill the battlefields of The Lord of the Rings — each soldier a little fuzzy-logic brain reacting to what it "saw." Today the field also has Golaem and Houdini's crowd tools, which wrap navigation, ORCA-style avoidance, and clip-blending into a director-friendly package. Under the hood, sheer count forces two performance tricks:
These are the same instancing and LOD ideas used everywhere in real-time graphics, but crowds lean on them the hardest: the difference between a thousand agents and a million is almost entirely a story about draw calls and LOD budgets.
The reciprocity trap. The single most important idea in local avoidance is the reciprocal part. If each agent naïvely avoids assuming the other will not move, both dodge by the full amount and to the same side; next frame the situation has flipped, so both dodge back — a shivering, oscillating deadlock (the pavement dance). RVO/ORCA fix this by having each agent take only half the avoidance and trust its partner for the rest. Shared responsibility, consistent corrections, no jitter. If your crowd wobbles or vibrates when agents meet, you are almost certainly avoiding non-reciprocally.
Don't conflate navigation with avoidance. Navigation answers where to go at map scale; avoidance answers how not to collide right now at metre scale. Fold them together — e.g. let local dodging also try to do the long-range routing — and agents get stuck grinding against walls and pillars, because a local avoider has no idea the wall is part of a corridor it must go around. Keep the layers separate: navigation gives the preferred velocity; avoidance only perturbs it. An agent pinned against a wall is the signature of the two layers having been mashed into one.