LOCKYOUで学ぶ

パラフドーム後日談

いえ～いパラフドーム後日談と見せかけた4分木空間分割によるオブジェクトの衝突判定の効率化講座はじまりはじまり～
ヒャッハ～～～！！！

やけにハイテンションだな

さて、この衝突判定の効率化の考え方もよそのサイトを参考にしてるわけで、
今回はこのサイトだね
その８ 4分木空間分割を最適化する！（理屈編）
~~この人のサイト見ればここの講座は見る必要ないね~~

この○×つくろーの人はこの本を参考にしたみたいだね
~~なんだあのたっかいもの……~~
ゲームプログラミングのためのリアルタイム衝突判定

どこを参考にしたかは置いておいて
タイトルにもなってる「4分木空間分割」ってなんだ？
どのくらい効果があるんだ？

え＝っとまずどのくらい効果があるのかっていうのだけど
これを見てくれ、こいつをどう思う？

実際のオブジェクトの衝突判定か？左上にある灰色の四角が0でボールは30まであるから31個か
下にいろいろ書いてあるやつは何だ？

左下にあるボタンは0の灰色の四角のオブジェクトを動かすボタンだね
右下のやつは今は「ペア数」ってやつに注目してもらいたいね
それ以外はまたあとでね

ペア数……何がペアになるかって言ったらオブジェクト同士しかねえから……
オブジェクト同士の衝突判定の回数か？

ナイスでーす！
前回でも言ってたけどオブジェクトが31個なら総当たりで465回だったよね

でもこのペア数を見てたら大体100前後当たり、多くて200行かないぐらいだな

歪みないでしょ？

で、ボールの色が変わってるのは何だ？
黄色は0に当たってるっていうのは何となくわかるが……

青が基本のボールの色なんだけど、別の色になってるのは
緑色が0と衝突判定しているもの
黄色は0と衝突しているものだね

総当たりの場合なら 0と1のオブジェクト、0と2、0と3、0と4、0と5、0と6……ってやる必要があったんだけど
この場合は0と3、0と11、0と17、みたいな感じで特定の条件を満たした奴だけ0と衝突判定すればいいようになってるよ

大体どれほど衝突判定が減るかは分かったが
具体的にどうやって実装するんだ？

じゃあまずここにがありますと

で、これを縦横に分けると

……4分木空間分割っていうやつか？

何気に鋭いですね……
で、分割した空間を部屋って呼ぶことにして、
右上、左上、右下、左下のそれぞれに入ってる部屋は別の部屋に入ってるやつとは
衝突判定する必要ないでしょ？

そうだな
……じゃあ線にまたがってるオブジェクトはどうしたらいいんだ？

その場合は分割する前の大きい部屋に属するって考えるよ
こんな感じの図でわかるかな？
そんで上の階層にある部屋は下にある階層を内包してるって感じだから……

上ににあるオブジェクトは分割された後の部屋にあるオブジェクト全部と当たる可能性があるっていう考えでいいんだな

そうだね
そしてこの部屋を気のすむまでさらに4分割することができるよ
これが4分木空間分割ってやつね

これは…… 一番上の黒い部屋にあるオブジェクトは下にある青い部屋と赤い部屋にあるオブジェクト全てと当たり判定を行う必要があるんだな？
ただ青い部屋に関しては、例えば一番左の青い部屋にあるオブジェクトは16個ある赤い部屋のうちその直下の4つのみと当たり判定すればいいってことか？
衝突判定をする必要があるのは同じ部屋のオブジェクトとその直下にある部屋全部のオブジェクトってわけか

ええぞ！ええぞ！
こうすれば衝突判定を少なくできるっていう寸法になるね
ちなみに4分木っていうのはこんな感じのデータ構造ね
上の図とずいぶん似ているでしょう？

○がノード、線がエッジという名前で、ノードはなんかしらデータを持ってるっていう形です
そしてノードから出てる線は自分以外のどのノードを見ることができるかという感じです
正直ふわふわした概念的な話なのでべつにここは特に気にする必要はないと思います

考え方は大体これで良しとして、次は具体的にどう実装してくかを見ていくね
じゃ、またね～