私の 2D ゲームには、静的オブジェクトと動的オブジェクトがあります。複数のカメラが存在する可能性があります。私の問題:現在のカメラのビュー四角形と交差するオブジェクトを決定します。
現在、私はすべての既存のオブジェクトを反復処理し (動的か静的かは気にしません)、それらのカメラ ビュー rect で AABB チェックを実行します。これは、非常に動的なオブジェクトには受け入れられるようですが、数万のオブジェクトが存在する可能性がある静的オブジェクト (シーン全体に散在する静的レベルのジオメトリ) には受け入れられないようです。
私の問題を解決できる複数のデータ構造を調べました。
- 四分木
これは私が最初に検討したことでしたが、問題はシーンが固定サイズになることです。(静的オブジェクトには使用できますが、動的オブジェクトには使用できません)
- 動的 AABB ツリー
良さそうに見えますが、リバランスのオーバーヘッドが多くの動的オブジェクトにとって大きすぎるようです。
- 空間ハッシュ
ここでの主な問題は、カメラでズームアウトすると、ほとんど存在しない膨大な数の空間ハッシュ バケットをクエリする必要があり、パフォーマンスが低下することでした。
一般に、この問題を適切に解決するための私の基準は次のとおりです。
動的サイズ: ソリューションによってシーン サイズが制限されたり、サイズ変更のために大量の再計算が必要になったりしてはなりません。
良好なクエリ パフォーマンス (カメラの場合)
非常に動的なオブジェクトの適切なサポート: 位置が絶えず変化するオブジェクトを処理するために必要な計算は適切である必要があります。
ゲーム内で一度に正常に動作する動的オブジェクトの最大数は、おそらく 5000 です。すべてのオブジェクトがフレームごとに位置を変えることを考慮してください。フレームごとにオブジェクトの AABB をカメラと比較するよりも、頻繁な挿入と削除を考慮して、高速化できるデータ構造さえありますか?