RVO.h
Go to the documentation of this file.
1 /*
2  * RVO.h
3  * RVO2 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 "RVOSimulator.h"
37 #include "Vector2.h"
38 
39 /**
40 
41  \file RVO.h
42  \brief Includes all public headers in the library.
43 
44  \namespace RVO
45  \brief Contains all classes, functions, and constants used in the library.
46 
47  \mainpage RVO2 Library
48 
49  \author Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and
50  Dinesh Manocha
51 
52  <b>RVO2 Library</b> is an easy-to-use C++ implementation of the
53  <a href="http://gamma.cs.unc.edu/ORCA/">Optimal Reciprocal Collision Avoidance</a>
54  (ORCA) formulation for multi-agent simulation. <b>RVO2 Library</b> automatically
55  uses parallelism for computing the motion of the agents if your machine has
56  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 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 Library</b>.
68 
69  <b>RVO2 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 Library
75 
76  \section localca Local Collision Avoidance
77 
78  The main difference between <b>RVO2 Library</b> and %RVO Library 1.x is the
79  local collision avoidance technique used. <b>RVO2 Library</b> uses
80  <a href="http://gamma.cs.unc.edu/CA/">Optimal Reciprocal Collision Avoidance</a>
81  (ORCA), whereas %RVO Library 1.x uses <a href="http://gamma.cs.unc.edu/RVO/">
82  Reciprocal Velocity Obstacles</a> (%RVO). For legacy reasons, and since both
83  techniques are based on the same principles of reciprocal collision avoidance
84  and relative velocity, we did not change the name of the library.
85 
86  A major consequence of the change of local collision avoidance technique is that
87  the simulation has become much faster in <b>RVO2 Library</b>. ORCA defines
88  velocity constraints with respect to other agents as half-planes, and an optimal
89  velocity is efficiently found using (two-dimensional) linear programming. In
90  contrast, %RVO Library 1.x uses random sampling to find a good velocity. Also,
91  the behavior of the agents is smoother in <b>RVO2 Library</b>. It is proven
92  mathematically that ORCA lets the velocity of agents evolve continuously over
93  time, whereas %RVO Library 1.x occasionally showed oscillations and reciprocal
94  dances. Furthermore, ORCA provides stronger guarantees with respect to collision
95  avoidance.
96 
97  \section global Global Path Planning
98 
99  Local collision avoidance as provided by <b>RVO2 Library</b> should in principle
100  be accompanied by global path planning that determines the preferred velocity of
101  each agent in each time step of the simulation. %RVO Library 1.x has a built-in
102  roadmap infrastructure to guide agents around obstacles to fixed goals.
103  However, besides roadmaps, other techniques for global planning, such as
104  navigation fields, cell decompositions, etc. exist. Therefore, <b>RVO2
105  Library</b> does not provide global planning infrastructure anymore. Instead,
106  it is the responsibility of the external application to set the preferred
107  velocity of each agent ahead of each time step of the simulation. This makes the
108  library more flexible to use in varying application domains. In one of the
109  example applications that comes with <b>RVO2 Library</b>, we show how a roadmap
110  similar to %RVO Library 1.x is used externally to guide the global navigation of
111  the agents. As a consequence of this change, <b>RVO2 Library</b> does not have a
112  concept of a &quot;goal position&quot; or &quot;preferred speed&quot; for each
113  agent, but only relies on the preferred velocities of the agents set by the
114  external application.
115 
116  \section structure Structure of RVO2 Library
117 
118  The structure of <b>RVO2 Library</b> is similar to that of %RVO Library 1.x.
119  Users familiar with %RVO Library 1.x should find little trouble in using <b>RVO2
120  Library</b>. However, <b>RVO2 Library</b> is not backwards compatible with %RVO
121  Library 1.x. The main reason for this is that the ORCA technique requires
122  different (and fewer) parameters to be set than %RVO. Also, the way obstacles
123  are represented is different. In %RVO Library 1.x, obstacles are represented by
124  an arbitrary collection of line segments. In <b>RVO2 Library</b>, obstacles are
125  non-intersecting polygons, specified by lists of vertices in counterclockwise
126  order. Further, in %RVO Library 1.x agents cannot be added to the simulation
127  after the simulation is initialized. In <b>RVO2 Library</b> this restriction is
128  removed. Obstacles still need to be processed before the simulation starts,
129  though. Lastly, in %RVO Library 1.x an instance of the simulator is a singleton.
130  This restriction is removed in <b>RVO2 Library</b>.
131 
132  \section smaller Smaller Changes
133 
134  With <b>RVO2 Library</b>, we have adopted the philosophy that anything that is
135  not part of the core local collision avoidance technique is to be stripped from
136  the library. Therefore, besides the roadmap infrastructure, we have also removed
137  acceleration constraints of agents, orientation of agents, and the unused
138  &quot;class&quot; of agents. Each of these can be implemented external of the
139  library if needed. We did maintain a <i>k</i>d-tree infrastructure for
140  efficiently finding other agents and obstacles nearby each agent.
141 
142  Also, <b>RVO2 Library</b> allows accessing information about the simulation,
143  such as the neighbors and the collision-avoidance constraints of each agent,
144  that is hidden from the user in %RVO Library 1.x.
145 
146 
147  \page building Building RVO2 Library
148 
149  We assume that you have downloaded <b>RVO2 Library</b> and unpacked the ZIP
150  archive to a path <tt>$RVO_ROOT</tt>.
151 
152  \section xcode Apple Xcode 3.x
153 
154  Open <tt>$RVO_ROOT/RVO.xcodeproj</tt> and select the <tt>%RVO</tt> target and
155  a configuration (<tt>Debug</tt> or <tt>Release</tt>). A framework
156  <tt>RVO.framework</tt> will be built in the default build directory, e.g. <tt>
157  $RVO_ROOT/build/Release</tt>.
158 
159  \section cmake CMake
160 
161  Create and switch to your chosen build directory, e.g. <tt>$RVO_ROOT/build</tt>.
162  Run <tt>cmake</tt> inside the build directory on the source directory, e.g.
163  <tt>cmake $RVO_ROOT/src</tt>. Build files for the default generator for your
164  platform will be generated in the build directory.
165 
166  \section make GNU Make
167 
168  Switch to the source directory <tt>$RVO_ROOT/src</tt> and run <tt>make</tt>.
169  Public header files (<tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and
170  <tt>Vector2.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory
171  and a static library <tt>libRVO.a</tt> will be compiled into the
172  <tt>$RVO_ROOT/lib</tt> directory.
173 
174  \section visual Microsoft Visual Studio 2008
175 
176  Open <tt>$RVO_ROOT/RVO.sln</tt> and select the <tt>%RVO</tt> project and a
177  configuration (<tt>Debug</tt>, <tt>ReleaseST</tt>, or <tt>ReleaseMT</tt>).
178  Public header files (<tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and
179  <tt>Vector2.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory
180  and a static library, e.g. <tt>RVO.lib</tt>, will be compiled into the
181  <tt>$RVO_ROOT/lib</tt> directory.
182 
183 
184  \page using Using RVO2 Library
185 
186  \section structure Structure
187 
188  A program performing an <b>RVO2 Library</b> simulation has the following global
189  structure.
190 
191  \code
192  #include <RVO.h>
193 
194  std::vector<RVO::Vector2> goals;
195 
196  int main()
197  {
198  // Create a new simulator instance.
199  RVO::RVOSimulator* sim = new RVO::RVOSimulator();
200 
201  // Set up the scenario.
202  setupScenario(sim);
203 
204  // Perform (and manipulate) the simulation.
205  do {
206  updateVisualization(sim);
207  setPreferredVelocities(sim);
208  sim->doStep();
209  } while (!reachedGoal(sim));
210 
211  delete sim;
212  }
213  \endcode
214 
215  In order to use <b>RVO2 Library</b>, the user needs to include RVO.h. The first
216  step is then to create an instance of RVO::RVOSimulator. Then, the process
217  consists of two stages. The first stage is specifying the simulation scenario
218  and its parameters. In the above example program, this is done in the method
219  setupScenario(...), which we will discuss below. The second stage is the actual
220  performing of the simulation.
221 
222  In the above example program, simulation steps are taken until all
223  the agents have reached some predefined goals. Prior to each simulation step,
224  we set the preferred velocity for each agent, i.e. the
225  velocity the agent would have taken if there were no other agents around, in the
226  method setPreferredVelocities(...). The simulator computes the actual velocities
227  of the agents and attempts to follow the preferred velocities as closely as
228  possible while guaranteeing collision avoidance at the same time. During the
229  simulation, the user may want to retrieve information from the simulation for
230  instance to visualize the simulation. In the above example program, this is done
231  in the method updateVisualization(...), which we will discuss below. It is also
232  possible to manipulate the simulation during the simulation, for instance by
233  changing positions, radii, velocities, etc. of the agents.
234 
235  \section spec Setting up the Simulation Scenario
236 
237  A scenario that is to be simulated can be set up as follows. A scenario consists
238  of two types of objects: agents and obstacles. Each of them can be manually
239  specified. Agents may be added anytime before or during the simulation.
240  Obstacles, however, need to be defined prior to the simulation, and
241  RVO::RVOSimulator::processObstacles() need to be called in order for the
242  obstacles to be accounted for in the simulation.
243  The user may also want to define goal positions of the agents, or a
244  roadmap to guide the agents around obstacles. This is not done in <b>RVO2
245  Library</b>, but needs to be taken care of in the user's external application.
246 
247  The following example creates a scenario with four agents exchanging positions
248  around a rectangular obstacle in the middle.
249 
250  \code
251  void setupScenario(RVO::RVOSimulator* sim) {
252  // Specify global time step of the simulation.
253  sim->setTimeStep(0.25f);
254 
255  // Specify default parameters for agents that are subsequently added.
256  sim->setAgentDefaults(15.0f, 10, 10.0f, 5.0f, 2.0f, 2.0f);
257 
258  // Add agents, specifying their start position.
259  sim->addAgent(RVO::Vector2(-50.0f, -50.0f));
260  sim->addAgent(RVO::Vector2(50.0f, -50.0f));
261  sim->addAgent(RVO::Vector2(50.0f, 50.0f));
262  sim->addAgent(RVO::Vector2(-50.0f, 50.0f));
263 
264  // Create goals (simulator is unaware of these).
265  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
266  goals.push_back(-sim->getAgentPosition(i));
267  }
268 
269  // Add (polygonal) obstacle(s), specifying vertices in counterclockwise order.
270  std::vector<RVO::Vector2> vertices;
271  vertices.push_back(RVO::Vector2(-7.0f, -20.0f));
272  vertices.push_back(RVO::Vector2(7.0f, -20.0f));
273  vertices.push_back(RVO::Vector2(7.0f, 20.0f));
274  vertices.push_back(RVO::Vector2(-7.0f, 20.0f));
275 
276  sim->addObstacle(vertices);
277 
278  // Process obstacles so that they are accounted for in the simulation.
279  sim->processObstacles();
280  }
281  \endcode
282 
283  See the documentation on RVO::RVOSimulator for a full overview of the
284  functionality to specify scenarios.
285 
286  \section ret Retrieving Information from the Simulation
287 
288  During the simulation, the user can extract information from the simulation for
289  instance for visualization purposes, or to determine termination conditions of
290  the simulation. In the example program above, visualization is done in the
291  updateVisualization(...) method. Below we give an example that simply writes
292  the positions of each agent in each time step to the standard output. The
293  termination condition is checked in the reachedGoal(...) method. Here we give an
294  example that returns true if all agents are within one radius of their goals.
295 
296  \code
297  void updateVisualization(RVO::RVOSimulator* sim) {
298  // Output the current global time.
299  std::cout << sim->getGlobalTime() << " ";
300 
301  // Output the position for all the agents.
302  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
303  std::cout << sim->getAgentPosition(i) << " ";
304  }
305 
306  std::cout << std::endl;
307  }
308  \endcode
309 
310  \code
311  bool reachedGoal(RVO::RVOSimulator* sim) {
312  // Check whether all agents have arrived at their goals.
313  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
314  if (absSq(goals[i] - sim->getAgentPosition(i)) > sim->getAgentRadius(i) * sim->getAgentRadius(i)) {
315  // Agent is further away from its goal than one radius.
316  return false;
317  }
318  }
319  return true;
320  }
321  \endcode
322 
323  Using similar functions as the ones used in this example, the user can access
324  information about other parameters of the agents, as well as the global
325  parameters, and the obstacles. See the documentation of the class
326  RVO::RVOSimulator for an exhaustive list of public functions for retrieving
327  simulation information.
328 
329  \section manip Manipulating the Simulation
330 
331  During the simulation, the user can manipulate the simulation, for instance by
332  changing the global parameters, or changing the parameters of the agents
333  (potentially causing abrupt different behavior). It is also possible to give the
334  agents a new position, which make them jump through the scene.
335  New agents can be added to the simulation at any time, but it is not allowed to
336  add obstacles to the simulation after they have been processed by calling
337  RVO::RVOSimulator::processObstacles(). Also, it is impossible to change the
338  position of the vertices of the obstacles.
339 
340  See the documentation of the class RVO::RVOSimulator for an exhaustive list of
341  public functions for manipulating the simulation.
342 
343  To provide global guidance to the agents, the preferred velocities of the agents
344  can be changed ahead of each simulation step. In the above example program, this
345  happens in the method setPreferredVelocities(...). Here we give an example that
346  simply sets the preferred velocity to the unit vector towards the agent's goal
347  for each agent (i.e., the preferred speed is 1.0). Note that this may not give
348  convincing results with respect to global navigation around the obstacles. For
349  this a roadmap or other global planning techniques may be used (see one of the
350  \ref example "example programs" that accompanies <b>RVO2 Library</b>).
351 
352  \code
353  void setPreferredVelocities(RVO::RVOSimulator* sim) {
354  // Set the preferred velocity for each agent.
355  for (size_t i = 0; i < sim->getNumAgents(); ++i) {
356  if (absSq(goals[i] - sim->getAgentPosition(i)) < sim->getAgentRadius(i) * sim->getAgentRadius(i) ) {
357  // Agent is within one radius of its goal, set preferred velocity to zero
358  sim->setAgentPrefVelocity(i, RVO::Vector2(0.0f, 0.0f));
359  } else {
360  // Agent is far away from its goal, set preferred velocity as unit vector towards agent's goal.
361  sim->setAgentPrefVelocity(i, normalize(goals[i] - sim->getAgentPosition(i)));
362  }
363  }
364  }
365  \endcode
366 
367  \section example Example Programs
368 
369  <b>RVO2 Library</b> is accompanied by three example programs, which can be found in the
370  <tt>$RVO_ROOT/examples</tt> directory. The examples are named ExampleBlocks, ExampleCircle, and
371  ExampleRoadmap, and contain the following demonstration scenarios:
372  <table border="0" cellpadding="3" width="100%">
373  <tr>
374  <td valign="top" width="100"><b>ExampleBlocks</b></td>
375  <td valign="top">A scenario in which 100 agents, split in four groups initially
376  positioned in each of four corners of the environment, move to the
377  other side of the environment through a narrow passage generated by four
378  obstacles. There is no roadmap to guide the agents around the obstacles.</td>
379  </tr>
380  <tr>
381  <td valign="top" width="100"><b>ExampleCircle</b></td>
382  <td valign="top">A scenario in which 250 agents, initially positioned evenly
383  distributed on a circle, move to the antipodal position on the
384  circle. There are no obstacles.</td>
385  </tr>
386  <tr>
387  <td valign="top" width="100"><b>ExampleRoadmap</b></td>
388  <td valign="top">The same scenario as ExampleBlocks, but now the preferred velocities
389  of the agents are determined using a roadmap guiding the agents around the obstacles.</td>
390  </tr>
391  </table>
392 
393 
394  \page params Parameter Overview
395 
396  \section globalp Global Parameters
397 
398  <table border="0" cellpadding="3" width="100%">
399  <tr>
400  <td valign="top" width="150"><strong>Parameter</strong></td>
401  <td valign="top" width="150"><strong>Type (unit)</strong></td>
402  <td valign="top"><strong>Meaning</strong></td>
403  </tr>
404  <tr>
405  <td valign="top">timeStep</td>
406  <td valign="top">float (time)</td>
407  <td valign="top">The time step of the simulation. Must be positive.</td>
408  </tr>
409  </table>
410 
411  \section agent Agent Parameters
412 
413  <table border="0" cellpadding="3" width="100%">
414  <tr>
415  <td valign="top" width="150"><strong>Parameter</strong></td>
416  <td valign="top" width="150"><strong>Type (unit)</strong></td>
417  <td valign="top"><strong>Meaning</strong></td>
418  </tr>
419  <tr>
420  <td valign="top">maxNeighbors</td>
421  <td valign="top">size_t</td>
422  <td valign="top">The maximum number of other agents the agent takes into
423  account in the navigation. The larger this number, the
424  longer the running time of the simulation. If the number is
425  too low, the simulation will not be safe.</td>
426  </tr>
427  <tr>
428  <td valign="top">maxSpeed</td>
429  <td valign="top">float (distance/time)</td>
430  <td valign="top">The maximum speed of the agent. Must be non-negative.</td>
431  </tr>
432  <tr>
433  <td valign="top">neighborDist</td>
434  <td valign="top">float (distance)</td>
435  <td valign="top">The maximum distance (center point to center point) to
436  other agents the agent takes into account in the
437  navigation. The larger this number, the longer the running
438  time of the simulation. If the number is too low, the
439  simulation will not be safe. Must be non-negative.</td>
440  </tr>
441  <tr>
442  <td valign="top" width="150">position</td>
443  <td valign="top" width="150">RVO::Vector2 (distance, distance)</td>
444  <td valign="top">The current position of the agent.</td>
445  </tr>
446  <tr>
447  <td valign="top" width="150">prefVelocity</td>
448  <td valign="top" width="150">RVO::Vector2 (distance/time, distance/time)
449  </td>
450  <td valign="top">The current preferred velocity of the agent. This is the
451  velocity the agent would take if no other agents or
452  obstacles were around. The simulator computes an actual
453  velocity for the agent that follows the preferred velocity
454  as closely as possible, but at the same time guarantees
455  collision avoidance.</td>
456  </tr>
457  <tr>
458  <td valign="top">radius</td>
459  <td valign="top">float (distance)</td>
460  <td valign="top">The radius of the agent. Must be non-negative.</td>
461  </tr>
462  <tr>
463  <td valign="top" width="150">timeHorizon</td>
464  <td valign="top" width="150">float (time)</td>
465  <td valign="top">The minimal amount of time for which the agent's velocities
466  that are computed by the simulation are safe with respect
467  to other agents. The larger this number, the sooner this
468  agent will respond to the presence of other agents, but the
469  less freedom the agent has in choosing its velocities.
470  Must be positive. </td>
471  </tr>
472  <tr>
473  <td valign="top">timeHorizonObst</td>
474  <td valign="top">float (time)</td>
475  <td valign="top">The minimal amount of time for which the agent's velocities
476  that are computed by the simulation are safe with respect
477  to obstacles. The larger this number, the sooner this agent
478  will respond to the presence of obstacles, but the less
479  freedom the agent has in choosing its velocities.
480  Must be positive. </td>
481  </tr>
482  <tr>
483  <td valign="top" width="150">velocity</td>
484  <td valign="top" width="150">RVO::Vector2 (distance/time, distance/time)
485  </td>
486  <td valign="top">The (current) velocity of the agent.</td>
487  </tr>
488  </table>
489 
490 
491  \page terms Terms and Conditions
492 
493  <b>RVO2 Library</b>
494 
495  Copyright 2008 University of North Carolina at Chapel Hill
496 
497  Licensed under the Apache License, Version 2.0 (the "License");
498  you may not use this file except in compliance with the License.
499  You may obtain a copy of the License at
500 
501  http://www.apache.org/licenses/LICENSE-2.0
502 
503  Unless required by applicable law or agreed to in writing, software
504  distributed under the License is distributed on an "AS IS" BASIS,
505  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
506  See the License for the specific language governing permissions and
507  limitations under the License.
508 
509  */
510 
511 #endif /* RVO_RVO_H_ */