大量の当たり判定（４分木空間分割）

内容的にはとっても多いあたり判定を少なくする方法の続きとなる。色々な大きさの当たり判定がごちゃ混ぜになっている状況で、比較的早く総当り判定が出来る方法があったので、メモしておく。
その名を４分木空間分割という方法で詳しくはここで紹介されている。
けっこう込み入った内容なので理解するのに結構時間がかかるけど、実装できればかなりの処理を軽減できると思う。
ってわけでその第一歩である、ＸＹ座標をモートン順序へ変換する関数を作ってみる。といっても情報元のサイトに書かれていた内容そのままになる。

namespace SpatialPartitioning
{
    public static class MortonMath
    {
        /// <summary>
        /// ＸＹ座標をモートン順序に変換
        /// </summary>
        /// <param name="x">Ｘの値</param>
        /// <param name="y">Ｙの値</param>
        /// <returns></returns>
        public static uint XYtoMotton(ushort x, ushort y)
        {
            return (BitSeparate32(x) | (BitSeparate32(y) << 1));
        }

        /// <summary>
        /// ビットを１つおきにわける
        /// </summary>
        /// <param name="n">分けるビット列</param>
        /// <returns></returns>
        public static uint BitSeparate32(ushort n)
        {
            uint i = (uint)n;
            i = (i | (i << 8)) & 0x00ff00ff;
            i = (i | (i << 4)) & 0x0f0f0f0f;
            i = (i | (i << 2)) & 0x33333333;
            return (i | (i << 1)) & 0x55555555;
        }
    }
}

これで二次元座標上のものをモートン順序として表すことができる。モートン順序には４分木空間分割以外にも使い道がありそうなんで、覚えていて損はなさそうだ。
さて、実装するにあたって、割り当てることが出来る空間を決めなくてはいけない。理論上は無限に細かく割り当てることができるが、今回「ＸＹ座標→モートン順序」として用意した関数はuint型のものでＸＹそれぞれの１辺は０〜６５５３５で表されることになる。これはルート階層を０階層としたときに１５層までを表現可能としている。なので、最大階層を１５層そして実装するのがよいと思われる。
しかし、１５層ともなると空間の数が4294967295という大きな値になるので各空間に割り当てられるメモリのことを考えると、実際に使う場合にはもっと少ない状態にするのがよいと思える。
また、４分木空間分割をそのまま導入した場合には、欠点もある。第１層での作成された境界をまたぐようなオブジェクトはどんなに小さいオブジェクトであっても全てのオブジェクトと判定を行う必要があることだ。
この問題を解決する場合別な視点からの空間分割を取り入れる必要があるとおもえる。