1

私は簡単なスケッチを持っています(処理中)。基本的にはたくさんのドットがさまよっており、互いに接触すると戦います(それぞれに強度値があり、勝つたびに増加し、等しい場合は勝者がランダムに選択されます)

約 5000 の 12 ピクセルの「ゾンビ」でうまく機能します (ゾンビが最初に互いに衝突する間、0.5 秒間わずかな減速があります)。他のものと同じくらい速く、減速ははるかに長く続く可能性があります..

コードは非常に単純です。基本的に、各ゾンビは X/Y 座標を持つクラスです。lurching各フレームで、すべてのゾンビが 1 ピクセルずつ微調整され、角度がランダムに変化します (または変化しません)。速度低下の最大の原因は衝突検出だと思います - 各ゾンビは他のすべてをチェックします (つまり、ゾンビ 1 は 2-5000 をチェックし、ゾンビ 2 は 1,3-5000 をチェックするなど..)

すべてをシンプルに保ち、「プレーンな処理」を維持したいと考えています (外部ライブラリを使用していないため、より効率的で簡単かもしれませんが、学習にはあまり役に立ちません)。

int numZombies = 5000;

Zombie[] zombies = new Zombie[numZombies];

void setup(){
  size(512, 512);
  noStroke();
  for(int i = 0; i < numZombies; i++){
    zombies[i] = new Zombie(i, random(width), random(height), random(360), zombies);
  }
}

void draw(){
  background(0);

  for(int i = 0; i < numZombies; i++){
    zombies[i].move();
    zombies[i].display();
  }
}

class Zombie{
  int id; // the index of this zombie

  float x, y; // current location
  float angle; // angle of zombies movement
  float lurching = 10; // Amount angle can change
  float strength = 2;

  boolean dead = false; // true means zombie is dead

  float diameter = 12; // How big the zombie is
  float velocity = 1.0; // How fast zombie moves

  Zombie[] others; // Stores the other zombies

  Zombie(int inid, float xin, float yin, float inangle, Zombie[] oin){
    id = inid;
    x = xin;
    y = yin;
    angle = inangle;
    others = oin;
  }

  void move(){
    if(dead) return;

    float vx = velocity * sin(radians(180-angle));
    float vy = velocity * cos(radians(180-angle));

    x = x + vx;
    y = y + vy;

    if(x + vx < 0 || x + vx > width || y + vy < 0 || y + vy > height){
      // Collided with wall
      angle = angle + 180;
    }

    float adecide = random(3);

    if(adecide < 1){
      // Move left
      angle=angle - lurching;
    }
    else if(adecide > 1 && adecide < 2){
      // Don't move x
    }
    else if(adecide > 2){
      // Move right
      angle = angle + lurching;
    }

    checkFights();
  }

  void checkFights(){
    for (int i=0; i < numZombies; i++) {
      if (i == id || dead || others[i].dead){
        continue;
      }

      float dx = others[i].x - x;
      float dy = others[i].y - y;
      float distance = sqrt(dx*dx + dy*dy);

      if (distance < diameter){
        fight(i);
      }
    }
  }

  void fight(int oid){
    Zombie o = others[oid];

    //println("Zombie " + id + "(s: "+ strength +") fighting " + oid + "(s: "+ o.strength +")");

    if(strength < o.strength){
      kill();
      o.strength++;
    } 
    else if (strength == o.strength){
      if(random(1) > 0.5){
        kill();
        o.strength++;
      }
      else{
        o.kill();
        strength++;
      }
    }
  }

  void kill(){
    dead = true;
  }

  void display(){
    if(dead) return;
    ellipse(x, y, diameter, diameter);
  }
}
4

5 に答える 5

4

あなたは自分自身O(n^2)の複雑さを手に入れました、そしてそれはあなたのアルゴリズムを殺しています. 移動する各ゾンビが衝突したかどうかを他のすべてのゾンビとチェックする必要があることは正しいため、二次的な複雑さが生じます。

画面を表すマトリックスを作成し、他のすべてのゾンビを反復処理する代わりに、マトリックス上の現在のゾンビの位置を更新し、別のゾンビが既に同じセルを占有しているかどうかを確認するのが 1 つの方向かもしれません。

于 2009-01-07T08:44:48.850 に答える
1

1800情報が言うように、どういうわけかあなたは比較の数を減らす必要があります。

プレイエリアをゾーンに分割することをお勧めします。現在の場所をゾーンの境界と比較し、適切なコレクションからゾンビを追加/削除するのにかかる時間は、それだけの価値があると思います。それらが一般的に直線で進むと仮定すると、ゾーンを頻繁に変更するべきではありません。

ゾーン間の衝突の可能性については問題があります。アイデアに便乗するために、画面を4つのゾーンに分割し、次に9つのゾーンに分割することができます。十字架に重ねられた三目並べを考えてみてください。これは悪い絵ですが、:

    |  ! |
    |  ! |
----+--!-+----
    |  ! |
====|==x=|====
----+--!-+----
    |  ! |
    |  ! |

このように、各ゾンビは一度に2つのゾーンにあり、1つのスキームのすべての境界は別のゾーンでカバーされます。私たちが死んでしまうか、死んでしまうので、同じゾンビをすべてもう一度チェックする必要はありません。したがって、二重処理は1回のothers[i].deadチェックのみです。


私がすぐに見ることができるもう1つのことは、死んでいるにもかかわらず、残りの要素をループしていることです。

  if (i == id || dead || others[i].dead){
    continue;
  }

多くの処理を節約できないかもしれませんが、次の場合は確かにいくつかの命令を削減できます。

  if (dead) return;

代わりは。


また、補足として、距離に対して直径または半径を確認しますか?

于 2009-01-07T09:08:31.923 に答える
1

基本的な衝突検出アルゴリズムの複雑さはO(n^2)です。

比較の数を減らすアプローチが必要です。

すでに述べた 1 つのアプローチは、競技場をゾーン/リージョンに分割し、ゾンビが同じゾーン/リージョンにいる場合にのみ衝突をチェックすることです。これは、エンティティをトポロジ的に (距離で) 並べ替えようとする試みです。あなたが望むのは、これらのゾンビを単に地理的に分離するのではなく、互いに「近い」場合にのみ比較されるようにソートすることです。そして、空の領域を無視したいとします。

地域へのツリー構造を検討してください。リージョンに数Nを超えるゾンビがいる場合、リージョンの半径が衝突距離に近づくまで、リージョンを小さく分割できます。マップを使用して地域を検索し、特定の地域 (および「十分に近い」地域) 内のすべてのゾンビをチェックします。

おそらく、 Nを <= log(n) にしたいでしょう...

于 2009-01-15T22:59:54.743 に答える
0

競技場を複数のゾーンに分割し、同じゾーンにあるゾンビ間の衝突のみをチェックする必要があるかもしれません。比較の数を減らす必要があります。

于 2009-01-07T08:38:18.007 に答える
0

このスレッドを思い出します:何が問題なのかわかりません!! . ウィキペディアの衝突検出の記事を参照してください
Quadtreesは、2D パーティショニングによく使用されるようです。

于 2009-01-07T17:10:35.493 に答える