Optimal Reciprocal Collision Avoidance

In 2013 I implemented Optimal Reciprocal Collision Avoidance and created a visualization/debugging tool.

The actual paper “Reciprocal n-body collision avoidance” suggests using a linear programming algorithm, but I figured that it was easier to compute optimal velocity vectors using simple and fast 2D geometric calculations without formalizing it into a convex optimization problem.

I integrated my implementation into the Source Engine NPC locomotion system for NPC-NPC, NPC-player and NPC-obstacle avoidance together with Recast/Detour nagivation meshes.

A neat feature of this method is the ability to give agents an “avoidance contribution” value. Usually this value is set to 0.5, meaning that agents reciprocally and equally divide up how much they need to alter their velocity. When you add the player character as an agent in the system with desired velocity equal to current velocity, and give it a contribution of 0, every NPC takes on full avoidance measures and can therefore react quite smoothly to get out of the way of approaching players, while avoiding other NPCs at the same time. The same thing applies for static obstacle avoidance, where static obstacles also get a responsibility of 0.

Videos

Here are some clips I found from my visualization tool. The grey lines represent the desired velocity vector, the white lines the actual velocity vector and the white dots the target positions of the agents. In the clips I set the parameters to avoid at a closer range, but you can also set the parameters to make agents “look ahead” more, i.e. to start avoiding each other at a greater distance.