Reciprocal velocity obstacles (RVO)
A method for letting many agents avoid each other smoothly by having each take half the responsibility for dodging.
A velocity obstacle (Fiorini & Shiller, 1998) is the set of all velocities that will eventually cause a collision with an obstacle. An agent simply picks a velocity outside that set. The trouble starts when both agents dodge at once: they ping-pong back and forth and begin to oscillate.
RVO (van den Berg, Lin & Manocha, 2008) fixes this by having each agent assume its counterpart will take half of the avoidance. The result is the smooth, human-looking motion of crowds and RTS units without the jitter. Its successor ORCA (2011) recasts it as linear constraints and scales to thousands of agents. RVO complements pathfinding: a navmesh gives the coarse route, RVO handles the last few metres between neighbours.