XNAどのように良い衝突アルゴリズムを書くには？

Question

私は現在XNAの新しいゲームに取り組んでおり、スプライト/アニメーション、入力、ゲームオブジェクトなどのような基本的なものを設定しています。

一方、私は良い方法を検出しようとしていますすべてのゲームオブジェクトの衝突を検出することができますが、ゲームを非常に少数のオブジェクトに制限する高速アルゴリズムを考えることはできません。 は、これは私が学校の割り当て

public static void UpdateCollisions() 
{ 
    //Empty the list 
    AllCollisions.Clear(); 

    //Find all intersections between collision rectangles in the game 
    for (int a = 0; a < AllGameObjectsWithCollision.Count; a++) 
    { 
     GameObject obja = AllGameObjectsWithCollision[a]; 
     for (int b = a; b < AllGameObjectsWithCollision.Count; b++) 
     { 
      GameObject objb = AllGameObjectsWithCollision[b]; 

      if (obja.Mask != null & objb.Mask!= null && obja != objb && !Exclude(new Collision(obja, objb))) 
      { 
       if (obja.Mask.CollisionRectangle.Intersects(objb.Mask.CollisionRectangle)) 
        AllCollisions.Add(new Collision(obja, objb)); 
      } 
     } 
    } 
} 

だった私の最後のプロジェクトでやったことあるので、それはすべてのオブジェクト間のすべての衝突をチェックしますが、除外は、私は不要見つけ衝突を加えます。

その後、私はゲームオブジェクトの量が増加したときにこれが遅くかなり迅速に私のゲームの実行を作っこの

//Look for collisions for this entity and if a collision is found, call the OnCollision method in this entity 
     var entityCol = FindCollision(entity); 

     if (entityCol != null) 
     { 
      if (entityCol.Other == entity) 
       entityCol = new Collision(entity, entityCol.Obj1); 
      entity.OnCollision(entityCol); 
     } 

Collision FindCollision(GameObject obj) 
{ 
    Collision collision = AllCollisions.Find(delegate (Collision col) { return (GameObject)col.Obj1 == obj || (GameObject)col.Other == obj; }); 
    return collision; 
} 

のように呼ばれる仮想メソッドOnCollisionを使用し、彼らは衝突している私のオブジェクトに通知します。

私の頭の中で最初にポップアップするのは、新しいスレッドを作成することです。これはいい考えです。&どうやったらいいですか？

私はアルゴリズムを少し勉強しましたので、私は基本的なコンセプトと、どのように動作するのかを知っています。

私はC＃とプログラミング全体でかなり新しいので、説明せずに進んではいけません。私はすぐに学ぶ。

Answer 1

あなたがすることができるかなりの数のものがあります。

ネストされたforループはオブジェクトの数が増加するにつれて、むしろ早く成長する二次の実行時間を、生産が。代わりに、いくつかのアクセラレーションデータ構造（グリッド、kdツリー、BVHなど）を使用できます。これらを使用すると、交叉チェックを、交差する可能性のあるエンティティのみに減らすことができます。

エンティティを注文できる場合は、エンティティのペアをチェックするだけで、衝突のチェックを半分に減らすことができます。エンティティのペアは、最初のものよりも大きい（順序に関して）2番目です。私。すでにa-bをチェックしている場合、b-aをチェックする必要はありません。

この部分は潜在的に遅くなることができます。

!Exclude(new Collision(obja, objb))) 

Collisionがクラスであれば、これは常にヒープ上に新しいメモリを割り当て、最終的にそれをリサイクルしています。したがってCollisionをstruct（それがまだない場合）にするか、objaとobjbを直接Exclude()に渡す方が良いかもしれません。これは、Collisionの他の用途にも当てはまります。 Exclude()の実装は表示されていませんが、単純な線形検索の場合はこれを改善することができます（たとえば、すべてのオブジェクトのエントリを含むリストを直線的に検索すると、ループの3次実行時間）。

FindCollision()の実装は、（AllCollisionsが何であるかによる）線形検索であり、非常に遅くなる可能性があります。とにかく衝突を保存しているのはなぜですか？あなたが衝突を見つけたらただちにOnCollision()に電話できませんでしたか？コリジョンが特定のエンティティに効率的に関連付けられているかどうかを確認したい場合は、別のデータ構造（ハッシュマップなど）が適しています。

最後に、パラレル化することは確かに実行可能なオプションです。しかし、これはいくらか関与しており、最初に基本に焦点を当てるよう助言します。正しく実行された場合、キューブの実行時間をn log nまたはnに減らすことができます。