局部避障：走廊里两个人怎么不跳舞

走廊里的「舞蹈」

你一定在走廊里遇到过这种尴尬：迎面来了一个人，你往左让，他也往左；你改往右，他也往右……游戏里的 NPC 同样会这样，而且更夸张。

上一课的寻路解决不了这个问题。全局寻路假设世界基本是静止的，每个角色独占自己的路径；可一群角色同时走时，彼此就是不断移动的障碍。处理「附近的人怎么挤得开」的，是单独的一层：局部避障 (Local Collision Avoidance)。

两层分工

局部避障不替代寻路，而是接在它后面：全局路径给出一个「想往哪走、走多快」的期望速度 (Preferred Velocity)，局部避障看看身边的邻居，把它修正成这一帧真正使用的速度。

flowchart LR
  G["全局路径 / 转向"] --> V["期望速度"]
  V --> O["局部避障：ORCA / RVO 求解"]
  N["邻居的位置和速度"] --> O
  O --> R["这一帧的实际速度"]

速度障碍：会撞上的那些速度

要理解避障算法，先换一个视角：不看角色在哪，而看它能选哪些速度。把所有可能的速度画在一张图上，每个点代表一个速度，这张图叫速度空间。

速度障碍 (Velocity Obstacle, VO) 回答一个问题：假设 B 保持现在的速度不变，A 选哪些速度，将来会撞上 B？这些速度在速度空间里刚好围成一个锥：

要避开碰撞，A 只要选一个锥外的速度就行。如果期望速度刚好在锥里，就挑锥外离它最近的那个速度——改动最小，也最不突兀。

动手：在速度空间里避让

下面的画布就是 A 的速度空间。B 在 A 的前方稍微偏上，正迎面走过来。橙色的锥是会撞的速度，冰蓝实心点是 A 现在的速度，空心点是 B 的速度，小黄点是锥顶。鼠标是 A 的期望速度（白圈），大黄点是避障算法最终选出的速度。

先把鼠标放进锥里，看黄点怎么被推到锥的边上；再把「模式」切到 1，看锥顶跳到哪里去了。

为什么 VO 会「跳舞」

用 VO，A 和 B 都假设对方不会变。于是两个人同时往旁边让；下一帧，各自发现对方已经让开了，原来的路线看起来又安全了，于是同时改回来；再下一帧，又同时让……这就是走廊里的那支舞，算法上叫振荡。

互惠速度障碍 (Reciprocal Velocity Obstacle, RVO) 改了一个假设：对方也会避让，而且双方各承担大约一半的避让责任。每个人只让一半，两边加起来正好让开，谁也不用来回改主意。van den Berg、Lin 和 Manocha 在 2008 年的 ICRA 论文里证明了，在论文的条件下，这样做既安全又不振荡。在画布上，这就是模式 1：锥顶挪到了两人速度的中点，A 需要改的量明显变小了。

ORCA：把约束变成半平面

RVO2 库里的最优互惠碰撞避免 (Optimal Reciprocal Collision Avoidance, ORCA) 又往前走了一步：每个邻居对 A 的约束，不再是一个锥，而是速度空间里的一个半平面——「速度要选在这条线的这一边」。所有邻居的半平面叠在一起，剩下的就是可行区域；再用一个低维的线性规划，求出可行区域里离期望速度最近的那个速度。

按 RVO2 文档的说法，ORCA 比早期靠采样的 RVO 更快、更平滑，碰撞保证也更强。

在游戏里怎么用

取舍与常见的坑

小结与练习

• 寻路给大方向，局部避障在期望速度上做近距离修正，两层分工；
• 速度障碍是「保持下去就会撞」的那些速度，在速度空间里是一个锥，选锥外最近的速度即可；
• VO 假设对方不变，双方同时改速会振荡；RVO 让双方各让一半，在论文条件下安全且不振荡；
• ORCA 把每个邻居的约束变成半平面，用线性规划求离期望速度最近的可行速度。

练习：画布里只有一个邻居 B。在代码里再加一个邻居 C（给它自己的位置和速度），让 avoid() 同时避开两个锥。当期望速度同时落在两个锥里时，「挑最近的边界点」还管用吗？再回头想想，ORCA 把每个约束都变成半平面、用线性规划求解，好处在哪里。