RVO.h
Go to the documentation of this file.
1 /*
2  * RVO.h
3  * RVO2-3D Library
4  *
5  * Copyright 2008 University of North Carolina at Chapel Hill
6  *
7  * Licensed under the Apache License, Version 2.0 (the "License");
8  * you may not use this file except in compliance with the License.
9  * You may obtain a copy of the License at
10  *
11  * http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing, software
14  * distributed under the License is distributed on an "AS IS" BASIS,
15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  * See the License for the specific language governing permissions and
17  * limitations under the License.
18  *
19  * Please send all bug reports to <geom@cs.unc.edu>.
20  *
21  * The authors may be contacted via:
22  *
23  * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha
24  * Dept. of Computer Science
25  * 201 S. Columbia St.
26  * Frederick P. Brooks, Jr. Computer Science Bldg.
27  * Chapel Hill, N.C. 27599-3175
28  * United States of America
29  *
30  * <http://gamma.cs.unc.edu/RVO2/>
31  */
32 
33 #ifndef RVO_RVO_H_
34 #define RVO_RVO_H_
35 
36 #include "API.h"
37 #include "RVOSimulator.h"
38 #include "Vector3.h"
39 
40 /**
41 
42  \file RVO.h
43  \brief Includes all public headers in the library.
44 
45  \namespace RVO
46  \brief Contains all classes, functions, and constants used in the library.
47 
48  \mainpage RVO2-3D Library
49 
50  \author Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha
51 
52  <b>RVO2-3D Library</b> is an easy-to-use C++ implementation of the
53  <a href="http://gamma.cs.unc.edu/CA/">Optimal Reciprocal Collision Avoidance</a>
54  (ORCA) formulation for multi-agent simulation in three dimensions. <b>RVO2-3D Library</b>
55  automatically uses parallelism for computing the motion of the agents if your machine
56  has multiple processors and your compiler supports <a href="http://www.openmp.org/">
57  OpenMP</a>.
58 
59  Please follow the following steps to install and use <b>RVO2-3D Library</b>.
60 
61  - \subpage whatsnew
62  - \subpage building
63  - \subpage using
64  - \subpage params
65 
66  See the documentation of the RVO::RVOSimulator class for an exhaustive list of
67  public functions of <b>RVO2-3D Library</b>.
68 
69  <b>RVO2-3D Library</b>, accompanying example code, and this documentation is
70  released for educational, research, and non-profit purposes under the following
71  \subpage terms "terms and conditions".
72 
73 
74  \page whatsnew What Is New in RVO2-3D Library
75 
76  \section localca Three Dimensions
77 
78  In contrast to RVO2 Library, <b>RVO2-3D Library</b> operates in 3D workspaces. It uses
79  a three dimensional implementation of <a href="http://gamma.cs.unc.edu/CA/">Optimal
80  Reciprocal Collision Avoidance</a> (ORCA) for local collision avoidance. <b>RVO2-3D
81  Library</b> does not replace RVO2 Library; for 2D applications, RVO2 Library should
82  be used.
83 
84  \section structure Structure of RVO2-3D Library
85 
86  The structure of <b>RVO2-3D Library</b> is similar to that of RVO2 Library.
87  Users familiar with RVO2 Library should find little trouble in using <b>RVO2-3D
88  Library</b>. <b>RVO2-3D Library</b> currently does not support static obstacles.
89 
90  \page building Building RVO2-3D Library
91 
92  We assume that you have downloaded <b>RVO2-3D Library</b> and unpacked the ZIP
93  archive to a path <tt>$RVO_ROOT</tt>.
94 
95  \section xcode Apple Xcode 4.x
96 
97  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.
98 
99  \section cmake CMake
100 
101  Create and switch to your chosen build directory, e.g. <tt>$RVO_ROOT/build</tt>.
102  Run <tt>cmake</tt> inside the build directory on the source directory, e.g.
103  <tt>cmake $RVO_ROOT/src</tt>. Build files for the default generator for your
104  platform will be generated in the build directory.
105 
106  \section make GNU Make
107 
108  Switch to the source directory <tt>$RVO_ROOT/src</tt> and run <tt>make</tt>.
109  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
110  <tt>$RVO_ROOT/lib</tt> directory.
111 
112  \section visual Microsoft Visual Studio 2010
113 
114  Open <tt>$RVO_ROOT/RVO.sln</tt> and select the <tt>RVOStatic</tt> project and a
115  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
116  <tt>$RVO_ROOT/lib</tt> directory.
117 
118 
119  \page using Using RVO2-3D Library
120 
121  \section structure Structure
122 
123  A program performing an <b>RVO2-3D Library</b> simulation has the following global
124  structure.
125 
126  \code
127  #include <RVO.h>
128 
129  std::vector<RVO::Vector3> goals;
130 
131  int main()
132  {
133  // Create a new simulator instance.
134  RVO::RVOSimulator* sim = new RVO::RVOSimulator();
135 
136  // Set up the scenario.
137  setupScenario(sim);
138 
139  // Perform (and manipulate) the simulation.
140  do {
141  updateVisualization(sim);
142  setPreferredVelocities(sim);
143  sim->doStep();
144  } while (!reachedGoal(sim));
145 
146  delete sim;
147  }
148  \endcode
149 
150  In order to use <b>RVO2-3D Library</b>, the user needs to include RVO.h. The first
151  step is then to create an instance of RVO::RVOSimulator. Then, the process
152  consists of two stages. The first stage is specifying the simulation scenario
153  and its parameters. In the above example program, this is done in the method
154  setupScenario(...), which we will discuss below. The second stage is the actual
155  performing of the simulation.
156 
157  In the above example program, simulation steps are taken until all
158  the agents have reached some predefined goals. Prior to each simulation step,
159  we set the preferred velocity for each agent, i.e. the
160  velocity the agent would have taken if there were no other agents around, in the
161  method setPreferredVelocities(...). The simulator computes the actual velocities
162  of the agents and attempts to follow the preferred velocities as closely as
163  possible while guaranteeing collision avoidance at the same time. During the
164  simulation, the user may want to retrieve information from the simulation for
165  instance to visualize the simulation. In the above example program, this is done
166  in the method updateVisualization(...), which we will discuss below. It is also
167  possible to manipulate the simulation during the simulation, for instance by
168  changing positions, radii, velocities, etc. of the agents.
169 
170  \section spec Setting up the Simulation Scenario
171 
172  A scenario that is to be simulated can be set up as follows. A scenario consists
173  of a set of agents that can be manually specified. Agents may be added anytime
174  before or during the simulation. The user may also want to define goal positions
175  of the agents, or a roadmap to guide the agents around obstacles. This is not done
176  in <b>RVO2-3D Library</b>, but needs to be taken care of in the user's external
177  application.
178 
179  The following example creates a scenario with eight agents exchanging positions.
180 
181  \code
182  void setupScenario(RVO::RVOSimulator* sim) {
183  // Specify global time step of the simulation.
184  sim->setTimeStep(0.25f);
185 
186  // Specify default parameters for agents that are subsequently added.
187  sim->setAgentDefaults(15.0f, 10, 10.0f, 2.0f, 2.0f);
188 
189  // Add agents, specifying their start position.
190  sim->addAgent(RVO::Vector3(-50.0f, -50.0f, -50.0f));
191  sim->addAgent(RVO::Vector3(50.0f, -50.0f, -50.0f));
192  sim->addAgent(RVO::Vector3(50.0f, 50.0f, -50.0f));
193  sim->addAgent(RVO::Vector3(-50.0f, 50.0f, -50.0f));
194  sim->addAgent(RVO::Vector3(-50.0f, -50.0f, 50.0f));
195  sim->addAgent(RVO::Vector3(50.0f, -50.0f, 50.0f));
196  sim->addAgent(RVO::Vector3(50.0f, 50.0f, 50.0f));
197  sim->addAgent(RVO::Vector3(-50.0f, 50.0f, 50.0f));
198 
199  // Create goals (simulator is unaware of these).
200  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
201  goals.push_back(-sim->getAgentPosition(i));
202  }
203  }
204  \endcode
205 
206  See the documentation on RVO::RVOSimulator for a full overview of the
207  functionality to specify scenarios.
208 
209  \section ret Retrieving Information from the Simulation
210 
211  During the simulation, the user can extract information from the simulation for
212  instance for visualization purposes, or to determine termination conditions of
213  the simulation. In the example program above, visualization is done in the
214  updateVisualization(...) method. Below we give an example that simply writes
215  the positions of each agent in each time step to the standard output. The
216  termination condition is checked in the reachedGoal(...) method. Here we give an
217  example that returns true if all agents are within one radius of their goals.
218 
219  \code
220  void updateVisualization(RVO::RVOSimulator* sim) {
221  // Output the current global time.
222  std::cout << sim->getGlobalTime() << " ";
223 
224  // Output the position for all the agents.
225  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
226  std::cout << sim->getAgentPosition(i) << " ";
227  }
228 
229  std::cout << std::endl;
230  }
231  \endcode
232 
233  \code
234  bool reachedGoal(RVO::RVOSimulator* sim) {
235  // Check whether all agents have arrived at their goals.
236  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
237  if (absSq(goals[i] - sim->getAgentPosition(i)) > sim->getAgentRadius(i) * sim->getAgentRadius(i)) {
238  // Agent is further away from its goal than one radius.
239  return false;
240  }
241  }
242  return true;
243  }
244  \endcode
245 
246  Using similar functions as the ones used in this example, the user can access
247  information about other parameters of the agents, as well as the global
248  parameters, and the obstacles. See the documentation of the class
249  RVO::RVOSimulator for an exhaustive list of public functions for retrieving
250  simulation information.
251 
252  \section manip Manipulating the Simulation
253 
254  During the simulation, the user can manipulate the simulation, for instance by
255  changing the global parameters, or changing the parameters of the agents
256  (potentially causing abrupt different behavior). It is also possible to give the
257  agents a new position, which make them jump through the scene.
258  New agents can be added to the simulation at any time.
259 
260  See the documentation of the class RVO::RVOSimulator for an exhaustive list of
261  public functions for manipulating the simulation.
262 
263  To provide global guidance to the agents, the preferred velocities of the agents
264  can be changed ahead of each simulation step. In the above example program, this
265  happens in the method setPreferredVelocities(...). Here we give an example that
266  simply sets the preferred velocity to the unit vector towards the agent's goal
267  for each agent (i.e., the preferred speed is 1.0).
268 
269  \code
270  void setPreferredVelocities(RVO::RVOSimulator* sim) {
271  // Set the preferred velocity for each agent.
272  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
273  if (absSq(goals[i] - sim->getAgentPosition(i)) < sim->getAgentRadius(i) * sim->getAgentRadius(i) ) {
274  // Agent is within one radius of its goal, set preferred velocity to zero
275  sim->setAgentPrefVelocity(i, RVO::Vector3());
276  } else {
277  // Agent is far away from its goal, set preferred velocity as unit vector towards agent's goal.
278  sim->setAgentPrefVelocity(i, normalize(goals[i] - sim->getAgentPosition(i)));
279  }
280  }
281  }
282  \endcode
283 
284  \section example Example Programs
285 
286  <b>RVO2-3D Library</b> is accompanied by one example program, which can be found in the
287  <tt>$RVO_ROOT/examples</tt> directory. The example is named Sphere, and
288  contains the following demonstration scenario:
289  <table border="0" cellpadding="3" width="100%">
290  <tr>
291  <td valign="top" width="100"><b>Sphere</b></td>
292  <td valign="top">A scenario in which 812 agents, initially positioned evenly
293  distributed on a sphere, move to the antipodal position on the
294  sphere. </td>
295  </tr>
296  </table>
297 
298 
299  \page params Parameter Overview
300 
301  \section globalp Global Parameters
302 
303  <table border="0" cellpadding="3" width="100%">
304  <tr>
305  <td valign="top" width="150"><strong>Parameter</strong></td>
306  <td valign="top" width="150"><strong>Type (unit)</strong></td>
307  <td valign="top"><strong>Meaning</strong></td>
308  </tr>
309  <tr>
310  <td valign="top">timeStep</td>
311  <td valign="top">float (time)</td>
312  <td valign="top">The time step of the simulation. Must be positive.</td>
313  </tr>
314  </table>
315 
316  \section agent Agent Parameters
317 
318  <table border="0" cellpadding="3" width="100%">
319  <tr>
320  <td valign="top" width="150"><strong>Parameter</strong></td>
321  <td valign="top" width="150"><strong>Type (unit)</strong></td>
322  <td valign="top"><strong>Meaning</strong></td>
323  </tr>
324  <tr>
325  <td valign="top">maxNeighbors</td>
326  <td valign="top">size_t</td>
327  <td valign="top">The maximum number of other agents the agent takes into
328  account in the navigation. The larger this number, the
329  longer the running time of the simulation. If the number is
330  too low, the simulation will not be safe.</td>
331  </tr>
332  <tr>
333  <td valign="top">maxSpeed</td>
334  <td valign="top">float (distance/time)</td>
335  <td valign="top">The maximum speed of the agent. Must be non-negative.</td>
336  </tr>
337  <tr>
338  <td valign="top">neighborDist</td>
339  <td valign="top">float (distance)</td>
340  <td valign="top">The maximum distance (center point to center point) to
341  other agents the agent takes into account in the
342  navigation. The larger this number, the longer the running
343  time of the simulation. If the number is too low, the
344  simulation will not be safe. Must be non-negative.</td>
345  </tr>
346  <tr>
347  <td valign="top" width="150">position</td>
348  <td valign="top" width="150">RVO::Vector3 (distance, distance)</td>
349  <td valign="top">The current position of the agent.</td>
350  </tr>
351  <tr>
352  <td valign="top" width="150">prefVelocity</td>
353  <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time)
354  </td>
355  <td valign="top">The current preferred velocity of the agent. This is the
356  velocity the agent would take if no other agents or
357  obstacles were around. The simulator computes an actual
358  velocity for the agent that follows the preferred velocity
359  as closely as possible, but at the same time guarantees
360  collision avoidance.</td>
361  </tr>
362  <tr>
363  <td valign="top">radius</td>
364  <td valign="top">float (distance)</td>
365  <td valign="top">The radius of the agent. Must be non-negative.</td>
366  </tr>
367  <tr>
368  <td valign="top" width="150">timeHorizon</td>
369  <td valign="top" width="150">float (time)</td>
370  <td valign="top">The minimum amount of time for which the agent's velocities
371  that are computed by the simulation are safe with respect
372  to other agents. The larger this number, the sooner this
373  agent will respond to the presence of other agents, but the
374  less freedom the agent has in choosing its velocities.
375  Must be positive. </td>
376  </tr>
377  <tr>
378  <td valign="top" width="150">velocity</td>
379  <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time)
380  </td>
381  <td valign="top">The (current) velocity of the agent.</td>
382  </tr>
383  </table>
384 
385 
386  \page terms Terms and Conditions
387 
388  <b>RVO2-3D Library</b>
389 
390  Copyright 2008 University of North Carolina at Chapel Hill
391 
392  Licensed under the Apache License, Version 2.0 (the "License");
393  you may not use this file except in compliance with the License.
394  You may obtain a copy of the License at
395 
396  http://www.apache.org/licenses/LICENSE-2.0
397 
398  Unless required by applicable law or agreed to in writing, software
399  distributed under the License is distributed on an "AS IS" BASIS,
400  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
401  See the License for the specific language governing permissions and
402  limitations under the License.
403 
404  */
405 
406 #endif /* RVO_RVO_H_ */