(数学)四分木14-1.四分木探索(理論編)14-2.四分木探索(実装編)基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。y座標を2つずつ、つまり4つに分割した領域を子に持つ。大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかる。四分木を利用すれば2次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。四分木という場合、大きく分けて、2つの分け方がある。四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。常に点の位置で分割この場合、各節は領域で無く点を表す。振り方モートン符号という振り方を用いる。10こうすると何が良いかというと、「親のインデックス×4+1~4」で、子の4つのインデックスが表せ、親子関係を辿りやすい。階層L,領域番号Nにある領域のインデックスは、親の階層のインデックス最大値に、自身の領域番号+1を足したものとなる。1}{3}+N$となり、インデックスと領域番号の変換も単純な演算で可能となる。ikatakosメディアマネージャー文書の先頭へ。