パフォーマンスの問題：単純な群衆シミュレーションのリストを更新する

Question

私は小さなゲームのための単純な群衆シミュレーションを行っています。

私の必要性はまともですが、パフォーマンスは良くありません。

基本的に私はウェイポイントに移動中に広がる必要があるオブジェクト（兵士）の "たくさんの"を持っています。

ここに私のコードのシンプルなバージョン書かアイブ氏：だからbasicly

List<Soldier> avoidList = new List<Soldier>(); 

foreach (Soldier s in gameWorld) 
{ 
    if (this == s) 
     continue; 

    if (Distance(s, this) <= 5) 
    { 
     avoidList.Add(s); 
    } 
} 

CalculateNewDirection(avoidList); 

を、各兵士は、シーン内の他のすべての兵士の距離を確認し、あまりにも接近している兵士に基づいて方向を算出します。

Like this picture.

は今のx^2つのオブジェクトを通して実行しているイム。

もし私が100個のオブジェクトを持っているならば、私は100^2 = 10.000個のオブジェクトを実行し、それぞれのオブジェクトavoidListを更新するだけです。

私は最大500個のオブジェクトをクランクすると、250.000個のオブジェクトを実行します。

Theresはこれを行うためには異なるスマートな方法でなければなりません！誰かが私を啓発することができます

希望:)私の頭の上オフ

Answer 1

は、距離をcalulatingときに不必要な平方根をやっているように思えます。代わりに、自乗距離を確認し、自乗された定数と照合することができます。

また、避けるべき兵士を見つけたら、もう一方の兵士も最初の兵士を避けるように改良が施されています。したがって、複数の回避リストを追跡する場合は、各ペアのチェックを1回だけ行う必要があります。

これは、あまりにも近いペアだけを保存することで実行できます。擬似コード

for (int i = 0; i < numSoldiers - 1; ++i) { 
    for (int j = i + 1; j < numSoldiers; ++j) { 
     if (Distance(soldier[i], soldier[j]) < 5) { 
      closePairs.Add(new Pair(i, j)); 
     } 
    } 
} 

// Calculate directions based on the pairs found. 

これらは基本的な最適化です。それよりも深く進む必要がある場合は、位置に基づいて兵士を分類する必要があります。あなたが各5平方メートルにある兵士を追跡すると、2つ以上の四角い兵士は、与えられた兵士に影響を及ぼす可能性があります。

X軸とY軸の兵士を最初に並べ替えると、同じ軸上の次の男との距離が半径よりも大きい場合は、距離を確認する必要はないことがわかっているので、同様の代替手段が得られます。

これは、パフォーマンスが向上しますが、データと、兵士の通常の疎感に依存します。