この Processing.org スケッチをより効率的にするにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/419577

  •  03-07-2019
  •  | 
  •  

質問

簡単なスケッチがあります（ 処理）、基本的にドットの束が歩き回っており、互いに接触すると戦います（それぞれの強度値があり、勝つたびに増加します。値が等しい場合、勝者はランダムに選ばれます）

約 5000 個の 12 ピクセルの「ゾンビ」でうまく機能します (ゾンビが最初に互いに衝突する間、0.5 秒間わずかに速度が低下します)。問題は、ゾンビが小さくなると、ゾンビ同士が衝突しなくなることです。他の場合は急速ですが、減速ははるかに長く続く可能性があります。

コードは非常に単純です。基本的に各ゾンビは X/Y 座標を持つクラスです。各フレームですべてのゾンビが 1 ピクセルずつ微調整され、ランダムに回転します。 lurching 度（またはそうでない）。遅さの最大の原因は衝突検出だと思います。各ゾンビはお互いをチェックします (つまり、ゾンビ 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);
  }
}
役に立ちましたか？

解決

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

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

ゾーン間で衝突が発生する可能性があるという問題があります。アイデアに便乗するには、画面を4つのゾーンに分割し、次に9つのゾーンに分割します。十字架の上に三目並べボードがあると考えてください。これは悪い描画ですが、：

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

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

もうすぐわかるのは、死んでも残りの要素をループすることです：

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

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

  if (dead) return;

代わりに。

サイドノートとして、距離に対して直径または半径を確認しますか？

他のヒント

あなたは自分自身にO(n^2)複雑さを感じました、そしてそれはあなたのアルゴリズムを殺しているのです。移動する各ゾンビが衝突した場合、他のすべてのゾンビと確認しなければならないのは正しいことです。

1つの方法は、画面を表すマトリックスを作成し、他のすべてのゾンビを反復処理する代わりに、マトリックス上の現在のゾンビの位置を更新し、別のゾンビがその同じセルをすでに占有しているかどうかを確認することです

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

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

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

地域のツリー構造を検討してください。リージョンに N 以上のゾンビがいる場合、リージョン半径が衝突距離に近づくまで、リージョンを小さく分割できます。地図を使用して地域を検索し、特定の地域（および「十分に近い」地域）のすべてのゾンビを確認します。

N を<！> lt; = log（n）...

にしたいでしょう

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

このスレッドを思い出します: 何が問題なのか全く分かりません!!. 。そして 衝突検知のヘルプ ここでは、Wikipedia の衝突検出の記事を参照します。
クワッドツリー 2Dパーティショニングによく使われるようです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top