ゲーム世界の空間分割

なぜ総当たりが破綻し、空間分割が要るのか

横にスクロール

ゲーム世界に n 個のオブジェクトがあり、互いの衝突を調べたいとします。素朴にやれば全ペアを比較するので比較回数は約 n*(n-1)/2、すなわち計算量は O(n^2) です。オブジェクトが 100 個なら約 5000 回で済みますが、10000 個になると約 5000 万回に膨れ、毎フレーム回すのは非現実的になります。可視性カリング（カメラに映らないものを描画から外す処理）も、全オブジェクトを毎フレーム視錐台と照合すれば同じく n に線形で効いてきます。

問題の本質は、遠く離れて絶対に相互作用しないペアまで律儀に比較している点です。画面の左端と右端のオブジェクトが衝突することはあり得ないのに、総当たりはそれを毎回確かめます。空間分割（spatial partitioning）は、オブジェクトを空間上の位置で索引化しておき、「あるオブジェクトの近くにいるのは誰か」を高速に引けるようにするデータ構造の総称です。これにより、衝突判定は「同じ・隣接する領域にいる相手」だけ、カリングは「視錐台と交差する領域」だけに絞り込め、平均的な計算量を近傍オブジェクト数に比例する規模まで落とせます。

一様グリッド：単純ゆえに速い

最も単純な構造が一様グリッド（uniform grid）です。世界を一定サイズ cellSize の正方形（3D なら立方体）セルに区切り、各オブジェクトをその座標が属するセルに登録します。セル座標は割り算だけで求まります。

セル座標の算出とバケットへの登録:

  cx = floor(x / cellSize)
  cy = floor(y / cellSize)
  grid[cx][cy].add(object)        # そのセルのリストに追加

衝突候補の列挙:
  自分のセルと周囲8セル（3x3）のオブジェクトだけを相手にする
  → オブジェクトの大きさが cellSize 以下なら、
     交差相手は必ずこの3x3の範囲に入る

セルの割り当てが定数時間、候補列挙も近傍セルの中身を見るだけなので、密度が均一なら極めて高速です。要はハッシュテーブルのバケットを2次元格子で作っているようなものです。弱点は cellSize の選び方に敏感なこと。セルを大きくしすぎると1セルに多数が入り総当たりに逆戻りし、小さくしすぎると大きなオブジェクトが多数のセルにまたがって登録コストが増えます。また世界が広大で疎らだと、空セルのための配列が巨大になりメモリを浪費します。密度が場所によって大きく偏る世界では、この均一な区切りが噛み合いません。

quadtree / octree：粗密に適応する木

密度が偏る世界には、適応的に分割する木構造が向きます。quadtree（四分木）は2D空間を再帰的に4つの象限へ分割する木で、3Dへ拡張して8分割にしたものがoctree（八分木）です。あるノードに登録されたオブジェクト数が容量閾値 K に達したら、その領域を4（または8）等分し、オブジェクトを子ノードへ振り分けます。オブジェクトが少ない広い空き領域は浅いまま、密集した領域だけが深く分割されるので、空間の粗密に木の深さが自動的に追従します。

検索は根から降りていきます。ある矩形範囲や視錐台と交差する子ノードだけを再帰的に訪ね、交差しない枝は丸ごと枝刈りします。空きが大半を占める広大なマップで少数の密集地を探すとき、無関係な領域を根の一段で切り捨てられるため、平均で木の高さ、おおむね O(log n) 相当の探索で近傍に到達できます。可視性カリングでは、視錐台に完全に含まれるノードは中身を無条件に可視、完全に外れるノードは丸ごと不可視、と判定できるため、階層カリングと相性が良いのが利点です。

quadtree ノードの構造（擬似コード）:

  node = {
    bounds,            # このノードが覆う矩形
    objects,           # まだ子に振り分けていないオブジェクト
    children[4] or nil # 分割済みなら4つの子、未分割なら nil
  }

  分割の判定: len(objects) が容量閾値以上 かつ 深さ上限未満なら subdivide()

弱点は、オブジェクトが複数ノードの境界をまたぐときの扱いです。境界に重なるものを親ノードに留める実装、関係する全ての葉に重複登録する実装（loose 化）などがあり、境界付近のオブジェクトが増えると木が肥大したり重複が増えたりします。木の再帰的なポインタ追跡はキャッシュ効率でも一様グリッドに劣りがちです。

spatial hash：無限の世界を有限テーブルへ

世界が事実上無限、あるいは非常に広くてグリッド配列を確保できない場合に効くのが空間ハッシュ（spatial hashing）です。考え方はグリッドと同じくセル座標 (cx, cy) を求めますが、それを2次元配列の添字にする代わりに、ハッシュ関数で1つの整数に畳み込み、ふつうのハッシュテーブルのキーにします。

セル座標を1つのハッシュ値へ畳み込む:

  cx = floor(x / cellSize)
  cy = floor(y / cellSize)
  h  = (cx * P1) XOR (cy * P2)     # P1, P2 は大きな素数
  bucket = table[h mod tableSize]  # このバケットへ登録

  候補列挙は grid と同じく周囲セルのハッシュ値を引く

この方式なら、確保するのは実際にオブジェクトが存在するセルの分だけで済み、空セルにメモリを払いません。座標の範囲に上限がない（プロシージャル生成で無限に広がるオープンワールドなど）場合でも、有限サイズのテーブルに写像できます。代償はハッシュ衝突で、異なるセルが同じバケットに落ちると、その分だけ無関係なオブジェクトが候補に混ざります。tableSize と素数の選び方、そして衝突時の再ハッシュや連鎖の設計が性能を左右します。負の座標で mod の符号がぶれない工夫も要ります。

動的オブジェクトの再挿入と更新コスト

ここまでは「登録済みの世界を検索する」話でしたが、ゲームではオブジェクトが毎フレーム動きます。あるオブジェクトが移動して別のセル（またはノード）へ移ったとき、索引はそれを反映しなければなりません。基本操作は再挿入（re-insertion）——古い所属セルから削除し、新しいセルへ追加する——です。

一様グリッドや空間ハッシュでは、これは「旧セルのリストから外し、新セルのリストへ入れる」だけで定数時間に近く、更新が軽いのが強みです。多くの実装は、移動後に新しいセル座標を計算し、前フレームのセル座標と異なるときだけ再登録します（同じセルに留まるなら何もしない）。quadtree/octree の場合はより重く、削除後にそのノードが空になれば子をまとめる（merge）、逆に移動先が閾値を超えれば分割する、といった木の再構成が絡みます。移動が激しいゲームで木を毎フレーム大きく作り替えると、検索が速くても更新で相殺されかねません。

移動が激しい環境では、毎フレーム索引を丸ごと作り直す（rebuild）方が、部分更新を積み重ねるより速いことすらあります。特に一様グリッドは全消去して全登録し直しても定数時間×n で済むため、ほぼ全オブジェクトが動く弾幕系などでは rebuild が単純かつ高速です。逆にほとんどが静止し一部だけ動く世界では、静的オブジェクトを別の索引に固定し、動的なものだけを軽い構造で管理する静動分離が効きます。

描画のBVHとは目的が違う

木構造による空間分割というと、レイトレーシングで使うBVH（境界ボリューム階層）を思い浮かべる人もいるでしょう。実際、グラフィックス（レンダリング・GPU） の分野では、光線と膨大な三角形の交差を高速化するために BVH や kd-tree が中心的に使われます。しかし本稿で扱ったのは衝突判定と可視性カリングという別用途です。両者は「空間を階層で索引化する」点で親戚ですが、最適化の対象が異なります。レイトレ用の構造は「1本の光線がどの三角形に当たるか」を最短で解くために、静的なシーンを前提に構築時間をかけてでも探索を最速化する設計に寄ります。対して衝突・カリング用の構造は、毎フレーム動くオブジェクトの再挿入コストと検索コストのバランスが主眼で、更新の軽さが構造選択を左右します。同じ木でも、静的シーンを深く最適化するのか、動的世界を軽く更新し続けるのかで設計判断が変わる——この使い分けを押さえておくと、どの構造をどの場面に持ち込むべきかを見誤りません。物理エンジンや可視判定は、ゲームのメインループ（OS（プロセス・メモリ） が管理するCPU時間の中で毎フレーム回る処理）の負荷を大きく左右するため、ここでの構造選択がフレームレートに直結します。

まとめ

空間分割は、ゲーム世界のオブジェクトを位置で索引化し、衝突判定のブロードフェーズと可視性カリングを近傍だけに絞ることで、総当たりの O(n^2) を平均的に近傍数へ比例する規模まで下げるためのデータ構造群です。一様グリッドは座標をセルに割るだけの単純さで密度が均一なら最速、quadtree/octree は空きの多い粗密の激しい世界に木の深さが適応し範囲探索を枝刈りでき、spatial hash はセル座標をハッシュで有限テーブルに畳み込むことで無限に広い世界すら扱えます。いずれも動的オブジェクトにはセル移動時の再挿入が必須で、更新の軽さと検索の速さのトレードオフが構造選択の軸になります。移動が激しければ全体rebuild、静止が多ければ静動分離といった運用も併せ、密度分布・世界の広さ・移動の激しさという三点で最適な索引を選ぶのが実務の勘所です。レイトレのBVHとは「空間を階層化する」発想を共有しつつも、更新コストを重視する衝突・カリング用途では設計判断が別物になる点も、あわせて押さえておきましょう。