超高速2D当たり判定プログラムを作りたかった

経緯

当たり判定を高速にするために、4分木（モートン順序）を使った空間分割アルゴリズムを勉強した際の備忘録です。
以下のサイトを参考に簡略的に解釈した内容をここに記します。

参考にさせていただいた記事
〇×つくろードットコム様 4分木空間分割を最適化する

自分なりに理解した順序を記します。
アルゴリズムの理解のためにまとめている為、プログラミング言語は一切出てきません。

4分木空間分割、及びモートン順序とは

シューティングや広いマップのRPGなど、大量のオブジェクト同士があたり判定をする場合、
全オブジェクトとの判定は非常に効率が悪いと言えます。
そこで、プレイヤーキャラと当たるオブジェクトには局所性があることから、分割された空間内のオブジェクトと当たり判定を行う事で無駄な処理を減らすことが出来ます。
4分木空間分割とはゲーム空間を4^nに分割する事であり、モートン順序は分割された空間に対して一定のルールで識別番号を振る事です。

詳しくは次項で解説します。

モートン順序の仕組み

一つのゲーム空間（ルート空間）を4分割して"親空間"。さらに4分割して"子空間"(合計16空間)
さらに分割して"孫空間"(合計64空間)を作ります。

これらの空間に0から始まる番号を以下図のように振ります。

アルファベットのZのように見えますね。
この番号の振り方には意味があり、それによって空間管理がビット単位で可能になります。

では、ひとつの数字から詳しく見ていきましょう。
孫空間の30番をモートン順序で所属空間の空間番号を求めます。
以下の4図から30番はルート空間から{0/1/3/2}の場所に所属している事が分かります。

この所属は空間番号30から2進数変換する事で割り出すことが可能です。

さらに、便利なことに2進数にはX軸とY軸を示す役割も持っています。

以上の通り、モートン順序を使うことで点の座標からわずかo(1)の速度で孫空間の番号までを割り出し、所属空間を決めることが出来ます。
次の項から実際に管理する方法を順番に見ていきます。

1.点の座標から空間番号を求める

ここでは、マウスポイント等の点座標からモートン空間の所属番号を割り出す方法を説明します。
では下図のマウス座標(583.2, 325.8)からモートン番号を導いていきましょう。

今まで使用してきた孫空間の画像を当てはめて、一度目で確かめてみましょう。

＊ゲーム画面と照らし合わせている事を理解しやすくするため、多少ずらしております。
この画像から、マウスポインタはモートン番号30番のところに目視で確認できました。
では、これよりモートン番号30番をプログラム上で求める手順を説明します。
全体の概要としては、点の座標をXとYのモートン番号に置き換え、ビット演算で30番という数字を求めだします。
では、手順を説明します。

1-1.モートン座標を求める

モートン番号を求めるためには、点座標からモートン番号のXとYに変換します。

素晴らしいことに、マウス座標からXとYのモートン座標を求めることが出来ました。

1-2.モートン番号を求める

次に、求められたモートン座標(6, 3)からモートン番号に変換する手順を説明します。
モートン番号は元々1bit目と2bit目でXとYを示す性質がありました。
その発展的な考え方でモートン番号は求められます。

以上の考え方から、ビット演算をすることでモートン番号を求めていきます。
おおまかな手順は、
・X:6の二進数「0110」の1bit飛ばしX'=「00010100」を作り上げる
・Y:3の二進数「0011」の1bit飛ばしY'=「00000101」を作り上げる
・Y'を更に1bit左へシフトしたY''=「00001010」を作り上げる
・X'とY''のORをとる

よってモートン番号を求めることが出来ました。

1章のまとめ

まずは、点の座標が孫空間内のどのモートン番号に所属するか判断するアルゴリズムを理解しました。手順をおさらいしてみます。
・単位距離を求める
・単位距離と点座標からモートン座標を求める
・モートン座標からモートン番号に変換する

1章では点の座標でした。次の章では範囲を持つオブジェクトの所属空間を求めていきます。

2.オブジェクトの空間番号を求める。

前章でやった方法では1点の座標から孫空間内のモートン番号を導き出しました。
しかし、この方法では範囲を持つオブジェクトは孫空間内のマスを跨ぐ可能性があります。そうなった場合、子空間または親空間、ルート空間のどの空間に所属しているのか判別しなければなりません。2章では、範囲を持つオブジェクトの所属空間とそのモートン番号を求めていきます。
全体の概要としては、オブジェクトの左上と右下の座標のモートン番号を求めて、ビット演算を施す事で所属空間を求める。所属空間に応じたビット演算で、所属空間内におけるモートン番号を求める。
では、その手順を説明します。

2-1.オブジェクトの所属空間を求める

まず、オブジェクトが親空間、もしくは子空間、ルート空間いずれに所属するかを判別します。
その方法は、オブジェクト左上と右下の座標のモートン番号のXORを取ることで、所属空間がどこにあるか判別する事が出来ます。
以下の図に、今回所属空間を求めるオブジェクト例を載せた図を示します。

前章にて点の座標からモートン番号を求めることは学習済みなので、省略します。
次に、これらのモートン番号のXORを取り、所属空間を判別します。

XORを取ることで、所属空間を求めることが出来ました。

2-2.所属空間内のモートン番号を求める

前項から親空間にオブジェクトが所属していることが分かりました。
しかし、現状親空間のどのモートン番号にオブジェクトが存在するのか判別する方法がありません。
その手順を以下の図に示します。

これら一連の流れから、所属空間の番号までビット演算で割り出すことが出来ました。
これで、オブジェクトがどの空間に所属して、どのモートン番号にいるか分かるようになりました。

2章のまとめ

範囲を持つオブジェクトの所属空間と所属空間内におけるモートン番号を求めることが出来ました。
手順をおさらいします。
・オブジェクト左上と右下のモートン番号を求める
・両方のモートン番号のXORを取ります
・XORした値から所属空間を判別する
・所属空間に応じて右下のモートン番号を左シフトする
・左シフトで求められた値を所属空間のモートン番号に当てはめる

まとめ

オブジェクトの所属空間をモートン順序法を使って管理する事で、ルート空間から木構造的に他オブジェクトを識別して、それらのオブジェクトとあたり判定をする事が出来ました。
これによって無駄な処理を省いた当たり判定を実現できます。
これ以上の説明はプログラミングが関わってくるところなので省きますが、この記事で概念が出来たかもしれません。
Unity2Dのあたり判定の使い勝手が悪かったので、今後このアルゴリズムを使って2D当たり判定ライブラリを作っていこうと思います。