¿Cómo puedo hacer que este bosquejo de Processing.org sea más eficiente?

Question

Tengo un boceto simple (en Procesando ), básicamente, un montón de puntos deambulan, si entran contactan entre sí pelean (cada uno tiene un valor de fuerza, aumenta cada vez que ganan, si es igual, el ganador es elegido al azar)

Funciona bien con alrededor de 5000 12 píxeles " zombies " (hay una ligera desaceleración durante medio segundo, mientras que los zombis inicialmente chocan entre sí), el problema es cuando los zombis se hacen más pequeños, no chocan entre sí tan rápido y la desaceleración puede durar mucho más. .

El código es realmente simple: básicamente cada zombie es una clase, que tiene una coordenada X / Y. Cada cuadro todos los zombies son empujados un píxel, girando aleatoriamente lurching grados (o no). Creo que la mayor causa de la lentitud es la detección de colisiones: cada zombie verifica a los demás (por lo que zombie 1 verifica 2-5000, zombie 2 verifica 1,3-5000, etc.)

Me gustaría mantener todo simple, y " Procesamiento simple " (no utiliza bibliotecas externas, que pueden ser más eficientes y fáciles, pero no me parecen muy útiles para aprender)

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

Como dice 1800 INFORMATION, de alguna manera necesita reducir el número de comparaciones.

Dividir el área de juego en zonas es una buena idea. Me imagino que vale la pena el tiempo que lleva comparar la ubicación actual con los límites de la zona y agregar / eliminar zombies de las colecciones apropiadas. Asumiendo que generalmente irán en línea recta, no deberían cambiar de zona con demasiada frecuencia.

Tenemos el problema de posibles colisiones entre zonas. Para aprovechar la idea, puede dividir la pantalla en 4 zonas y luego 9 zonas nuevamente. Piense en un tablero de tres en raya superpuesto en una cruz. Este es un mal dibujo, pero:

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

De esta manera, cada zombie está en dos zonas a la vez y cada borde en un esquema está cubierto por otra zona. Ni siquiera tendrías que volver a comprobar los mismos zombis porque estaríamos muertos o ellos lo harían. Entonces, el único doble procesamiento es una sola others[i].dead verificación.

---

Otra cosa que puedo ver rápidamente es que todavía recorres el resto de los elementos aunque estés muerto:

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

Puede que no ahorre mucho procesamiento, pero ciertamente puede cortar algunas instrucciones si usted:

  if (dead) return;

en su lugar.

---

También como nota al margen, ¿desea verificar el diámetro o el radio contra la distancia?

Answer 2

Tienes O(n^2) complejidad, y eso está matando tu algoritmo. Es correcto que cada zombi que se mueve tiene que verificar con todos los demás si chocaron, lo que te lleva a una complejidad cuadrática.

Una dirección podría ser crear una matriz que represente su pantalla, y en lugar de iterar sobre todos los demás zombies, simplemente actualice la ubicación actual del zombie en la matriz y verifique si otro zombie ya está ocupando esa misma celda.

Answer 3

Su algoritmo básico de detección de colisión tiene O (n ^ 2) complejidad.

Necesita un enfoque que reduzca el número de comparaciones.

Un enfoque ya mencionado es dividir el campo de juego en zonas / regiones, y solo verifica la colisión cuando un zombie está en la misma zona / región. Este es un intento para ordenar las entidades topológicamente (por distancia). Lo que quieres es separar estos zombies no solo por geografía, sino para clasificarlos de modo que solo se comparen cuando están 'cerca' el uno del otro. Y desea ignorar las regiones vacías.

Considere una estructura de árbol para sus regiones. Cuando una región tiene más de un número N de zombis, puede dividir la región más pequeña, hasta que el radio de la región se aproxime a su distancia de colisión. Use un mapa para buscar una región y verifique todos los zombis en una región determinada (y cualquier región 'lo suficientemente cercana').

Probablemente desee que N sea < = log (n) ...

Answer 4

Tal vez deberías dividir el campo de juego en zonas y solo buscar colisiones entre zombis que estén en la misma zona. Debe reducir la cantidad de comparaciones.

Answer 5

Me recuerda a este hilo: ¡¡No tengo idea de cuál podría ser el problema !! . Y ayuda para la detección de colisión donde señalo el artículo de Wikipedia sobre detección de colisión.
Quadtrees parece usarse a menudo para particiones 2D .