AI - 碰撞避免算法分析(VO/RVO)

VO/RVO

VO和RVO的原理本身理解起来比较简单的，就是根据两个圆形的相对半径，相对速度，相对位置，求出碰撞区域，然后将速度移出碰撞区域。VO是双方都是当作对方速度不变的情况下，各自都将速度完整的移出了会碰撞的速度域，因此会抖动，RVO则是双方都默认对方速度也会移一半，因此自身也只移一半。
VO的原理
RVO的原理与VO类似，VO通过求出一个速度向量u，让物体的速度加上向量u，来移出会碰撞的速度域，RVO只移一半就行，即物体的速度加上向量u/2

数学相关的判断

代码实现主要是解一些数学题

求碰撞速度域

比如，即是求点到一个圆的两个切线。

//求point 到 以circleCenter为圆心半径radius的圆的切线
pair<Vec2, Vec2>GeometryMath::calculateTangetLines(Vec2 point, Vec2 circleCenter,float radius){//点到圆心的长度，上图红线float distSq = circleCenter.getDistanceSq(point);//len是点到切点的长度float len =sqrt(distSq - radius * radius);//上图盖住部分红线的绿线
    Vec2 temp = circleCenter - point;
    temp.normalize();
    temp *= len;//左右各旋转夹角，即为切线点float cosA = len /sqrt(distSq);float sinA = radius /sqrt(distSq);//顺时针float x1 = temp.x * cosA - temp.y * sinA;float y1 = temp.x * sinA + temp.y * cosA;//逆时针float x2 = temp.x * cosA - temp.y *(-sinA);float y2 = temp.x *(-sinA)+ temp.y * cosA;returnmake_pair(Vec2(x1, y1),Vec2(x2, y2));}

判定是否碰撞

判定速度是否在碰撞域内，即判定速度点与在左切线的右边，并且在右切线的左边

// 点 c 在a到b向量的左边, 即∠abc 小于180°boolGeometryMath::isInLeft(Vec2 a, Vec2 b, Vec2 c){float e =getVectorCross(a, b, c);returngetVectorCross(a, b, c)<0;}// 点 c 在a到b向量的右边, 即∠abc 大于180°boolGeometryMath::isInRight(Vec2 a, Vec2 b, Vec2 c){returngetVectorCross(a, b, c)>0;}// 点 c 与a到b向量共线, 即∠abc 等于180°boolGeometryMath::isCollineation(Vec2 a, Vec2 b, Vec2 c){returngetVectorCross(a, b, c)<0.00001;}floatGeometryMath::getVectorCross(Vec2 a, Vec2 b, Vec2 c){
    Vec2 vectorBA = a - b;
    Vec2 vectorBC = c - b;return vectorBA.cross(vectorBC);}

bool isCollision;bool isFirstLeft =GeometryMath::isInLeft(Vec2::ZERO, verts.second, verts.first);if(isFirstLeft){
            isCollision =GeometryMath::isInLeft(Vec2::ZERO, verts.second, relativeVelocity)&&GeometryMath::isInRight(Vec2::ZERO, verts.first, relativeVelocity);}else{
            isCollision =GeometryMath::isInLeft(Vec2::ZERO, verts.first, relativeVelocity)&&GeometryMath::isInRight(Vec2::ZERO, verts.second, relativeVelocity);}

求速度转移向量u

选择更近的一条切线边，求出速度到切线上的垂直点，作为新的速度，两者相减即为u
向量a与单位向量n的点积，即为a在n方向的投影长度

Vec2 vert = relativeVelocity.getDistance(verts.first)< relativeVelocity.getDistance(verts.second)? verts.first : verts.second;//求切线的单位向量
Vec2 v2 = vert.getNormalized();//速度在切线上的投影长度float n = relativeVelocity.dot(v2);
Vec2 v = v2 * n;
Vec2 u = v - relativeVelocity;

VO的效果：

RVO的效果:

实际写代码中VO其实还有个问题，就是在当前帧求出了新的速度的话，如果在这一帧立刻更新位置的话，在非常近的情况下。是极有可能产生碰撞的。
因为VO抖动的问题就是，在第一帧，双方可能碰撞于是计算了新的速度相互错开(此时的新速度在下一帧计算VO是不会碰撞的)如果当前帧根据新速度更新位置不会产生碰撞。而到了第二帧，双方根据此时的速度计算不会碰撞，于是新速度调整回了最佳速度(调整回的新速度在下一帧计算VO是会产生碰撞的，所以之后会产生抖动)，而此时如果根据当前帧调整的最佳速度立刻更新位置，在非常近的情况下，是会直接产生碰撞的