80)は64分割されている孫空間の左から3番目、上から6番目に位置する」という事を意味しています。この位置は、実は先ほどの45番の空間に当たります。110)です(3桁あるのは分割回数が3回であるところから来ています)。この2進数と先ほどの45の2進数表示と見比べてみます:2bit単位に区切った1bit目がX軸の3に、2bit目が6に対応するという大変にすばらしい関係になっているのがわかります。先ほどの簡単な変換で求めた各軸ごとの空間番数さえわかれば、上のようにビット値をミックスさせる事で所属する空間をビシッと吐き出す事ができるわけです。これを実現するために、ビットを1つ飛びに変換する関数を作ってみます。統一的に扱えるように、最大16bitの数値で考えてみます。1つ飛びにする方法は単純です。具体的な変換の流れを見てみましょう:上が入力情報で右16bitが有効です。これを一番下の状態にする過程をここでは示しています。最初の数nを左に8bitシフトして、元の数字とORします。すると、真ん中の状態になります。「*」は任意のビット値ですが、ここは必要無いのでマスクをかませると、一番下のように8ビット飛びに分かれます。これと全く同じような作業を繰り返します。今度は下の結果を4ビットだけ左にずらし、マスクをかけると4bit飛びになります。2bitシフトしてマスク、最後に1bitずらしてマスクすると、1bit飛びの32ビット数値ができあがります。(BitSeparate32(y)<<1));}この関数にx=3、y=6を渡すと、45がちゃんとお目見えします(^-^)。これで点の座標からその点が所属する空間を一発で出せるようになりました。オブジェクトの所属空間番号を算出する点の所属空間がわかって喜んでいてはいけません。私たちが空間に入れたいのは点ではなくてボリュームのあるオブジェクト、つまり縦横の大きさがある境界図形です。衝突をざっくり判定するのに適している境界図形は「境界円」か「AABB(軸並行境界ボックス)」です。以下で説明する所属空間判定アルゴリズムもこれらの境界図形を対象としています。登録時に境界図形のAABBの左上と右下点の所属空間番号を算出します。使えば瞬時にわかります:上の例だと左上は19番、右下は31番に含まれています。ここからが面白いところで、色々と試行錯誤し、またJagoon様からのご指摘によって修正されたうれしい法則です。右下の空間番号31と左上空間番号19の排他的論理和を取ると12となります。この12を2進数で表現するとこうなります:実は、境界図形の所属する分割レベルはこの排他的論理和の結果ビットが0じゃない最上位の区切りに表現されます。上の例だと青色で示した区切りが[11]となっています。所属空間は、上の例のように一番下の区切りを一つ上のレベル(ここでは子になります)、そこから親、ルートと空間レベルを上げていきます。[11]のビットはこの法則に従うと「親空間に所属」と判断されます。排他的論理和の結果から空間レベルがわかったら、次は右下の空間番号31(もしくは19)に注目します。前の説明になってしまいましたが、モートン空間番号は所属する親や子の空間番号を全部含んでいるのでした。31番の親は5bit目と6bit目(一番左)の「01」、すなわち1番です。ここから、この境界図形は「親空間の1番に所属する」と結論付けられます。これをプログラムで表現するのは簡単で、31番を右に4つシフトさせれば良いだけです。「4右シフト」をどう導くかは次の対応をご覧下さい:排他的論理和の結果を右から2つずつ見て行きます。0ならば捨て、0じゃ無ければそのシフト数を採用します。これをルート空間まで繰り返し、最後に採用されたシフト数を採択します。上の場合だと、3,4bit目が有効なので4右シフトとなります。これは空間がもっと細かくても同じです。ここで求めたシフト数分だけ右下の番号を右シフトすれば所属番号がビシッと出ます。一応もう1問だけやっておきます。境界図形の左上を44番、右下を47番とします。先に答えを言いますと、この境界図形は子空間の11番に所属します。この2進数は「00|00|11」ですね。子空間所属である事がわかります。右下47を右に2だけシフトすると「10|11」。これは、11番ですよね。子空間の11番が導けたわけです。くどいのですがもう一問。境界図形の左上は15番、右下が60番とします。15^60=51(排他的論理和はどちらを左辺にしてもOK)。2進数表現は「11|00|11」。最上位の区切りを採用するというルールだったので、ここは一番左の11を採用します。これは「ルート空間所属」です。この段階でもう終了しても良いのですが、一応シフト数6で60番を右シフトすると、やっぱり0になります。ルート空間所属で決定です。これで計算手順はばっちりでしょう。線形4分木でアクセスを高速化ここまでの4分木は、いわゆる樹状でしたが、これは末端の空間にアクセスするには不便過ぎました。Tree)と言います。これでルートから辿らなくても要素番号さえ指定すればo(1)レベルでどの空間にでもアクセスできます。今境界図形の所属レベルとその空間番号はビシッと算出できています。線形4分木はルート空間から一本に並べていますので、通し番号になっています。その対応が下の図です:上は通し番号(要素番号)、下は空間レベルとそのレベル内の通し番号です。先ほど浴びるほどやったビット計算で出てくるのは下の番号と空間レベルLです。下の番号を上の要素番号にする法則は簡単です。ビット計算の結果空間レベルL=2(子空間)の11番に所属する事がわかったとしましょう。それに対応する要素番号は16です。上の要素番号で子空間の最初は5から始まっていますね。11+5=16で変換ができます。結局のところ、「レベルLの最初の要素番号は何か?」がわかればいいだけなんです。足し算した「5」という数は、当たり前ですがL=0(ルート空間)とL=1(親空間)の空間の数の合計です。L=3とかL=4になると足す数はいくつになるのか?これは、高校の時にきっと皆さん習っている「等比級数の和」を使うと求まります。証明はさて置き、足す数を求める一般式は以下の通りです:L=2を入れると確かに5になりますし、L=3だと21、L=4だと85である事がわかります。この足す数は固定的ですから、プログラムに埋め込んでもきっとかまいません。動くオブジェクトの空間切り替えをo(1)で行うここまでで1つのオブジェクトが所属する空間へo(1)レベルで登録できるようになりました。OBJECT_FOR_TREE構造体を見れば、所属した空間へもo(1)でアクセスできます。これができると、空間内を盛んに動いているオブジェクトの所属する空間番号の切り替えもo(1)でできるようになります。所属空間を切り替えるには、オブジェクトが所属していた空間から自分を切り離し、新しい空間のリストに自身をくっつけます。自分を切り離すというのはリストからはずれるということです。リストを構築するためには、OBJECT_FOR_TREE構造体自体が双方向リンクリスト構造になっている必要があります。次の構造体へのポインタ};空間から外れる時には、自分の前の構造体と次の構造体をくっつけます。空間へ登録する時はそのリンクリストにただ加わるだけです。これらの作業は通常o(1)です。空間を移り変わる代わりに切り離すだけにすると、これは消去作業になります。ここまでアルゴリズムを切り詰めると、4分木空間分割に対する登録・変更・消去がすべてo(1)レベルでできるわけです。いやはや、もうお腹いっぱいです。1回の木巡回で衝突判定を終わらせる線形4分木に登録した全オブジェクトは、上位の空間から下に向けて衝突判定されます。この時、ツリーを重複して辿らないように工夫する必要があります。ルート空間にあるオブジェクトは登録された全てのオブジェクトと衝突する可能性があるので、全ての空間を巡って衝突判定をします。この作業を終えた後、一つ下の親空間L=1にあるオブジェクトについて同様に下位のオブジェクトと衝突を検証しようと考えたとします。この段階で、膨大なツリーをもう1度辿る事になってしまいます。これでは先ほどまで一生懸命最適化した意味がまるでなくなってしまいます。木は1回だけ巡りたいんです。木を一度通り抜けるだけですべての有効な衝突を終了させるために、衝突オブジェクトリストを導入します。下の図をご覧下さい:これは4分木にオブジェクトが登録されている様子を表しています。A〜Jがオブジェクトで、天辺がルート空間です。下位空間で生成されていない空間は×印で示しました。衝突判定は�@のルート空間から始まります。どの空間でも、まずはその空間内のオブジェクト同士の衝突を行います。判定が終わったら「衝突オブジェクトリスト」に登録されている上位空間のオブジェクトとの衝突判定を行います。�@の場合、まだリストには1つもオブジェクトが登録されていませんのでこの処理はスキップされます。一つの空間での衝突判定が終了したら、空間に登録されているオブジェクト(A〜D)をリストに追加します。�@のルート空間での衝突処理がすべて終了したら、次は�Aの子空間に移動します。ここでも新しい空間に入った最初の処理である空間内のオブジェクトE,Fの衝突をチェックします。その後に衝突オブジェクトリストにある全オブジェクトとの衝突をチェックします。このチェック後は次の空間に移動する予定なのですが、�Aの場合は子空間を持ちません。この場合、スタックにオブジェクトE,Fを登録せずに親の空間に戻ります。順序から次は�Bのチェックとなります。�Bでもする事は同様です。自身の空間にはオブジェクトが1つ(G)なので、その衝突チェックは外されますが、衝突オブジェクトリストとの衝突判定は行います。小空間も持ちますので、Gをリストに追加し、�Cの空間に移動します。�Cでも同様ですが、この空間は子空間を持ちませんので、H,I,Jオブジェクトをリストに追加せずに上に戻ります。戻った�Bの空間でもう下るべき他の子空間はありません。そこで、リストに登録されているGを除きます。これは最後尾にありますので単純にpopするだけです。一般に戻った時にpopするオブジェクトの数は、その空間に登録されているオブジェクトの数と等しくなります。�@の空間にさらに戻ります。�@ももう辿るべき子空間がありませんので、リストから自身の持つA〜Dをpopします。popがオブジェクト登録数4とやはり一緒になる点に注目して下さい。ルート空間で辿る子空間がもう無いとなった時点で、ここまでの再帰的な処理がすべて終了します。気が付けば木を1回辿っただけで衝突処理は適切に終了しており、且つ衝突オブジェクトリストも空っぽになります。再帰関数を使わない工夫この作業、再帰関数を使いたくてたまらなくなるのですが、ちょっと待ってください。再帰関数は関数呼び出しのオーバーヘッドがかかります。インライン展開もされません。オブジェクトがかなり多くて、これによるパフォーマンス低下が気になってしまう場合は、1つの関数内だけで木を巡る事を検討した方が良いかもしれません。false;}}再帰関数を用いない実装は、どうしても用いた場合よりも乱雑になりますが、呼び出しオーバーヘッドが無くなるので一般的には再帰関数を使った時よりも高速になります。上の実装では衝突チェックをこの関数内で行っていますが、別にこうしなくても構いません。この部分を分離してもよし、衝突予定オブジェクトリストを作成してこの関数を抜けた後に一気に衝突チェックをしても良しです。まとめ最適化をする前はn個ある全てのオブジェクトを登録するだけでo(n*(s/2+logs))レベル(nはオブジェクトの数、sは全空間の数)もの手数がかかっていた4分木空間分割は、この章で紹介した最適化アルゴリズムを適用する事で登録作業をo(n*1)レベルまで下げる事ができました。ゲームループでオブジェクトが動く場合には、毎回オブジェクトの更新と空間の移動の再登録が必要になりますが、モートン順序で空間に番号を振り、境界図形を工夫する事でこれもo(n*1)レベルで実現できます。衝突判定もリストをうまく使う事でで木を1回辿るだけで重複無くすべて終了するようにできました。プログラムの組み方にもよりますが、少なくともこのアルゴリズムで4分木空間分割は実用に耐えるレベルになるはずです。この章を編纂してつくづく思ったのが、たかが4分木、されど4分木という事でした。ここで紹介した方法がすべてではありませんし、改良の余地はまだあるかもしれませんが、さすがに脳が疲れまして、4分木についてこれ以上突っ込むつもりはありません(^-^;。空間分割についてさらに細かな情報が欲しい方は是非「ゲームプログラミングのためのリアルタイム衝突判定(ボーンデジタル)」及びこの書籍で紹介されている学術論文等をご覧下さい。謝辞アルゴリズムの修正に関してJagoon様から大変的確なアドバイスを頂きました。この場を借りてお礼申し上げます。