4分木空間分割を最適化する!(理屈編)ゲーム空間に置いたオブジェクトを総当りで衝突判定する事ははっきりと非効率だと言えます。60FPSのゲームの1フリップ約16.6ミリ秒の内衝突判定に10%の時間余裕(1.66ミリ秒)を与えられたとします。1000回の衝突判定に1ミリ秒かかるなら(1000回/msec)、判定回数は1660回以下に抑えないと間に合いません。総当りだとこれは58オブジェクトくらいで限界です。判定時間が200回/msecならオブジェクトはたった18個で限界。これはどう考えても節約が無いとゲームになりません。オブジェクトの全ての位置が決まった時、自分とぶつかる可能性があるのは自分の周りのオブジェクトだけです。遠い所にある物は判定する必要すらありません。Partitioning)です。Partitioning)です。4分木分割の理屈は非常に簡単です。空間を正方形(長方形でももちろん可能)とします。衝突対象のオブジェクトはこの空間内に置かれます。この一番大きな空間をルート空間と呼んでおきます。次に、空間を上下左右に4分割し(下図参照)、ルート空間に空間オブジェクトとして登録します。その分割線をオブジェクトがまたいでいなければ、オブジェクトは分割されたより小さい空間内にあることがわかります。そこで、その小空間をさらに4分割して同様の登録とチェックを繰り返します。Level)に達したら分割を終了します。衝突に関して、上の図では一番大きな球と右半分の空間にあるオブジェクトとは空間が異なるので衝突しないことがこの段階でもうわかっています。この衝突チェックは行いません。真ん中の境界線をまたいでいる小さな球は、他の3つとの衝突チェックが必要になります。それでも、総当りで6回の判定が、上の場合は3回と半分に減っています。これはオブジェクトの数が多くなるほどより効果的になります。4分木の理屈は以上のように簡単なのですが、いざこの通りにまともに組んでみると、これが激烈に『遅い』ということもすぐにわかります。衝突判定が遅いということではなく、空間にオブジェクトを適切に登録する事、また動いているオブジェクトについては登録削除と再登録をする、これがかなりの手間になるんです。本当に何も考えていない場合についてですが、適切な分割空間にオブジェクトを登録する時には樹状なのでo(logs)レベルの手数がかかります。sは分割空間の総数です。動いているオブジェクトの位置を変更する時には、空間内のそれの検索が必要です。これは線形検索となり平均o(s/2)かかります。取り除くのはo(1)で出来ますが、再登録にまたo(logs)かかります。これを全オブジェクトに対して行うと平均でおよそo(n*s/2+nlogs)となります。これは空間の数をs=500くらい、オブジェクトをn=100個とした場合、毎回平均25000回強の力技検索が必要である事を示しています。これでは全然駄目なわけです。衝突判定回数を劇的に減らす4分木はパフォーマンス向上に必要です。まともに考えると遅い。4分木をどう最適化すれば良いのか?この章ではその理屈をじっくりと検討してみます。本章で試行錯誤した4分木空間分裂の実装方法については次章に回します。オブジェクトが登録されている空間にo(1)でアクセスするまともに実装した中で最も遅いのは、木の中からオブジェクトを探す部分です。木のどこにあるかわからないので、ルート空間から丹念に探していくしかありません。これは大変質の悪い線形検索です。「木の中からオブジェクトを探す」という考え方に固執してしまうと、どれだけ頑張ってもo(logs)レベルの検索以下にはできません。これ以上の速度o(1)を期待するには、オブジェクトが空間を知っている状態、つまりオブジェクト→空間のハッシュテーブルを作成するしかありません。任意オブジェクトへのポインタ};CCellというのが空間オブジェクトで、m_pObjectが登録するT型のオブジェクトへのポインタです。テンプレートにするのは登録されるオブジェクトが何かわからないためです。逆にこうしておくと分木を使いまわせます。4分木にはオブジェクトではなくてこの構造体を登録することになります。オブジェクトの空間登録をo(1)で行うオブジェクトを包んだOBJECT_FOR_TREE構造体を木の中に素直に登録するとo(logs)レベルの手間がかかります(sは空間の数)。具体的には、まずルートとなる一番大きな空間の境界線にオブジェクトがまたがっているかををチェックします。線をまたいでいるなら、このオブジェクトはルート空間に所属します。またいでいない場合、それを包んでいる小さな空間にレベルを落とします。小空間でも同じ事を繰り返し、オブジェクトを完全に包む一番小さな空間を探していきます:「logなら割といいんじゃ?」と思うかもしれません。1つの空間に所属するか否かを検討するには、オブジェクトと境界線の交差判定をしなければなりません。交差していないとなると今度は4つある空間のどこに所属するかの検討です。これは難しい事はありませんが手間と手数はかかります。メモリの制約などから小空間の分割回数を7〜8回くらいにしたとしても、一番小さなオブジェクトはこの作業を最大8回繰り返す事になります。オブジェクトが動いている場合はそれを全オブジェクトで毎回行う必要があり、その作業は十分に体感できるほど遅くなります。この節ではこの登録作業をo(1)にしようと目論見ます。オブジェクトの境界範囲から空間をズバッと指定するハッシュを作ろうというわけです。これは可能なんです!その準備として、まずは「モートン順序」からお話を始めます。モートン順序ルート空間は言わずもがなで1つしかありません。それを4分割した親空間には、空間が4つ存在します。親空間1つ1つを4分割すると、子空間が16個、同様な分割で孫空間は64個となります。Order)」と言います。親空間の1つを分割した子空間も、全く同じように番号を振ります。ルールはそれほど難しくありません。これを見た誰しもが「何でこんな番号の振り方をするのよ?」と疑問に思うと思います。この振り方は実に理にかなっているんです。モートン順序にならんだ空間は上位空間の情報を持つこの並びの本質は、ある空間番号を見るだけでどの上位空間に所属しているかがわかってしまう点にあります。上の孫空間の中央下方にある「45番」の空間に注目して下さい。この空間の上位空間のモートン順序は「親空間の2番(2番)、その親空間内の子空間の3番(11番)、子内孫空間の1番(45番)」となっています。下の図で確認してみて下さい:(それぞれモートン順序で考えてください)ここで孫空間45番を2進数で表現してみます:このように、数値を2つずつに区切って10進数に直すと、上位にある子や親の番号がそのまま出現します!これはどの孫空間番号でも、それどころかどの空間分割レベルであっても引き継がれる性質であり、所属空間を判定するのに持って来いなんです。点の座標値から所属するモートン空間番号を出す上の45番の2bitずつの情報。これは親や子空間の軸の情報も含んでいます。この1bit目の0はX軸の情報です。具体的には「X軸で見ると原点の左側にある」という情報を含んでいます。2bit目はY軸情報で、「Y軸は原点の下にある」となっています。ここから45番の空間は親空間単位で見れば左下(2番)にあると判断できるわけです。同じ事は子空間でも確認できます。ここから、空間内の点がどの空間番号に属するかを叩き出す事ができます。例として、今ルート空間の辺の長さを100として、孫空間を対象とし点(48,80)の空間番号を算出してみます。孫空間を構成する小空間の辺の長さ(単位長)を求めます。これはU=100/23で算出できますね。