私は何年もの間、ネット上で quadtree/quadtree ノードの実装を探していました。基本的なものはいくつかありますが、実際にゲームで使用できるものはありません。
私の目的は、衝突検出などを処理するためにオブジェクトをゲームに格納することです。四分木が使用するのに最適なデータ構造であると 100% 確信しているわけではありませんが、私が読んだ限りではそうです。私はすでに赤黒木をコーディングしましたが、パフォーマンスが自分のゲーム (Ankh のようなアドベンチャー 3 人称ゲーム) にとって十分であるかどうかはよくわかりません。
C++ で基本的だが完全な quadtree クラス (または octree) を作成するにはどうすればよいですか? 衝突に四分木をどのように使用しますか?
四分木は、効果的に平面上にあるものだけを格納する必要がある場合に使用されます。古典的なRTSのユニットのように、それらはすべて地面にあるか、その少し上にあります. 基本的に、各ノードには、ノードのスペースを均等に分散された四分の一に分割する 4 つの子へのリンクがあります。
オクトリーは同じことを行いますが、2 次元だけでなく 3 次元すべてであるため、8 つの子ノードがあり、空間を 8 つに分割します。これらは、ゲーム エンティティが 3 つの次元すべてに均等に分散されている場合に使用する必要があります。
赤黒木などの二分木を探している場合は、二分空間分割木 (BSP 木) と呼ばれるデータ構造か、KD 木と呼ばれるそのバージョンを使用します。これらは、平面を使用してスペースを半分に分割します。KD ツリーでは、平面は (XZ、XY、ZY 軸上で) 直交しているため、3D シーンでうまく機能する場合があります。BSP ツリーは、プレーンを使用して任意の方向にシーンを分割しますが、非常に便利であり、Doom まで使用されていました。
ゲーム空間を分割したので、すべてのゲーム エンティティを他のすべてのゲーム エンティティに対してテストして、それらが衝突するかどうかを確認する必要はありません。これはせいぜい O(n^2) アルゴリズムです。代わりに、データ構造にクエリを実行して、ゲーム空間のサブ領域内のゲーム エンティティを返し、それらのノードの相互の衝突検出のみを実行します。
これは、すべてのゲーム エンティティの衝突検出が (最悪の場合) n O(nlogn) 操作であることを意味します。
注意すべきいくつかの追加事項：
赤黒木は空間インデックスではありません。単一の序数キーでのみソートできます。四分木は (2 次元の場合) 空間インデックスであり、ポイントの高速検索と削除を可能にします。Octree は、3 次元に対して同じことを行います。
四分木を使用する理由は、x 座標と y 座標で分割し、x、y、z で八分木を作成して、衝突検出を簡単にするためです。
四分木: 要素が左上にない場合、右上、左下、または右下の要素と衝突しません。
これは非常に基本的なクラスなので、見つけた実装に何が欠けているのかわかりません。
私はそのようなクラスを書きません。適切なライセンスを持つプロジェクトから借りるだけです。
たとえば、Ogre3D などのレンダリング エンジンを使用することを強くお勧めします。私の知る限り、シーン管理用に Octrees をサポートしています。ただし、Octree ベースのクラスは必要に応じて拡張できます。以前は必要なものを自分でコーディングしていましたが、複雑なプロジェクトの場合、それは正しい方法ではありません。
現在、STANN は最高のオープン ソース実装です。
一般に、ツリーは、挿入されたアイテムが境界上にある可能性があるという点で問題があり、その状況に対処するすべての方法はかなり不十分です。
ほとんどの場合、オブジェクトを可動オブジェクトと静的オブジェクトに分類し、特定のフレームで移動したオブジェクトを静的オブジェクトと比較して確認したいと思うでしょう。
BSP ツリーは、静的ジオメトリ (オブジェクトを 2 つの部分に分割することによって処理される境界ケース) や、Sort や Sweep (Sweep および Prune とも呼ばれる) などの動的な試行に対して受け入れられているソリューションです。