衝突判定とQuadtree — 近いものだけ比べれば足りる
画面に弾が40個飛んでいるゲームで、「どれとどれがぶつかったか」を調べたい。素直に書くと、すべての組み合わせを1つずつ確かめることになります。40個なら780通り、200個なら19,900通り――個数の2乗で増えていくので、あっという間に間に合わなくなります。
でも考えてみると、画面の左上と右下にある弾は比べる前から当たらないと分かる。だったら近くにいるものだけ比べればいい。この「近い相手を素早く絞り込む」ための入れ物がQuadtree(四分木)です。下の図1で点の数を増やし、総当たりとQuadtreeの距離計算の回数を見比べてください。
4分割を、必要なところだけ繰り返す
Quadtreeの作り方は驚くほど単純です。まず領域全体を1つの箱として点を入れていき、入っている点が一定数(たとえば4個)を超えたら、その箱を4つに割る。割ったあとも混み合っている箱だけ、さらに4つに割る――これだけです。結果として、点が密集している場所は細かく、空いている場所は粗いままという無駄のない分割ができあがります。図1で点を増やすと、混んだ一角だけ枠が細かくなるのが見えるはずです。
衝突判定は2段構えで考えます。まずQuadtreeで「当たっている可能性のある相手」だけを拾い出す(ブロードフェーズ)。次に、拾えた少数の相手にだけ正確な距離計算をする(ナローフェーズ)。総当たりが O(n²) なのに対し、点がほどよく散らばっていればブロードフェーズはおおむね O(n log n) まで下がります。ただし全部の点が1か所に固まっていると絞り込みが効かず、総当たりに近い回数まで戻ってしまう――これが空間分割の弱点です。
この考え方はゲームだけのものではありません。地図アプリで「画面内のピンだけ探す」、当たり判定を持つ物理エンジン、画像の領域分割、そして地理情報の検索インデックス――「広い空間から近いものを速く見つける」場面には、たいてい同じ発想の木構造が入っています。
- Quadtree（四分木）
- 2次元の領域を、混み合った箱だけ4分割していく木構造。3次元版はOctree（八分木）。
- ブロードフェーズ
- 「当たっているかもしれない候補」をざっくり絞る段階。ここを速くするのが空間分割。
- ナローフェーズ
- 絞り込んだ候補だけに正確な衝突判定を行う段階。
- O(n²)
- 個数の2乗で計算量が増えること。総当たりの比較回数は n(n−1)/2 になる。
- 容量（capacity）
- 1つの箱に入れられる点の上限。超えると4分割する。小さすぎると木が深くなりすぎる。
まとめ
衝突判定の高速化は、賢い計算をすることではなく、比べる相手を減らすことで達成されます。Quadtreeは混んでいる場所だけ4分割を繰り返すという単純な規則で空間を仕分け、「近くにいる候補」を一瞬で取り出せるようにします。総当たりの O(n²) が、散らばった配置なら O(n log n) 程度に。逆に一点集中では効果が薄れるので、データがどう散らばっているかを見て使うのがコツです。