大量の動的エンティティを持つ 2D ゲームに取り組んでいます。楽しみのために、彼らを兵士と呼びましょう。50000 人いるとしましょう (これは私がランダムに考えただけで、これよりも多い場合も少ない場合もあります :))。
これらの兵士はすべて、規則に従ってすべてのフレームを動かしています。各兵士の動きを更新するには、処理中の兵士に最も近い X 兵士が必要です。
オーバーヘッドをあまりかけずにこのような計算を容易にするために、それらを格納するのに最適な空間階層は何でしょうか? (すべてのエンティティはフレームごとに更新/移動されるため、動的エンティティをうまく処理する必要があります)
最も簡単な方法は、グリッドを使用することです。これにはいくつかの利点があります。
また、距離チェックごとに平方根を実行しないようにしてください。距離だけを比較しているので、距離の 2 乗を比較することもできます。
ブロード フェーズの衝突検出の場合、四分木 (2D であるため) またはグリッドのような空間インデックスで十分です。以前、Metanet Software のチュートリアルにリンクしたことがあります。グリッドベースのスキームを概説します。もちろん、ゲームでグリッドをそれほど広範囲に使用する必要さえありません。各アクターを非表示のグリッドに保存し、同じセルおよび隣接するセル内のオブジェクトと衝突させるだけです。
適切な空間階層を選択する際の要点は、テストが必要なオブジェクトのみをすばやく選択できるようにすることです。（その小さなサブセットを見つけたら、平方根はおそらくそれほど害を及ぼすことはありません）
また、高度に動的なオブジェクトの 2D 空間インデックス作成に最適な方法とは何かにも興味があります。
Quadtree / kd-tree は良さそうに見えますが、動的な挿入にはあまり適していません。KD ツリーは不均衡になる可能性があります。
ランダムな考えですが、エンティティが点である場合、二重挿入ソート構造 (X と Y による) を二分探索と組み合わせて試してみるのもいいかもしれません..?