diff options
Diffstat (limited to 'thirdparty/rvo2/src/RVO.h')
| -rw-r--r-- | thirdparty/rvo2/src/RVO.h | 406 |
1 files changed, 406 insertions, 0 deletions
diff --git a/thirdparty/rvo2/src/RVO.h b/thirdparty/rvo2/src/RVO.h new file mode 100644 index 0000000000..81c9cbd8d3 --- /dev/null +++ b/thirdparty/rvo2/src/RVO.h @@ -0,0 +1,406 @@ +/* + * 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 <geom@cs.unc.edu>. + * + * 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 + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +#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 + + <b>RVO2-3D Library</b> is an easy-to-use C++ implementation of the + <a href="http://gamma.cs.unc.edu/CA/">Optimal Reciprocal Collision Avoidance</a> + (ORCA) formulation for multi-agent simulation in three dimensions. <b>RVO2-3D Library</b> + automatically uses parallelism for computing the motion of the agents if your machine + has multiple processors and your compiler supports <a href="http://www.openmp.org/"> + OpenMP</a>. + + Please follow the following steps to install and use <b>RVO2-3D Library</b>. + + - \subpage whatsnew + - \subpage building + - \subpage using + - \subpage params + + See the documentation of the RVO::RVOSimulator class for an exhaustive list of + public functions of <b>RVO2-3D Library</b>. + + <b>RVO2-3D Library</b>, 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, <b>RVO2-3D Library</b> operates in 3D workspaces. It uses + a three dimensional implementation of <a href="http://gamma.cs.unc.edu/CA/">Optimal + Reciprocal Collision Avoidance</a> (ORCA) for local collision avoidance. <b>RVO2-3D + Library</b> does not replace RVO2 Library; for 2D applications, RVO2 Library should + be used. + + \section structure Structure of RVO2-3D Library + + The structure of <b>RVO2-3D Library</b> is similar to that of RVO2 Library. + Users familiar with RVO2 Library should find little trouble in using <b>RVO2-3D + Library</b>. <b>RVO2-3D Library</b> currently does not support static obstacles. + + \page building Building RVO2-3D Library + + We assume that you have downloaded <b>RVO2-3D Library</b> and unpacked the ZIP + archive to a path <tt>$RVO_ROOT</tt>. + + \section xcode Apple Xcode 4.x + + Open <tt>$RVO_ROOT/RVO.xcodeproj</tt> and select the <tt>Static Library</tt> scheme. A static library <tt>libRVO.a</tt> will be built in the default build directory. + + \section cmake CMake + + Create and switch to your chosen build directory, e.g. <tt>$RVO_ROOT/build</tt>. + Run <tt>cmake</tt> inside the build directory on the source directory, e.g. + <tt>cmake $RVO_ROOT/src</tt>. 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 <tt>$RVO_ROOT/src</tt> and run <tt>make</tt>. + Public header files (<tt>API.h</tt>, <tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and <tt>Vector3.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory and a static library <tt>libRVO.a</tt> will be compiled into the + <tt>$RVO_ROOT/lib</tt> directory. + + \section visual Microsoft Visual Studio 2010 + + Open <tt>$RVO_ROOT/RVO.sln</tt> and select the <tt>RVOStatic</tt> project and a + configuration (<tt>Debug</tt> or <tt>Release</tt>). Public header files (<tt>API.h</tt>, <tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and <tt>Vector3.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory and a static library, e.g. <tt>RVO.lib</tt>, will be compiled into the + <tt>$RVO_ROOT/lib</tt> directory. + + + \page using Using RVO2-3D Library + + \section structure Structure + + A program performing an <b>RVO2-3D Library</b> simulation has the following global + structure. + + \code + #include <RVO.h> + + std::vector<RVO::Vector3> 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 <b>RVO2-3D Library</b>, 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 <b>RVO2-3D Library</b>, 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 + + <b>RVO2-3D Library</b> is accompanied by one example program, which can be found in the + <tt>$RVO_ROOT/examples</tt> directory. The example is named Sphere, and + contains the following demonstration scenario: + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="100"><b>Sphere</b></td> + <td valign="top">A scenario in which 812 agents, initially positioned evenly + distributed on a sphere, move to the antipodal position on the + sphere. </td> + </tr> + </table> + + + \page params Parameter Overview + + \section globalp Global Parameters + + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="150"><strong>Parameter</strong></td> + <td valign="top" width="150"><strong>Type (unit)</strong></td> + <td valign="top"><strong>Meaning</strong></td> + </tr> + <tr> + <td valign="top">timeStep</td> + <td valign="top">float (time)</td> + <td valign="top">The time step of the simulation. Must be positive.</td> + </tr> + </table> + + \section agent Agent Parameters + + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="150"><strong>Parameter</strong></td> + <td valign="top" width="150"><strong>Type (unit)</strong></td> + <td valign="top"><strong>Meaning</strong></td> + </tr> + <tr> + <td valign="top">maxNeighbors</td> + <td valign="top">size_t</td> + <td valign="top">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.</td> + </tr> + <tr> + <td valign="top">maxSpeed</td> + <td valign="top">float (distance/time)</td> + <td valign="top">The maximum speed of the agent. Must be non-negative.</td> + </tr> + <tr> + <td valign="top">neighborDist</td> + <td valign="top">float (distance)</td> + <td valign="top">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.</td> + </tr> + <tr> + <td valign="top" width="150">position</td> + <td valign="top" width="150">RVO::Vector3 (distance, distance)</td> + <td valign="top">The current position of the agent.</td> + </tr> + <tr> + <td valign="top" width="150">prefVelocity</td> + <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time) + </td> + <td valign="top">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.</td> + </tr> + <tr> + <td valign="top">radius</td> + <td valign="top">float (distance)</td> + <td valign="top">The radius of the agent. Must be non-negative.</td> + </tr> + <tr> + <td valign="top" width="150">timeHorizon</td> + <td valign="top" width="150">float (time)</td> + <td valign="top">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. </td> + </tr> + <tr> + <td valign="top" width="150">velocity</td> + <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time) + </td> + <td valign="top">The (current) velocity of the agent.</td> + </tr> + </table> + + + \page terms Terms and Conditions + + <b>RVO2-3D Library</b> + + 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_ */ |