Main Page
Related Pages
Namespaces
Classes
Files
File List
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 "goal position" or "preferred speed" 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
"class" 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_ */
RVO2 Library. Copyright 2008 University of North Carolina at Chapel Hill.