Comment puis-je rendre ce sketch Processing.org plus efficace?

Question

J'ai un simple croquis (dans Processing ), qui consiste essentiellement en une série de points errants, s'ils entrent en contact les uns avec les autres ils se battent (chacun a une valeur de force, augmentée chaque fois qu'ils gagnent, si elle est égale, le gagnant est choisi au hasard)

Cela fonctionne bien avec environ 5000 " zombies " (il y a un léger ralentissement pendant une demi-seconde, alors que les zombies se heurtent initialement les uns aux autres), le problème est que lorsque les zombies sont réduits, ils ne se heurtent pas aussi rapidement et le ralentissement peut durer beaucoup plus longtemps. .

Le code est très simple: chaque zombie est une classe qui a une coordonnée X / Y. Chaque image, tous les zombies sont décalés d’un pixel, tournant au hasard lurching degrés (ou non). Je pense que la plus grande cause de lenteur est la détection de collision - chaque zombie vérifie les deux autres (donc zombie 1 vérifie 2 à 5 000, zombie 2 vérifie 1 à 5 000, etc.)

Je voudrais que tout reste simple et & "Traitement simple" & "; (ne pas utiliser de bibliothèques externes, ce qui pourrait être plus efficace et plus facile, mais je ne le trouve pas très utile pour apprendre)

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

Comme le dit 1800 INFORMATION, vous devez réduire le nombre de comparaisons.

Découper l’aire de jeu en zones est une bonne idée. J'imagine que le temps qu'il faut pour comparer l'emplacement actuel aux limites de zone et pour ajouter / supprimer des zombies des collections appropriées en vaut la peine. En supposant qu'ils marchent généralement en lignes droites, ils ne devraient pas changer de zone trop fréquemment.

Nous avons cependant le problème des collisions possibles entre les zones. Pour reprendre l’idée, vous pouvez diviser l’écran en 4 zones, puis à nouveau en 9 zones. Pensez à un tableau de tic-tac-toe superposé à une croix. C'est un mauvais dessin, mais:

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

Ainsi, chaque zombie est dans deux zones à la fois et chaque frontière d’un schéma est couverte par une autre zone. Vous n’auriez même pas besoin de vérifier tous les mêmes zombies car nous serions morts ou ils le seraient. Ainsi, le seul double traitement est une others[i].dead vérification

.

Une autre chose que je peux voir rapidement est que vous parcourez toujours le reste des éléments même si vous êtes mort:

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

Cela ne fera peut-être pas économiser beaucoup de traitement, mais cela peut certainement couper certaines instructions si vous:

  if (dead) return;

à la place.

Voulez-vous également vérifier le diamètre ou le rayon par rapport à la distance?

Answer 2

Vous avez vous-même O(n^2) la complexité, et cela tue votre algorithme. Il est exact que chaque zombie qui se déplace doit vérifier auprès de tous les autres s’ils se sont rencontrés, ce qui vous amène à une complexité quadratique.

Une direction pourrait être de créer une matrice représentant votre écran et, au lieu de parcourir tous les autres zombies, il suffit de mettre à jour l'emplacement actuel du zombie sur la matrice et de vérifier si un autre zombie occupe déjà la même cellule.

Answer 3

Votre algorithme de base de détection de collision présente une complexité O (n ^ 2) .

Vous avez besoin d'une approche qui réduira le nombre de comparaisons.

Une approche déjà mentionnée consiste à diviser le terrain de jeu en zones / régions et vérifiez uniquement si un zombie se trouve dans la même zone / région. C'est une tentative trier les entités topologiquement (par distance). Ce que vous voulez, c'est séparer ces zombies pas simplement par la géographie, mais pour les trier afin qu'ils ne soient comparés que lorsque ils sont 'proches' les uns des autres. Et vous voulez ignorer les régions vides.

Envisagez une arborescence de vos régions. Lorsqu'une région compte plus d'un N nombre de zombies, vous pouvez diviser la région en parties plus petites, jusqu'à ce que le rayon de la région atteigne votre distance de collision. Utilisez une carte pour rechercher une région et vérifiez tous les zombies d’une région donnée (et de toute région "suffisamment proche").

Vous voulez probablement que N soit < = log (n) ...

Answer 4

Peut-être devriez-vous diviser le terrain de jeu en zones et vérifier uniquement les collisions entre zombies qui se trouvent dans la même zone. Vous devez réduire le nombre de comparaisons.

Answer 5

Cela me rappelle ce fil de discussion: Aucune idée de ce qui pourrait être le problème !! . Et aide à la détection de collision , où je pointe vers l'article de Wikipédia sur la détection de collision.
Les quadtrees semblent être souvent utilisées pour le partitionnement en 2D .