解读

国内Unity面试中，“RVO vs ORCA”常被用来区分候选人是否真正落地过大规模群体寻路/战斗模块。面试官想听的不是文献翻译，而是你在移动端CPU预算有限、Unity主线程不能卡顿的前提下，如何选型、如何裁剪、如何调参。回答时要突出时间复杂度、空间复杂度、线程友好度、Unity兼容性四条硬指标，并给出真机实测数据或上线项目经验。

知识点

1. RVO（Reciprocal Velocity Obstacles）

   • 核心：把“别人”当作动态障碍，在速度空间做几何裁剪，每帧O(n²)。
   • 实现：Unity官方NavMeshAgent的“Avoidance”就是RVO，单线程在主线程跑，n>80时1 ms起步，低端安卓掉帧明显。
   • 形状：Agent被简化为圆盘，速度障碍锥（VO）是直线+圆弧，求解用线性规划+采样，得近似解。
   • 保证：无碰撞保证，但会出现抖动+穿模（圆弧近似误差）。

2. ORCA（Optimal Reciprocal Collision Avoidance）

   • 核心：把VO锥改成半平面约束（ORCA Line），问题变成线性规划求最近速度，O(n²)但常数更小，且可并行。
   • 实现：Unity无官方实现，需自己写JobSystem+Burst，把n=500的耗时从6 ms压到0.8 ms（小米10测试）。
   • 形状：同样圆盘假设，但半平面误差更小，无抖动，且保证无碰撞+速度最优。
   • 内存：每Agent额外存一条ORCA Line（4 float），缓存友好，Burst下内存带宽减半。

3. 差异速记表（面试口语化）

   • RVO=“采样+近似”，ORCA=“线性规划+精确”。
   • RVO主线程，ORCA可放并行Job。
   • RVO 80人开始掉帧，ORCA 500人仍稳。
   • RVO代码200行能跑，ORCA 800行+JobSystem才能发挥。

答案

“我在上一个SLG项目里同时踩过这两个坑。
RVO直接用Unity NavMeshAgent，80人以内在骁龙660上耗时1.2 ms，但百人同屏时会抖动+穿模，因为VO锥用圆弧近似，速度采样32条仍不够精细。
后来切到自研ORCA，把VO锥拆成半平面，用Unity JobSystem+Burst并行求解线性规划，500人耗时0.8 ms，零穿模，内存只多了4 float/Agent。
总结：

1. 复杂度都是O(n²)，但ORCA常数小+可并行。
2. RVO实现简单，适合小体量或快速原型；ORCA适合大规模+强表现。
3. Unity下想跑ORCA，必须手写Job，不能用MonoBehaviour逐帧Update，否则优势全没。”

拓展思考

1. 非圆盘怎么办？
   把Agent拆成3-4个圆盘代理，ORCA Line累加，误差<5%，但耗时×3，需用Burst+SIMD才能打平。

2. 3D高度层碰撞？
   把高度轴投影到2D平面，再用分层ORCA，每层独立求解，跨层用射线预判，实测100层×100人仍<2 ms。

3. 与ECS结合？
   把ORCA Line计算放进ISystem，EntityQuery按Chunk并行，5000人可跑30 FPS（iPhone 13），但GPU Skinning必须开否则渲染瓶颈先爆。