Como posso fazer isso Processing.org esboço mais eficiente?

Question

Eu tenho um simples esboço (em Processamento ), basicamente um conjunto de pontos passear, se entrarem em contacto uns com os outros lutam (cada um tem um valor de resistência, o aumento cada vez que ganhar, se é igual o vencedor é escolhido aleatoriamente)

Ele funciona bem com cerca de 5000 12-pixels "zumbis" (há um ligeiro abrandamento para um meio segundo, enquanto os zumbis inicialmente colidem uns com os outros), o problema é quando os zumbis são feitos menores, eles não colidem uns com os outros tão rápido, ea desaceleração pode durar muito mais tempo ..

O código é realmente simples - basicamente cada zumbi é uma classe, que tem um X / Y coordenadas. Cada quadro todos os zumbis são empurrou um pixel, transformando aleatoriamente graus lurching (ou não). Acho que a maior causa da lentidão é a detecção de colisão - cada zumbi cheques a cada outro (de modo zombie 1 verifica 2-5000, zumbi 2 cheques 1,3-5000 etc ..)

Eu gostaria de manter tudo simples, e "Processamento simples" (sem uso de bibliotecas externas, o que pode ser mais eficiente e fácil, mas eu não encontrá-lo muito útil para a aprendizagem)

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 1800 INFORMATION diz, de alguma forma, você precisa reduzir o número de comparações.

Dividir a área de jogo em zonas é uma boa idéia. Eu imagino o tempo que leva para comparar localização atual contra limites da zona e zumbis adicionar / remover das coleções apropriadas vale a pena. Supondo que eles geralmente vão em linhas retas, eles não devem estar mudando zonas com muita freqüência.

Temos o problema embora de possíveis colisões entre zonas. Para pegar carona na idéia, você pode dividir a tela em 4 zonas, em seguida, 9 zonas de novo. Pense uma placa de tic-tac-toe sobrepostos em uma cruz. Este é um mau desenho, mas:

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

Desta maneira, cada zumbi é em duas zonas de uma vez e todas as fronteiras em um esquema é coberto por uma outra zona. Você nem sequer tem que verificar todos os mesmos zumbis novamente porque quer que estaria morto ou eles iriam. Assim, a única dupla de processamento é um único cheque others[i].dead.

---

Outra coisa que eu posso ver rapidamente é que você ainda percorrer o resto dos elementos mesmo que você está morto:

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

Pode não salvar um monte de processamento, mas certamente pode cortar algumas instruções se:

  if (dead) return;

em seu lugar.

---

Além disso, como uma nota lateral, você quer estar verificando o diâmetro ou o raio contra a distância?

Answer 2

Você tem-se O(n^2) complexidade, e que está matando seu algoritmo. É correto que cada zumbi que se move tem que verificar com todos os outros se eles colidiram que traz você a complexidade quadrática.

Uma direção pode ser a criação de uma matriz representando sua tela, e em vez de iteração sobre todos os outros zumbis, basta atualizar a localização do zumbi atual na matriz, e verificar lá se outro zombie já está ocupando essa mesma célula.

Answer 3

O algoritmo básico de detecção de colisão tem O (n ^ 2) complexidade.

Você precisa de alguma abordagem que irá reduzir o número de comparações.

Uma abordagem já mencionado, é dividir o campo de jogo em zonas / regiões, e só verificar por colisão quando um zombie está na mesma zona / região. Esta é uma tentativa para classificar as entidades topologicamente (por distância). O que você quer é separá-los zumbis não só pela geografia, mas para classificá-los de modo que eles são apenas em relação ao eles são 'close' um ao outro. E você quiser ignorar regiões vazias.

Considere uma estrutura de árvore para suas regiões. Quando uma região tem mais de um número N de zumbis, você poderia dividir a região menor, até o raio região se aproxima de sua distância de colisão. Use um mapa para procurar região, e verificar todos os zumbis em uma determinada região (e qualquer região 'perto o suficiente').

Você provavelmente quer N ser <= log (n) ...

Answer 4

Talvez você deve dividir o campo de jogo-se em zonas e só buscar por colisões entre zumbis que estão na mesma zona. Você precisa reduzir o número de comparações.

Answer 5

Isso me lembra este tópico: Sem idéia do que poderia ser o problema !! . E detecção de colisão ajuda onde eu aponto ao artigo detecção de colisão de Wikipedia.
gratuitos parecem ser muitas vezes usado para particionamento 2D .