RVO2 Library: Reciprocal Collision Avoidance for Real-Time Multi-Agent Simulation

Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill

Contact: To report bugs, suggest novel functionality, or discuss commercial licensing, please contact us.

Maintained by: Jamie Snape.

Latest update: May 17, 2012.

RVO2 Library: Copyright © and trademark ™ 2008-12 University of North Carolina at Chapel Hill. All rights reserved.

Get RVO2 Library

News

  • RVO2 Library C++ was featured in an interview on AIGameDev.com, April 29, 2012.

  • RVO2 Library C++ appears in an article in Intel Visual Adrenaline Magazine and online at Intel Software Network, April 24, 2012.

  • RVO2 Library C++ has been licensed for the video game Warhammer 40,000: Space Marine from developer Relic.

    From a review of Warhammer 40,000: Space Marine in the Daily Telegraph, September 12, 2011:

    "It's worth noting, however, that no matter how many orks are barreling your way (and often there will be a lot) the framerate never takes a hit."

Latest Versions

  • RVO2 Library C++ v2.0.1, released October 26, 2010.
  • RVO2-3D Library C++ v1.0, released May 13, 2011.
  • RVO2 Library C# v2.0, released January 10, 2011.

Introduction

Simulations of multiple agents sharing a common workspace have gained increasing attention recently, for various purposes such as crowd simulation, navigating a team of mobile robots, video games, studying natural flocking behavior, traffic engineering, architecture and design, emergency training simulations, etc.

We present an algorithm for interactive navigation and planning of large numbers of agents in two-dimensional (crowded) environments. At runtime, each agent senses the environment independently and computes a collision-free motion based on the optimal reciprocal collision avoidance (ORCA) formulation. Our algorithm ensures that each agent exhibits no oscillatory behaviors.

RVO2 Library C++ is an implementation of our algorithm. It has a simple API for third-party applications. The user specifies static obstacles, agents, and the preferred velocities of the agents. The simulation is performed step-by-step via a simple call to the library. The simulation is fully accessible and manipulable during runtime. The library exploits multiple processors if they are available using OpenMP for efficient parallelization of the simulation.

RVO2-3D Library C++ is an implementation of our algorithm for applications in three dimensions without static obstacles. A C# implementation of our algorithm by Slan is also available.

Sponsors

This work was supported by ARO under Contract W911NF‑04‑1‑0088, by NSF under Award 0636208, Award 0917040, and Award 0904990, by DARPA and RDECOM under Contract WR91CRB‑08‑C‑0137, and by Intel. Any opinions, findings, and conclusions or recommendations expressed herein are those of the authors and do not necessarily reflect the views of ARO, NSF, DARPA, RDECOM, or Intel.

Related Links


Relic is a trademark of SEGA, registered in the U.S. and other countries. Warhammer and Space Marine are trademarks of Games Workshop Ltd., registered in the U.S. and other countries. Warhammer 40,000 is a trademark of Games Workshop Ltd. OpenMP is a trademark of the OpenMP Architecture Review Board, registered in the U.S. and other countries. Intel is a trademark of Intel Corporation, registered in the U.S. and other countries. Other names may be trademarks of their respective owners.