/* * RVO.h * RVO2-3D Library * * Copyright 2008 University of North Carolina at Chapel Hill * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * Please send all bug reports to . * * The authors may be contacted via: * * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha * Dept. of Computer Science * 201 S. Columbia St. * Frederick P. Brooks, Jr. Computer Science Bldg. * Chapel Hill, N.C. 27599-3175 * United States of America * * */ #ifndef RVO_RVO_H_ #define RVO_RVO_H_ #include "API.h" #include "RVOSimulator.h" #include "Vector3.h" /** \file RVO.h \brief Includes all public headers in the library. \namespace RVO \brief Contains all classes, functions, and constants used in the library. \mainpage RVO2-3D Library \author Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha RVO2-3D Library is an easy-to-use C++ implementation of the Optimal Reciprocal Collision Avoidance (ORCA) formulation for multi-agent simulation in three dimensions. RVO2-3D Library automatically uses parallelism for computing the motion of the agents if your machine has multiple processors and your compiler supports OpenMP. Please follow the following steps to install and use RVO2-3D Library. - \subpage whatsnew - \subpage building - \subpage using - \subpage params See the documentation of the RVO::RVOSimulator class for an exhaustive list of public functions of RVO2-3D Library. RVO2-3D Library, accompanying example code, and this documentation is released for educational, research, and non-profit purposes under the following \subpage terms "terms and conditions". \page whatsnew What Is New in RVO2-3D Library \section localca Three Dimensions In contrast to RVO2 Library, RVO2-3D Library operates in 3D workspaces. It uses a three dimensional implementation of Optimal Reciprocal Collision Avoidance (ORCA) for local collision avoidance. RVO2-3D Library does not replace RVO2 Library; for 2D applications, RVO2 Library should be used. \section structure Structure of RVO2-3D Library The structure of RVO2-3D Library is similar to that of RVO2 Library. Users familiar with RVO2 Library should find little trouble in using RVO2-3D Library. RVO2-3D Library currently does not support static obstacles. \page building Building RVO2-3D Library We assume that you have downloaded RVO2-3D Library and unpacked the ZIP archive to a path $RVO_ROOT. \section xcode Apple Xcode 4.x Open $RVO_ROOT/RVO.xcodeproj and select the Static Library scheme. A static library libRVO.a will be built in the default build directory. \section cmake CMake Create and switch to your chosen build directory, e.g. $RVO_ROOT/build. Run cmake inside the build directory on the source directory, e.g. cmake $RVO_ROOT/src. Build files for the default generator for your platform will be generated in the build directory. \section make GNU Make Switch to the source directory $RVO_ROOT/src and run make. Public header files (API.h, RVO.h, RVOSimulator.h, and Vector3.h) will be copied to the $RVO_ROOT/include directory and a static library libRVO.a will be compiled into the $RVO_ROOT/lib directory. \section visual Microsoft Visual Studio 2010 Open $RVO_ROOT/RVO.sln and select the RVOStatic project and a configuration (Debug or Release). Public header files (API.h, RVO.h, RVOSimulator.h, and Vector3.h) will be copied to the $RVO_ROOT/include directory and a static library, e.g. RVO.lib, will be compiled into the $RVO_ROOT/lib directory. \page using Using RVO2-3D Library \section structure Structure A program performing an RVO2-3D Library simulation has the following global structure. \code #include std::vector goals; int main() { // Create a new simulator instance. RVO::RVOSimulator* sim = new RVO::RVOSimulator(); // Set up the scenario. setupScenario(sim); // Perform (and manipulate) the simulation. do { updateVisualization(sim); setPreferredVelocities(sim); sim->doStep(); } while (!reachedGoal(sim)); delete sim; } \endcode In order to use RVO2-3D Library, the user needs to include RVO.h. The first step is then to create an instance of RVO::RVOSimulator. Then, the process consists of two stages. The first stage is specifying the simulation scenario and its parameters. In the above example program, this is done in the method setupScenario(...), which we will discuss below. The second stage is the actual performing of the simulation. In the above example program, simulation steps are taken until all the agents have reached some predefined goals. Prior to each simulation step, we set the preferred velocity for each agent, i.e. the velocity the agent would have taken if there were no other agents around, in the method setPreferredVelocities(...). The simulator computes the actual velocities of the agents and attempts to follow the preferred velocities as closely as possible while guaranteeing collision avoidance at the same time. During the simulation, the user may want to retrieve information from the simulation for instance to visualize the simulation. In the above example program, this is done in the method updateVisualization(...), which we will discuss below. It is also possible to manipulate the simulation during the simulation, for instance by changing positions, radii, velocities, etc. of the agents. \section spec Setting up the Simulation Scenario A scenario that is to be simulated can be set up as follows. A scenario consists of a set of agents that can be manually specified. Agents may be added anytime before or during the simulation. The user may also want to define goal positions of the agents, or a roadmap to guide the agents around obstacles. This is not done in RVO2-3D Library, but needs to be taken care of in the user's external application. The following example creates a scenario with eight agents exchanging positions. \code void setupScenario(RVO::RVOSimulator* sim) { // Specify global time step of the simulation. sim->setTimeStep(0.25f); // Specify default parameters for agents that are subsequently added. sim->setAgentDefaults(15.0f, 10, 10.0f, 2.0f, 2.0f); // Add agents, specifying their start position. sim->addAgent(RVO::Vector3(-50.0f, -50.0f, -50.0f)); sim->addAgent(RVO::Vector3(50.0f, -50.0f, -50.0f)); sim->addAgent(RVO::Vector3(50.0f, 50.0f, -50.0f)); sim->addAgent(RVO::Vector3(-50.0f, 50.0f, -50.0f)); sim->addAgent(RVO::Vector3(-50.0f, -50.0f, 50.0f)); sim->addAgent(RVO::Vector3(50.0f, -50.0f, 50.0f)); sim->addAgent(RVO::Vector3(50.0f, 50.0f, 50.0f)); sim->addAgent(RVO::Vector3(-50.0f, 50.0f, 50.0f)); // Create goals (simulator is unaware of these). for (size_t i = 0; i < sim->getNumAgents(); ++i) { goals.push_back(-sim->getAgentPosition(i)); } } \endcode See the documentation on RVO::RVOSimulator for a full overview of the functionality to specify scenarios. \section ret Retrieving Information from the Simulation During the simulation, the user can extract information from the simulation for instance for visualization purposes, or to determine termination conditions of the simulation. In the example program above, visualization is done in the updateVisualization(...) method. Below we give an example that simply writes the positions of each agent in each time step to the standard output. The termination condition is checked in the reachedGoal(...) method. Here we give an example that returns true if all agents are within one radius of their goals. \code void updateVisualization(RVO::RVOSimulator* sim) { // Output the current global time. std::cout << sim->getGlobalTime() << " "; // Output the position for all the agents. for (size_t i = 0; i < sim->getNumAgents(); ++i) { std::cout << sim->getAgentPosition(i) << " "; } std::cout << std::endl; } \endcode \code bool reachedGoal(RVO::RVOSimulator* sim) { // Check whether all agents have arrived at their goals. for (size_t i = 0; i < sim->getNumAgents(); ++i) { if (absSq(goals[i] - sim->getAgentPosition(i)) > sim->getAgentRadius(i) * sim->getAgentRadius(i)) { // Agent is further away from its goal than one radius. return false; } } return true; } \endcode Using similar functions as the ones used in this example, the user can access information about other parameters of the agents, as well as the global parameters, and the obstacles. See the documentation of the class RVO::RVOSimulator for an exhaustive list of public functions for retrieving simulation information. \section manip Manipulating the Simulation During the simulation, the user can manipulate the simulation, for instance by changing the global parameters, or changing the parameters of the agents (potentially causing abrupt different behavior). It is also possible to give the agents a new position, which make them jump through the scene. New agents can be added to the simulation at any time. See the documentation of the class RVO::RVOSimulator for an exhaustive list of public functions for manipulating the simulation. To provide global guidance to the agents, the preferred velocities of the agents can be changed ahead of each simulation step. In the above example program, this happens in the method setPreferredVelocities(...). Here we give an example that simply sets the preferred velocity to the unit vector towards the agent's goal for each agent (i.e., the preferred speed is 1.0). \code void setPreferredVelocities(RVO::RVOSimulator* sim) { // Set the preferred velocity for each agent. for (size_t i = 0; i < sim->getNumAgents(); ++i) { if (absSq(goals[i] - sim->getAgentPosition(i)) < sim->getAgentRadius(i) * sim->getAgentRadius(i) ) { // Agent is within one radius of its goal, set preferred velocity to zero sim->setAgentPrefVelocity(i, RVO::Vector3()); } else { // Agent is far away from its goal, set preferred velocity as unit vector towards agent's goal. sim->setAgentPrefVelocity(i, normalize(goals[i] - sim->getAgentPosition(i))); } } } \endcode \section example Example Programs RVO2-3D Library is accompanied by one example program, which can be found in the $RVO_ROOT/examples directory. The example is named Sphere, and contains the following demonstration scenario:
Sphere A scenario in which 812 agents, initially positioned evenly distributed on a sphere, move to the antipodal position on the sphere.
\page params Parameter Overview \section globalp Global Parameters
Parameter Type (unit) Meaning
timeStep float (time) The time step of the simulation. Must be positive.
\section agent Agent Parameters
Parameter Type (unit) Meaning
maxNeighbors size_t The maximum number of other agents the agent takes into account in the navigation. The larger this number, the longer the running time of the simulation. If the number is too low, the simulation will not be safe.
maxSpeed float (distance/time) The maximum speed of the agent. Must be non-negative.
neighborDist float (distance) The maximum distance (center point to center point) to other agents the agent takes into account in the navigation. The larger this number, the longer the running time of the simulation. If the number is too low, the simulation will not be safe. Must be non-negative.
position RVO::Vector3 (distance, distance) The current position of the agent.
prefVelocity RVO::Vector3 (distance/time, distance/time) The current preferred velocity of the agent. This is the velocity the agent would take if no other agents or obstacles were around. The simulator computes an actual velocity for the agent that follows the preferred velocity as closely as possible, but at the same time guarantees collision avoidance.
radius float (distance) The radius of the agent. Must be non-negative.
timeHorizon float (time) The minimum amount of time for which the agent's velocities that are computed by the simulation are safe with respect to other agents. The larger this number, the sooner this agent will respond to the presence of other agents, but the less freedom the agent has in choosing its velocities. Must be positive.
velocity RVO::Vector3 (distance/time, distance/time) The (current) velocity of the agent.
\page terms Terms and Conditions RVO2-3D Library Copyright 2008 University of North Carolina at Chapel Hill Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. */ #endif /* RVO_RVO_H_ */