hello everyone, i'm trying to implement RVO, and potentially HRVO later, but i can't seem to find many papers on the subject. and any papers/resources i do find seem to share common(or blatant rip-off) diagrams, which lead me to believe that any work i find, is just a copy+paste of the original paper: http://gamma.cs.unc....VO/icra2008.pdf

the problem i'm having is actually understanding the mathmatics behind it, the diagrams presented don't make alot of sense to me(or arn't very well explained. particularly with how the lines are extruded to x distance, and how to choose a new target.) as well, the mathmatic's is quite heavy, and assumes that i can recognize all the mathmatical symbols/proofs, and interpret them correctly, which clearly i can not.

so, i found this video:
[media][/media]

it has a minor explanation of the approach which i used to base a bit more of how the process works, and allowed me to understand the cones of collision, but again, how selecting a new target is made i'm dumbfounded on.

so i finally decided to download the RVO2 source, and actually look at how they do it.

looking at calculateNewVelocitys in Agent.cpp, i'm looking over the neighbor agent code:



for (size_t i = 0; i < agentNeighbors_.size(); ++i) {
const Agent* const other = agentNeighbors_.second;
const Vector2 relativePosition = other->position_ - position_;
const Vector2 relativeVelocity = velocity_ - other->velocity_;
const float distSq = absSq(relativePosition);
const float combinedRadius = radius_ + other->radius_;
const float combinedRadiusSq = sqr(combinedRadius);
Line line;
Vector2 u;
if (distSq > combinedRadiusSq) {
/* No collision. */
const Vector2 w = relativeVelocity - invTimeHorizon * relativePosition;
/* Vector from cutoff center to relative velocity. */
const float wLengthSq = absSq(w);
const float dotProduct1 = w * relativePosition;
if (dotProduct1 < 0.0f && sqr(dotProduct1) > combinedRadiusSq * wLengthSq) {
/* Project on cut-off circle. */
const float wLength = std::sqrt(wLengthSq);
const Vector2 unitW = w / wLength;
line.direction = Vector2(unitW.y(), -unitW.x());
u = (combinedRadius * invTimeHorizon - wLength) * unitW;
} else {
/* Project on legs. */
const float leg = std::sqrt(distSq - combinedRadiusSq);
if (det(relativePosition, w) > 0.0f) {
/* Project on left leg. */
line.direction = Vector2(relativePosition.x() * leg - relativePosition.y() * combinedRadius, relativePosition.x() * combinedRadius + relativePosition.y() * leg) / distSq;
} else {
/* Project on right leg. */
line.direction = -Vector2(relativePosition.x() * leg + relativePosition.y() * combinedRadius, -relativePosition.x() * combinedRadius + relativePosition.y() * leg) / distSq;
}
const float dotProduct2 = relativeVelocity * line.direction;
u = dotProduct2 * line.direction - relativeVelocity;
}
} else {
/* Collision. Project on cut-off circle of time timeStep. */
const float invTimeStep = 1.0f / sim_->timeStep_;
/* Vector from cutoff center to relative velocity. */
const Vector2 w = relativeVelocity - invTimeStep * relativePosition;

const float wLength = abs(w);
const Vector2 unitW = w / wLength;
line.direction = Vector2(unitW.y(), -unitW.x());
u = (combinedRadius * invTimeStep - wLength) * unitW;
}
line.point = velocity_ + 0.5f * u;
orcaLines_.push_back(line);
}



this is the code i've extrapolated in actionscript:



var ConeRadius:Number = (m_Radius + m_MoveSpeed * m); //Max 10 steps ahead
var ConeList:Array = new Array();
for (var v:Vehicle = VehicleList; v != null; v = v.m_Next) {
if (v == this) continue;
var xDis:Number = v.m_Vehicle.x - m_Vehicle.x;
var yDis:Number = v.m_Vehicle.y - m_Vehicle.y;
var Dis:Number = xDis * xDis + yDis * yDis;
if (Dis > ConeRadius * ConeRadius || Dis <= 0.001) continue;
var r:Number = v.m_Radius + m_Radius;
var r2:Number = r * r;
var ux:Number = 0.0;
var uy:Number = 0.0;
var dx:Number = 0.0;
var dy:Number = 0.0;
if (Dis > r2) {
//No collision
var xRelVel:Number = m_xVel - v.m_xVel;
var yRelVel:Number = m_yVel - v.m_yVel;
var xW:Number = xRelVel - xDis;
var yW:Number = yRelVel - yDis;
var WLength:Number = (xW * xW + yW * yW);
var dotProductA:Number = xW * xDis + yW * yDis;
if (dotProductA < 0.0 && dotProductA * dotProductA > r2 * WLength) {
var WSqrtLength:Number = Math.sqrt(WLength);
var uxW:Number = xW / WSqrtLength;
var uyW:Number = yW / WSqrtLength;
dx = uyW;
dy = -uxW;
ux = (r - WSqrtLength) * uxW;
uy = (r - WSqrtLength) * uyW;
trace("Direction: " + dx + " " + dy);
}else {
var Leg:Number = Math.sqrt(Dis - r);
if (xDis * yW - yDis * xW > 0.0) {
dx = (xDis * Leg - yDis * r)/Dis;
dy = (xDis * r + yDis * Leg)/Dis;
}else {
dx = -( xDis * Leg + yDis * r)/Dis;
dy = -(-xDis * r + yDis * Leg)/Dis;
}
//trace("Dir: "+dx+" "+dy);
var dotProductB:Number = xRelVel * dx + yRelVel * dy;
ux = dotProductB * dx - xRelVel;
uy = dotProductB * dy - yRelVel;
}
ConeList.push(m_xVel + 0.5 * ux, m_yVel + 0.5 * uy, dx, dy);
}else {
trace("Already Colliding, not bothering with at the moment");
}
}


I then draw all the lines, offset to the vehicles position, since from my understanding, the line/direction is relative to velocity, instead of to the agent.

anyway, i seem to run into this same branch regardless of what i do:


if (dotProductA < 0.0 && dotProductA * dotProductA > r2 * WLength) {
var WSqrtLength:Number = Math.sqrt(WLength);
var uxW:Number = xW / WSqrtLength;
var uyW:Number = yW / WSqrtLength;
dx = uyW;
dy = -uxW;
ux = (r - WSqrtLength) * uxW;
uy = (r - WSqrtLength) * uyW;
trace("Direction: " + dx + " " + dy);
}


the math seems to check out, but when i position my agents where going around the left leg would be shorter than the right, it seems to only want to navigate around the right leg at all costs....

so, hopefully this post isn't too overwhelming, and someone can point out any mistakes i might be making in trying to replicate the code into actionscript.

First of all, thanks for taking the time to formulate a great question! It stands out among most others here :-)

I haven't worked with RVO2, so I'm not sure why it's taking that branch. However, a few things may help:

• ORCA is a bit easier to understand from the perspective of the "solver" -- it's just linear programming.
  
• Some algorithms have biases for turning in a particular direction, so it may be on purpose.
  
• ORCA for instance completely rules out half of the search space, which would similar to what you're seeing.
  

Have you tried drawing the velocity obstacles? See this screenshot I tweeted recently from last weekend's AiGameDev interview. The green planes are what ORCA gets as input, and the red circles (less obvious) are the velocity obstacle. It does make sense visually so you should be getting something that looks reasonable.

Alex

P.S. There's also a masterclass on the topic with Jamie Snape on AiGameDev but it sounds like you're almost there :-)

First of all, thanks for taking the time to formulate a great question! It stands out among most others here :-)

I haven't worked with RVO2, so I'm not sure why it's taking that branch. However, a few things may help:

• ORCA is a bit easier to understand from the perspective of the "solver" -- it's just linear programming.
  
• Some algorithms have biases for turning in a particular direction, so it may be on purpose.
  
• ORCA for instance completely rules out half of the search space, which would similar to what you're seeing.
  

Have you tried drawing the velocity obstacles? See this screenshot I tweeted recently from last weekend's AiGameDev interview. The green planes are what ORCA gets as input, and the red circles (less obvious) are the velocity obstacle. It does make sense visually so you should be getting something that looks reasonable.

Alex

P.S. There's also a masterclass on the topic with Jamie Snape on AiGameDev but it sounds like you're almost there :-)

wow, thanks for the info. i looked up ORCA, and found this paper: http://emotion.inria...-etal-icraw.pdf after reading it. it clicked in what i was doing wrong, i was completely ignoring T, as such, i was essentially simulating one time step in the future, which my velocity is less then my agent radius, so the only time collision avoidance would be consider, is long after the two were colliding.

I've accounted for it, and now my output lines look spot on!=-)

thanks for the info.

edit: ok, seems i mis-jumped about being spot on, while they are taking the correct leg(right or left), it's not extruding out correctly:



the setup is agent A(left) is moving past agent B to the red circle, and agentB is not moving, so it's a static object for the time being.A will try to move only half way through B.

however, when i setup B to move towards A, like so:



then they both map away from each other correctly.

any tips on what i might be doing wrong?

ah, i see, so, should i use VO mechanism for static/non-moving agents, and RVO when interacting with moving agents?

So, after a bunch of work, and studying, i took my understanding of velocity obstacle/RVO, and what i understood of the RVO2 library, and i constructed my own algorithm which does a solid job of collision avoidance with static, or dynamic objects, although it does fail in situations where the number of obstacles give nearly no valid movement locations.

so here's a small demo in flash: http://www.megaswf.com/file/2462485 (might have to play in fullscreen)

and i've attached the source code for anyone interested.

edit:
controls:

hit space to advance one step when not running.
click to drag an agent or node(red dot's when an agent is selected)
when an agent is selected shift-click to add another node.
when no agent is selected shift-click to add another agent.
push delete to delete agent/node selected.

when an agent is selected, you will see all the collision radius's/cones constructed.