Wie kann ich diese Processing.org Skizze effizienter?

Question

Ich habe eine einfache Skizze (in Verarbeitung ), im Grunde eine Reihe von Punkten wandert herum, wenn sie kommen in Kontakt miteinander sie (jeder hat einen Stärkewert, jedesmal, wenn sie gewinnen erhöht, wenn es der Sieger gleich ist, wird zufällig ausgewählt) kämpfen

Es funktioniert gut mit etwa 5000 12-Pixel „Zombies“ (es gibt eine leichte Abschwächung für eine halbe Sekunde, während die Zombies zunächst miteinander kollidieren), das Problem ist, wenn die Zombies kleiner gemacht werden, sie nicht kollidieren miteinander, wie schnell, und die Verlangsamung kann viel länger dauern ..

Der Code ist wirklich einfach - im Grunde jeder Zombie ist eine Klasse, die ein X hat / Y-Koordinate. Jeder Rahmen alle Zombies ein Pixel stupste, zufällig lurching Grad (oder nicht) drehen. Ich denke, die größte Ursache der Langsamkeit ist die Kollisionserkennung - jeder Zombie jedes andere prüft (so Zombie 1 prüft 2-5000, Zombie 2 prüft 1,3-5000 etc ..)

Ich möchte alles einfach halten, und „plain Processing“ (keine externen Bibliotheken, die effizienten und leicht sein könnte, aber ich finde es nicht für das Lernen sehr nützlich)

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);
  }
}

Answer 1

Wie 1800 INFORMATION sagt, irgendwie die Anzahl der Vergleiche reduzieren müssen.

Splitting der Spielfläche in Zonen ist eine gute Idee. Ich könnte mir vorstellen, die Zeit, die aktuelle Position gegen Zonengrenzen zu vergleichen und Hinzufügen / Entfernen von Zombies aus den entsprechenden Sammlungen ist es wert. Unter der Annahme, sie in der Regel in geraden Linien gehen, sollten sie nicht Zonen häufig zu wechselnden werden.

Wir haben das Problem, obwohl die möglichen Kollisionen zwischen den Zonen. Huckepack auf der Idee, können Sie den Bildschirm in vier Zonen dann 9 Zonen wieder teilen. Denken Sie ein Tic-Tac-Toe-Brett auf einem Kreuz überlagert. Dies ist eine schlechte Zeichnung, aber:

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

Auf diese Weise jeden Zombie ist in zwei Zonen auf einmal und jede Grenze in einem Schema wird von einer anderen Zone bedeckt. Sie müssten alle die gleichen Zombies wieder nicht einmal überprüfen, weil wir entweder tot sein würde oder sie würden. So ist die einzige Doppelverarbeitung ist eine einzige others[i].dead überprüfen.

---

Eine andere Sache, die ich schnell sehen kann, ist man noch Schleife durch den Rest der Elemente, obwohl Sie sind tot:

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

Es ist vielleicht nicht viel Verarbeitung speichern, aber es kann einige Anweisungen, wenn Sie sicher schneiden:

  if (dead) return;

statt.

---

Auch als eine Randnotiz, tun Sie den Durchmesser oder den Radius gegen den Abstand zu checken möchten?

Answer 2

Sie erhielten sich O(n^2) Komplexität, und dass Ihr Algorithmus tötet. Es ist richtig, dass jeder Zombie, die mit allen anderen bewegt hat zu überprüfen, ob sie zusammengestoßen, die Sie quadratische Komplexität bringt.

Eine Richtung könnte sein, eine Matrix, die den Bildschirm zu erstellen, und statt über alle anderen Zombies Laufen, einfach aktualisiert die Position des aktuellen Zombies auf der Matrix, und es überprüfen, ob ein anderer Zombie bereits die gleiche Zelle einnimmt.

Answer 3

Ihr grundlegender Kollisionserkennungsalgorithmus hat O (n ^ 2) Komplexität.

Sie müssen einig Ansatz, der die Anzahl der Vergleiche reduzieren.

Ein Ansatz bereits erwähnt, ist das Spielfeld in Zonen / Bereiche zu unterteilen, und nur für Kollisionsprüfung, wenn ein zombie in der gleichen Zone / Region ist. Dies ist ein Versuch die Entitäten topologisch (nach Entfernung) zu sortieren. Was Sie wollen, ist diese zu trennen Zombies einfach nicht durch die Geographie, sondern sie zu sortieren, so dass sie nur verglichen werden, wenn sie sind ‚schließen‘ zueinander. Und Sie wollen leere Regionen ignorieren.

eine Baumstruktur auf Ihre Regionen in Betracht. Wenn eine Region mehr als eine bestimmte Anzahl hat N von Zombies, könnten Sie die Region kleinere aufgeteilt, bis der Bereich Radius Ihre Kollision Abstand annähert. Verwenden Sie eine Karte Region nachzuschlagen, und überprüfen Sie alle Zombies in einer bestimmten Region (und jede ‚nahe genug‘ Region).

Sie wollen wahrscheinlich N auf <= log (n) ...

Answer 4

Vielleicht sollten Sie das Spielfeld in Zonen aufgeteilt nach oben und nur für Kollisionen zwischen Zombies überprüfen, die in der gleichen Zone sind. Sie müssen die Anzahl der Vergleiche reduzieren.

Answer 5

Es erinnert mich an diesem Thread: Keine Ahnung, was das Problem sein könnte !! . Und Kollisionserkennung Hilfe , wo ich zur Wikipedia Kollisionserkennung Artikel verweisen.
Quadtrees oft für 2D-Partitionierung verwendet werden, scheint .