Come posso rendere questo schizzo di Processing.org più efficiente?

Question

Ho uno schizzo semplice (in in lavorazione), in pratica un mucchio di puntini vagano in giro, se entrano in contatto tra loro combattono (ognuno ha un valore di forza, che aumenta ogni volta che vince, se è uguale il vincitore viene scelto casualmente)

Funziona bene con circa 5000 "zombi" da 12 pixel (c'è un leggero rallentamento per mezzo secondo, mentre gli zombie inizialmente si scontrano tra loro), il problema è che quando gli zombie vengono rimpiccioliti, non si scontrano tra loro altri altrettanto rapidi, e il rallentamento può durare molto più a lungo..

Il codice è davvero semplice: fondamentalmente ogni zombie è una classe che ha una coordinata X/Y.In ogni fotogramma tutti gli zombi vengono spostati di un pixel, ruotando in modo casuale lurching gradi (o meno).Penso che la principale causa di lentezza sia il rilevamento delle collisioni: ogni zombie controlla tutti gli altri (quindi zombie 1 controlla 2-5000, zombie 2 controlla 1,3-5000 ecc..)

Mi piacerebbe mantenere tutto semplice e "semplice elaborazione" (non utilizzare librerie esterne, che potrebbero essere più efficienti e facili, ma non lo trovo molto utile per l'apprendimento)

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

Come dice 1800 INFORMATION, in qualche modo è necessario ridurre il numero di confronti.

Dividere l'area di gioco in zone è una buona idea. Immagino che valga la pena il tempo necessario per confrontare la posizione corrente con i confini delle zone e aggiungere / rimuovere zombi dalle raccolte appropriate. Supponendo che generalmente andranno in linea retta, non dovrebbero cambiare zona troppo frequentemente.

Abbiamo il problema di possibili collisioni tra zone. Per dare una svolta all'idea, è possibile dividere lo schermo in 4 zone e poi di nuovo 9 zone. Pensa a una tavola di tic-tac-toe sovrapposta a una croce. Questo è un brutto disegno, ma:

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

In questo modo ogni zombi si trova in due zone contemporaneamente e ogni bordo in uno schema è coperto da un'altra zona. Non dovresti nemmeno controllare di nuovo tutti gli stessi zombi perché o saremmo morti o loro lo farebbero. Quindi l'unica doppia elaborazione è un singolo others[i].dead controllo.

---

Un'altra cosa che posso vedere rapidamente è che continui a scorrere il resto degli elementi anche se sei morto:

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

Potrebbe non risparmiare molta elaborazione, ma può sicuramente tagliare alcune istruzioni se:

  if (dead) return;

, invece.

---

Anche come nota a margine, vuoi controllare il diametro o il raggio rispetto alla distanza?

Answer 2

Hai preso te stesso O(n^2) complessità, e questo sta uccidendo il tuo algoritmo.È corretto che ogni zombie che si muove debba verificare con tutti gli altri se si è scontrato, il che ti porta alla complessità quadratica.

Una direzione potrebbe essere quella di creare una matrice che rappresenti il ​​tuo schermo e, invece di scorrere tutti gli altri zombi, aggiornare semplicemente la posizione corrente dello zombi sulla matrice e controllare lì se un altro zombi sta già occupando quella stessa cella.

Answer 3

Il tuo algoritmo di base per il rilevamento delle collisioni ha O (n ^ 2) complessità.

È necessario un approccio che riduca il numero di confronti.

Un approccio già menzionato è quello di dividere il campo di gioco in zone / regioni e controlla la collisione solo quando uno zombi si trova nella stessa zona / regione. Questo è un tentativo per ordinare le entità topologicamente (per distanza). Quello che vuoi è separarli gli zombi non semplicemente per geografia, ma per ordinarli in modo che vengano confrontati solo quando sono "vicini" l'uno all'altro. E vuoi ignorare le regioni vuote.

Prendi in considerazione una struttura ad albero per le tue regioni. Quando una regione ha più di un numero N di zombi, puoi dividere la regione più piccola, finché il raggio della regione non si avvicina alla distanza di collisione. Usa una mappa per cercare la regione e controlla tutti gli zombi in una determinata regione (e qualsiasi regione "abbastanza vicina").

Probabilmente vuoi che N sia < = log (n) ...

Answer 4

Forse dovresti dividere il campo di gioco in zone e controllare solo le collisioni tra gli zombi che si trovano nella stessa zona. Devi ridurre il numero di confronti.

Answer 5

Mi ricorda questo thread: Nessuna idea di quale potrebbe essere il problema !! . E aiuto per il rilevamento delle collisioni dove indico l'articolo sul rilevamento delle collisioni di Wikipedia.
Quadtrees sembra essere spesso usata per il partizionamento 2D .