私は、衝突検出の最適化に関する情報を探しています。衝突検出の最適化
点から点bに移動しているオブジェクト（円）があります。このオブジェクトは半径がrであり、フィールドにも多くの障害（円）があります。
すべての障害物Iは、円とカプセルの間の衝突をチェックするアルゴリズム（機能）を持っている、と私は現在、ために、この関数を呼び出す：多くの障害は非常に遠く離れている
for-each (o : obstacles)
if collide(o, Capsule(a,b,r))
return true;
return false;
を移動物体から離れており、衝突検出機能によるチェックから無視することができる。
私の質問は：
は、衝突検出機能付きすべての障害をチェック無視する解決策はありますか？何かのように最近隣の検索またはKD木？
EDIT：すべての障害物の半径は同じです。
最初の手順として、特定のフレーム/ボックス内に存在しないすべての障害を無視することができます。
など。 y座標（障害物の形状のy点の最下点）が大きい障害物はすべて、移動物体の半径に対するaとb +の同じ最大距離のy座標を無視することができます。より低いyボーダーとxボーダーに似ています。 1つのボックスの代わりに、さらに2つのボックスに同様のブランチをブランチできます。例えば、a-bの距離を2つの距離に分割し、（a、（b-a）/ 2）、/（b-a）/ 2、bのそれぞれについて上記の手順を実行する。
しかし、これらの値は、衝突手続きと比較してどのように効率的に比較できるかによって異なります。
グリッドを使用するだけで、各セルがそのセルに接触するすべての障害物を保持します。今度は、あなたのカプセルが触れる衝突のために細胞をチェックするだけです。 また、クォッドツリーを使用することもできますが、私の経験からはグリッドは通常十分であり、障害物が移動した場合でも簡単かつ迅速に更新可能であるという利点もあります。
モンスターカーブ、たとえばヒルベルトカーブをお勧めします。これはデータ構造のようなクアッドツリーまたはkdツリーであり、2dの複雑さを1dの問題に減らします。各フレームでは、開始からモンスターカーブを作成するだけで、4分木またはkdツリーに削除または挿入することができます。それはまた、いくつかのより良い2Dタイルプロパティを持っていますが、それはあなたのケースでは望ましくないかもしれません。
Martinさんの解答に対するコメント：
私の場合はシンプルで良いアプローチです。
私はBox(a.x-R, a.y-R, b.x+R, b.y+R)
R = ObjectRadius+ObstacleRadiusのような箱を作り、すべての障害物がこのボックス内ではありませんドロップします。
図では、黄色のドットの障害物のみがチェックされます。
コードで空間パーティショニングを実装できます。スペース/マップ全体をカバーする各ボックスに各オブジェクト/障害物を分割する。そうすることで、障害をセクションにグループ化します。したがって、小さなセクション内の衝突をチェックするだけで、膨大な量の衝突チェックを減らすことができます。あなたの障害物が動いていない場合は、各障害物に対してこの分割を1回だけ行う必要があります。移動中の場合は、毎回各障害物の[再グループ化]を更新する必要があります。
空間分割技法はかなり長い間行われてきましたが、実装に役立つリンクがあります。
あなたはどのように多くの障害を持っていますか？彼らはどれくらい密集していますか？衝突はしばしば起こるか、まれに起こるか？ –
約100の障害を考えると、彼らはまばらに分布しています。アルゴリズムは10msごとに呼び出します。 – deepmax
私のプログラムのバトルネックはこの問題だと思います。 – deepmax