ひとことで
衝突判定を、「ぶつかっていそうな組を大まかに絞る」広域判定（ブロードフェーズ）と、「残った組を正確に調べる」詳細判定（ナローフェーズ）の 2 段階に分ける考え方です。物体が 個あれば組は 通りあり、全部を正確に判定すると、物体の数の 2 乗に比例して時間がかかります。実際に接触しているのはほんの一部なので、まず AABB のような簡単な形で候補を絞り、重い判定は候補だけにかけます。ほぼすべての物理エンジンがこの構成です。
ゲームでの使いどころ
- 物理エンジン：剛体どうしの接触を毎フレーム求める処理の、最初の段。
- 弾と敵、プレイヤーとアイテム：数百〜数千の物体どうしの当たり判定。
- トリガー・範囲の検出：範囲に入った物体のイベントを出す。
- AI の近傍探し：近くの敵や味方を探す処理にも、同じ広域判定の構造を使い回せる。
しくみ
広域判定：物体を AABB で囲み、AABB が重なる組を効率よく探します。代表的な方法は 3 つです。
| 方法 | しくみ | 向いている場面 |
|---|---|---|
| 一様な格子・空間ハッシュ | セルに登録し、同じセルの物体どうしだけ比べる | 大きさのそろった多数の物体 |
| スイープ・アンド・プルーン | 軸に投影した区間の重なりを、端点の並びで探す | 大きさがばらばら、動きが少ない |
| 動的な BVH（AABB 木） | 箱の木をたどって重なる相手を探す | 大きさも動きもばらばら、レイキャストと共用 |
詳細判定：候補の組について、実際の形（球・カプセル・箱・凸多面体・メッシュ）どうしの正確な判定を行い、接触点・法線・めり込みの深さを求めます。形の組み合わせごとに専用の関数（球と球、球と箱など）を用意し、一般の凸形状には GJK や分離軸定理を使います。
広域判定がうまく働けば、全体の手間は「物体の数 + 候補の数」に比例し、2 乗の増え方を避けられます。
実装のポイント
- 形の組み合わせの表：形の種類が 個なら、 の関数の表を用意して、組み合わせで呼び分けます。
- フィルタを広域判定で：「味方の弾は味方に当たらない」のような衝突のレイヤー・マスクは、詳細判定の前に候補から外します。
- 接触を使い回す：前のフレームで接触していた組は、次のフレームも接触していることが多いので、接触点や積み上げた力を使い回すと安定します（ウォームスタート）。
- 静止した物体を眠らせる：止まっている物体どうしは判定を省き、動く物体との組だけを調べます。
つまずきやすい点
- 広域判定の箱が大きすぎる：AABB が物体よりずっと大きいと、候補が増えて絞り込みの意味がなくなります。
- 巨大な物体：床や地形のような巨大な物体は、ほかのすべてと候補になります。静的な地形は別の構造（BVH など）に入れ、動く物体からそこを問い合わせる形にします。
- 組を 2 回数える：格子の複数のセルにまたがる物体は、同じ組が何度も候補に上がります。重複を取り除きます。
デモで試すこと
- 円と回転する箱が動き回っています。広域判定で残った候補の組が青い線で結ばれ、詳細判定で本当に接触していた物体が赤くなります。
- 左下で、「全部の組」と「詳細判定にかけた組」「接触していた組」を比べてください。広域判定があれば、候補の数は接触の数に近くなります。
- 「なし（全部の組を詳細判定）」に切り替えて、「物体の数」を増やすと、右下のグラフの判定時間が急に増えます。格子やスイープ・アンド・プルーンでは、ゆるやかにしか増えません。
- 「候補の組を線で表示」を切ると、判定の結果だけを見られます。