具体的分析网上有挺多的，理论本身还是比较好理解的，这里直接转载别人的了ORCA(RVO2)算法优化整理版
ORCA源码地址
RVOSimulator相当于整个碰撞避免逻辑的管理模拟器。
一些参数
timeStep_：管理器每次模拟的时间间隔，传入的基本就是游戏运行的每帧时间
kdTree_：一个数组结构的KD树，用来管理每个机器人的相邻目标
agents_：管理器控制的机器人
obstacles_：管理器控制的静态障碍物
主要函数：
addAgent：向管理器添加需要进行碰撞避免处理的机器人
doStep：模拟一次所有机器人碰撞避免处理：先构建kd树，计算每个机器人的相邻目标，在计算新的速度，然后更新位置
kd树的原理之前文章有分析过，这里先跳过了
KDTree
实际碰撞物的代理目标，可以每帧中把游戏实际物体的参数传入，通过RVOSimulator计算后，再取出对应代理目标的位置信息更新游戏实际物体
类似这样：
Agent参数
agentNeighbors_：相邻的动态目标
obstacleNeighbors_：相邻的静态障碍物
orcaLines_：储存的半平面信息
newVelocity_：新的避障速度
*position_*位置
prefVelocity_：最佳目标速度
velocity_：当前速度
id_：唯一id
maxNeighbors_：最大避障邻居数(太遥远的过多邻居没有避障意义)
maxSpeed_：最大速度
neighborDist_：查找避障领据的判定位置(太遥远的目标没有避障意义)
radius_：物体半径
timeHorizon_：提前避障的时间，即只判定在一定时间范围内可能的碰撞
timeHorizonObst_：静态物体提前避障的时间
避障核心代码入口
void Agent::computeNewVelocity()
创建静态障碍物的ORCA半平面
其中障碍物的类：当前point_和下一个障碍物nextObstacle_的point_会构成一条直线，unitDir_是当前point_指向下一个point_的单位方向向量，isConvex_表示是否凹角
半平面的坐标计算都是以自身位置为坐标系计算。因此障碍物直线的坐标也要转换一下。即relativePosition1
代码里invTimeHorizonObst根据不同的判定时间，向量长度会有不同的缩放，但相对比例是不变的，分析的时候可以都当成1来处理，来忽略掉。
det(invTimeHorizonObst * relativePosition1 - orcaLines_[j].point, orcaLines_[j].direction)
这行代码是半平面的点到障碍物直线一个端点的向量，与半平面单位方向向量取叉积，因为叉积的模等于两矢量各自的模的积再乘以两矢量夹角的正弦，其中一个向量为单位矢量，则结果就是另一个向量到单位向量直线上的垂直距离。
>= -RVO_EPSILON 叉积大于0表示在向量逆时针方向,即新的障碍物直线端点在已处理的半平面右边
(-relativePosition1 * obstacleVector) 求点积，两矢量模相乘，再乘夹角的余弦。
即 s = |-relativePosition1|*|obstacleVector| * cosθ / |obstacleVector|
s为物体坐标在障碍物直线上的投影点到障碍物直线起始点的长度，即上图中红色线段长度。s的大小可以表示此时物体在障碍物直线的左边，右边，还是两个端点之间
distSqLine 为物体坐标到障碍物直线的垂直记录，即上图中灰色线段长度
已经碰撞，对于物体相对于障碍物直线的不同碰撞点，做不同处理
因为静态障碍物是不会动的，因此半平面直接以物体自身为目标点，方向以垂直偏离碰撞点为目的，即上图中白色箭头。
物体与障碍物直线起始点2，即右端点相撞。和左端点类似，只是加了一个判断，就是下图中，obstacle2-unitDir在红线右侧的方向的话，就忽略这条障碍线的碰撞处理，以相邻边的障碍线处理为准
分析两根leg线是否会和障碍物直线的相邻边碰撞
根据当前速度在速度障碍域的不同位置做不同处理
上述t的含义表示了当前速度更靠近左右两边哪个端点。0-0.5更靠近左，0.5-1更靠近右，0.5正好居中。
tleft和tright就是判断当前速度投影到leg直线上，依次判断在leg射线上的哪个部分。小于0，则在leg射线的外部
判断物体是否以远离速度障碍域两个端点为目标
创建动态物体间的ORCA半平面
首先定义了几个相对参数
relativePosition：相对位置
relativeVelocity：相对速度
combinedRadius：自身半径视作0后，对方的相对半径
处理双方未碰撞的情况
即distSq > combinedRadiusSq
判断是否往小圆上计算u
求u的代码含义也在上图中标出来了
处理双方已碰撞的情况
本质也是往在圆的里面远离圆心，和未碰撞往小圆上计算u的原理一样
计算半平面的位置
u计算出来后半平面的位置也就确定了
半平面交集求解
lines：所有半平面
radius：求解时的限定圆形半径(即物体最大速度)
optVelocity：当前物体的期望速度
directionOpt：默认false，执行linearProgram3(交集没有可行解)为true
result：当前步骤求出的最新速度
初始一下默认优化速度
遍历所有半平面，对每个半平面进行线性处理
只处理在当前半平面右侧的速度，左侧的速度本身就属于当前半平面的可行解。(注意叉积大于0虽然是逆时针方向。但是这里的是result指向lines[i].point，不是lines[i].point指向result)
线性规划求解
计算当前半平面的可行解，返回有无可行解
dotProduct就是向量lines[lineNo].point在lines[lineNo].direction上的投影长度。即上图中两个黑色线段的长度
圆的半径，即物体最大速度，必须在半平面的左边才能有解。即上图中粉色线必须大于紫色线。
紫色线标为len，即物体原点到半平面的垂直距离。
需要 radius > len
==>>radius * radius > len * len
(灰线长度为 |lines[lineNo].point|，根据勾股定理)
==>> sqr(radius) > absSq(lines[lineNo].point - sqr(dotProduct)
==>> sqr(radius) + sqr(dotProduct) - absSq(lines[lineNo].point > 0
==>> discriminant > 0
因此，下面代码表示无解退出
同时sqrtDiscriminant还表示上图黄色线段的长度
根据勾股定理
discriminant = sqr(radius) - sqr(len)
(sqr(len) = absSq(lines[lineNo].point - sqr(dotProduct))
==>> discriminant = sqr(radius) - absSq(lines[lineNo].point + sqr(dotProduct)
tLeft和tRight即为上图中橙色和蓝色线段的长度。分别表示圆的两个交点到lines[lineNo].point的距离
比较已处理过的半平面
在当前 lineNo 半平面线性规划求解时，需要和之前处理过的半平面对比来缩小解的范围。最初的解范围是速度圆和半平面直线的两个交点范围。
t 的含义是上图中两个半平面交点 o 到 当前半平面 lines[lineNo].point 的距离
因为
图中红色箭头为向量 lines[lineNo].point - lines[i].point
半平面的方向向量，长度都为1， 即 |lines[i].direction| = 1
叉积为两向量模乘正弦，因此 numerator 为上图中紫色线段长度，即 lines[lineNo].point 到 i 半平面的垂直距离
此时以两个半平面交点 o 为起点，画一个向量 lines[lineNo].direction ，可以得出 denominator 为上图中棕色线段的长度
又因为 |lines[lineNo].direction| = 1
并且 t / |lines[lineNo].direction| = numerator / denominator
即上图黄色线段
可行解最初的范围是大于 tLeft 小于 tRight
上图中，当 i 半平面的方向在 lineNo 半平面的右边。此时的可行解一定是大于交点 o 的区域
因此 denominator < 0 时， 需要 t 和 tLeft 对比谁更大。反之同理
directionOpt 为 true 时，不会有可行解，直接根据期望速度与半平面方向是否同向来取交点
无可行解
numObstLines：静态障碍物半平面的数量
beginLine：索引id，表示从哪条半平面开始无法求出可行解
另外三个参数和之前一样
这行代码是求当前新解与之后的每条半平面的垂直距离，以处理距离最远的半平面为准。我的理解是，离的最远的半平面，是碰撞机率最大的，因为他需要最大的调整速度，才能够调整回不碰撞的速度可行域
这个函数里的遍历都是去掉了静态障碍物的半平面的，因为静态障碍物自身是无法进行碰撞避免处理的
即让之前的有解线性集合往当前无解半平面靠近。这里都是靠近一半的距离，我的理解是应该是认为双方躲避的责任相等，所以是靠近一半
i++往后续的半平面遍历，如果新的半平面到红点的距离，小于distance，说明碰撞的概率不如 半平面i，因此先忽略。
旋转的角度是根据 normalize(lines[j].direction - lines[i].direction) 设置的
我试着改变了 lines[i].direction 的长度，使旋转的角度不同
len为1是旋转1/2的夹角，len越接近0，旋转后的半平面越接近 i 半平面，len越大，旋转后的半平面越偏离 i 半平面。
静态图
以下是几种设置不同旋转角度后，求得的速度，以四个球最下方的那个球为分析目标，
三根不同的射线就是三条半平面，此时的三个半平面是没有可行解的。球的黑点位置就是新的速度朝向。
设置不同len时的，物体的新速度朝向：
len = 1，旋转1/2角度
动态效果
大量物体
有的时候出现双方，避障权重一样，速度一样，方向相对，位置也是相对。
最后都静止不动了。以上述例子来看，下面的球速度始终是垂直向上，上面的球速度始终是垂直向下。双打的速度始终在碰撞半平面的可行域里，但是为了避免碰撞，双方的速度越来越小
但实际项目中，一般不会有这种情况，因为此时只要一个外来的变化量，或者双方目标速度，权重，啥的有一点点变化。就随便一个微量情况，打破了这种平衡，物体就会继续移动下去。只是可能会出现物体在原地磨蹭了很久之后，才相互错开。因此。具体项目在使用源代码的时候，还需要根据不同需求做不同的调整
另一个问题是，在大量物体的情况下，代码运行过程中，实际仍会有许多物体运行到这段代码