私は膨大な量の動的エンティティを持つ2Dゲームに取り組んでいます。 楽しいことに、彼らを兵士と呼ぶことにしましょう。そして、彼らの50000人がいるとしましょう（私はランダムに考えました、それははるかに少なくなるかもしれません:)）。2Dゲーム：他のエンティティのx個の最も近いエンティティを見つけるための高速（est）方法 - 非常に動的なエンティティの膨大な量
すべてのこれらの兵士は、ルールに従ってフレームを動かしています - ボイド/フロッキング/ステアリングの動作を考えてください。 各兵士について、その動きを更新するには、私が処理しているものに最も近いX個の兵士が必要です。
このような計算を容易にするために、あまりにもオーバーヘッドがかからないように、それらを格納するのに最適な空間階層は何でしょうか？ （すべてのエンティティはフレームごとに更新/移動されるため、動的エンティティを非常にうまく処理する必要があります）
最も簡単な方法はグリッドを使用することです。これは、いくつかの利点があります：
また、すべての距離の確認には平置きをしないでください。距離を比較するだけなので、距離の二乗を比較することもできます。
+1を四角いアドバイスのために、常にそれを思い出させるのはいい – Gnoupi
+1広場のために、多くの人々は分かりませんどのような機能が本当に広大で、どれほどシンプルなのかを避けることです） –
広帯域の衝突検出では、クワッドツリーのようにspatial index（2Dのため）またはグリッドが行います。前にMetanet Software's tutorialにリンクしています。グリッドベースのスキームの概要を説明します。もちろん、ゲームではグリッドを広範囲に使用する必要はありません。隠れたグリッドに各アクタを格納して、それを同じ隣接セル内のオブジェクトと衝突させるだけです。
quadtreeはおそらく最高のものではありません。なぜなら、すべての移動オブジェクトに対して、それをツリーから削除してから挿入する必要があるからです。潜在的に高価な操作。または、フレームごとにツリーを再構築する必要があります。 – Toad
@reinier：四分木を更新する頻度を把握するためにいくつかのテストを行うと思います。その速度を遅くして、オブジェクトの半径を広げて衝突をテストすることができます。確かに、動きの速いオブジェクトは拡大された半径から飛び出すことがありますが、最初は問題のあるオブジェクトでした。 –
グリッドについても同じ議論が行われます; ^） – Toad
良い空間階層を選択することのポイントは、テストを必要とするオブジェクトだけを素早く選択できることです。 （その小さなサブセットを見つけたら、平方根はおそらくあまりそれを傷つけることはないでしょう）
また、2次元空間インデックスの高度な最適化方法についても興味があります動的オブジェクト。
Quadtree/kd-treeは素晴らしく見えますが、動的挿入ではそれほど優れていません。 KDツリーはアンバランスになる可能性があります。
エンティティがポイントである場合、バイナリ検索と組み合わせてダブル挿入ソート構造（XとY）を試してみてください。
もしそれが必要でないなら、なぜそれを使うのですか？ – Toad
最も便利な回答を選択して質問を閉じることを忘れないでください。 – Toad
ここでは、[いいアルゴリズム]（http://wapedia.mobi/en/Flocking_（behavior））を紹介しています。 –
[このブログ]（http://blogs.msdn.com/devdev/）には、[1つの解決策の良い記事があります]（http://blogs.msdn.com/devdev/archive/2007/06/07/k） -nearest-neighbor-spatial-search.aspx）（他の良いarticalsの数だけでなく） – BCS