四分木で 2D の衝突判定を最適化
今回は四分木 (Quad Tree) について。
オブジェクト同士の衝突判定を行う際、みなさんはどうしていますか？
一番最初に思い付く方法は衝突対象のオブジェクトを配列にでも入れて、総当たりで Sprite#hitTestObject() なんかで判定してしまおうという方法だと思います。この方法でも、対象のオブジェクト数が少なければ特に問題にはなりません。しかし対象のオブジェクト数が多かった場合、総当たりで計算を行うという方法では計算量が膨大になってしまい、とても現実的とは言えません。
Sprite#hitTestObject() などの衝突判定を行う前に、どうにか衝突の可能性があるオブジェクトを限定出来ないか？
そんな時には四分木を使えば計算量が減らせます。
概念的には miscellaneous さんの「四分木」エントリーが参考になります。
四分木を構築する方法で一般的（？）なものは、空間全体をルートとし、2 x 2 の空間に分割しながらノードを構築するというもの。しかしながらこの方法、必ずしも計算量が減るわけではありません。なぜなら、衝突対象のオブジェクトを探すためにルートから該当部までノードをたどる必要があり、検索にもまた、計算コストが掛かってしまうからです。
じゃあ、どうすればいいのか？
その計算量を減らすため、四分木の構築方法は色々な方法が考え出されているようで、その中の一つに線形四分木というものがあります。概念的なものは、マルペケつくろードットコムさんの「その８ 4分木空間分割を最適化する！（理屈編）」がとても参考になります。このエントリーで書いてあることもほぼ受け売りです。
で、本題。今回自作ライブラリに線形四分木用のクラスを追加しました。これを使えば、四分木がどうこう考えなくても計算対象のオブジェクトを限定することが出来ます。その限定したオブジェクトに対して Sprite#hitTestObject() なんかを行えば、計算量も下がります。
※ 描画部分は四分木とはまた別の部分なので最適化していません。あんまり円を増やしすぎると、総当たりに切り替えた時にかなり重くなりますので注意してください。
デモはキーボードで各種操作を行え、四分木 <-> 総当たりの計算量比較が出来ます。オブジェクト同士を繋ぐ線は、衝突判定が必要なことを表しています。計算量がどれだけ減ったかを確認してみて下さい。
ソースは Bitbucket に一式上げてますので、興味の有る方はどうぞ。
使い方は後日、時間がある時にでも…。