Optimal Reciprocal Collision Avoidance

This explanation is currently available in Japanese.

ひとことで

大勢のキャラクターが、相手も同じように避けてくれることを前提に、互いにぶつからない速度を選ぶ方法です。相手ごとに「この先数秒ぶつからない速度の範囲」を半平面（直線の片側）として求め、すべての半平面を満たす速度のうち、行きたい速度に最も近いものを選びます。避ける量を相手と半分ずつ分け合うので、両方が大きく避けすぎて左右に揺れる、ということが起きません。群衆シミュレーションやゲームの群れの移動で広く使われています（RVO2 ライブラリ、Unity の NavMesh の回避など）。

ゲームでの使いどころ

• 群衆・観客・通行人：駅や広場を大勢が行き交う場面。ぶつからずにすれ違う。
• RTS のユニット：大量のユニットを移動させるとき、経路はナビメッシュやフローフィールドで、細かな回避は ORCA で決める。
• ゾンビや敵の群れ：プレイヤーに向かう大量の敵が、互いに重ならず自然に取り囲む。
• ドローンや車の編隊：2 次元でも 3 次元でも同じ考え方で使える。

しくみ

速度障害物（VO）：自分 A と相手 B（半径の合計 $r$、相対位置 $\mathbf{p}$）について、「このまま $\tau$ 秒進むと B とぶつかる相対速度」の集合は、速度空間の中で、原点から B の方向へ開いた、先端が丸く切られた円錐になります。

ORCA の半平面：今の相対速度 $\mathbf{v}_A - \mathbf{v}_B$ が円錐の中にあるなら、円錐のふちまでの最短のずれ $\mathbf{u}$（と、ふちの外向きの法線 $\mathbf{n}$）を求めます。A は、そのずれの半分だけを受け持ち、

という半平面の中から速度を選ぶことにします。B も同じく半分を受け持つので、2 人合わせてちょうどぶつからなくなります。

速度の選択：周りの相手ごとの半平面と、最高速度の円をすべて満たす速度のうち、行きたい速度 $\mathbf{v}^{\text{pref}}$ に最も近いものを、2 次元の線形計画法で求めます。半平面を 1 つずつ加え、今の答えが外れたら、その直線の上で最適な点を探し直します（期待値で相手の数に比例する時間）。すべてを満たす速度がない（混みすぎ）ときは、はみ出しが最小の速度を選びます。

実装のポイント

• 近い相手だけ：相手は近い順に 10 体程度に絞ります。近傍探しには空間ハッシュや kd 木を使います。
• 先読みの時間 $\tau$：長いほど早めに避け始めますが、混雑した所では動けなくなりやすくなります。人なら 1〜3 秒程度です。
• 行きたい速度：経路探索で決めた次の曲がり角の方向に、希望の速さを掛けたものです。ゴールの近くでは減速させます。
• 壁：静止した障害物は、相手が避けてくれないので、半分ではなく全部を自分で受け持つ半平面として加えます。

つまずきやすい点

• 全員が同じ向きに避ける：完全に対称な配置（円の入れ替わりなど）では、判断が決まらず止まることがあります。ほんの少しの乱れ（行きたい速度にわずかな雑音）を足すと解消します。
• 相手が避けない：プレイヤーや、ORCA を使わない物体は、半分を受け持ってくれません。それらに対しては、全部を自分で避ける半平面にします。
• 速度だけで決める：ORCA は速度を選ぶ方法で、加速度の上限を考えていません。急に向きが変わるのが気になる場合は、選んだ速度へなめらかに近づけます。

デモで試すこと

1. 「円の反対側へ入れ替わる」では、22 人が一斉に反対側へ向かい、真ん中でぶつからずにすれ違います。左下の「重なっている組」がほぼ 0 のままです。
2. 「避けない」にすると、全員が真ん中で重なり（赤）、「近い相手から離れる力」では、押し合って渋滞し、揺れながら進みます。
3. 白い 1 人には、相手ごとの半平面の境目（紫の線）と、行きたい速度（灰色）・選んだ速度（黄緑）の矢印が表示されます。混んでくると線が増え、選べる速度が狭まっていきます。
4. 「先読みの時間 τ」を短くすると、ぎりぎりまで避けずに急に曲がり、長くすると早めに大回りします。「2 つの群れが十字に交差」も試してください。