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

経緯 当たり判定を高速にするために、4分木（モートン順序）を使った空間分割アルゴリズムを勉強した際の備忘録です。 以下のサイトを参考に簡略的に解釈した内容をここに記します。 参考にさせていただいた記事 〇×つくろードットコム様 4分木空間分割を最適化する 自分なりに理解した順序を記します。 アルゴリズムの理解のためにまとめている為、プログラミング言語は一切出てきません。 4分木空間分割、及びモートン順序とは シューティングや広いマップのRPGなど、大量のオブジェクト同士があたり判定をする場合、 全オブジェクトとの判定は非常に効率が悪いと言えます。 そこで、プレイヤーキャラと当たるオブジェクトには局所性があることから、分割された空間内のオブジェクトと当たり判定を行う事で無駄な処理を減らすことが出来ます。 4分木空間分割とはゲーム空間を4^nに分割する事であり、モートン順序は分割された空間に対