How can I make this Processing.org sketch more efficient?

Question

I have a simple sketch (in Processing), basically a bunch of dots wander around, if they come into contact with each other they fight (each has a strength value, increased each time they win, if it's equal the winner is randomly chosen)

It works well with about 5000 12-pixel "zombies" (there's a slight slowdown for a half a second, while the zombies initially collide with each other), the problem is when the zombies are made smaller, they don't collide with each other as quick, and the slowdown can last much longer..

The code is really simple - basically each zombie is a class, which has an X/Y coordinate. Each frame all the zombies are nudged one pixel, randomly turning lurching degrees (or not). I think the biggest cause of slowness is the collision detection - each zombie checks every other one (so zombie 1 checks 2-5000, zombie 2 checks 1,3-5000 etc..)

I'd like to keep everything simple, and "plain Processing" (not using external libraries, which might be more efficient and easy, but I don't find it very useful for learning)

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

Maybe you should split the playing field up into zones and only check for collisions between zombies that are in the same zone. You need to reduce the number of comparisons.

Answer 2

You got yourself O(n^2) complexity, and that's killing your algorithm. It's correct that each zombie that moves has to check with all the others if they collided which brings you to quadratic complexity.

One direction might be to create a matrix representing your screen, and instead of iterating over all the other zombies, simply update the current zombie's location on the matrix, and check there if another zombie is already occupying that same cell.

Answer 3

Like 1800 INFORMATION says, somehow you need to reduce the number of comparisons.

Splitting the playing area into zones is a good idea. I would imagine the time it takes to compare current location against zone boundaries and add/remove zombies from the appropriate collections is worth it. Assuming they generally will go in straight lines, they shouldn't be changing zones too frequently.

We have the problem though of possible collisions between zones. To piggyback on the idea, you could divide the screen into 4 zones then 9 zones again. Think a tic-tac-toe board overlaid on a cross. This is a bad drawing, but:

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

This way each zombie is in two zones at once and every border in one scheme is covered by another zone. You wouldn't even have to check all the same zombies again because either we'd be dead or they would. So the only double-processing is a single others[i].dead check.

---

Another thing I can see quickly is you still loop through the rest of the elements even though you're dead:

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

It might not save a lot of processing, but it can certainly cut some instructions if you:

  if (dead) return;

instead.

---

Also as a side note, do you want to be checking the diameter or the radius against the distance?

Answer 4

It reminds me of this thread: No idea what could be the problem!!. And collision detection help where I point to Wikipedia's Collision detection article.
Quadtrees seem to be often used for 2D partitioning.

Answer 5

Your basic collision detection algorithm has O(n^2) complexity.

You need some approach which will reduce the number of comparisons.

One approach already mentioned, is to divide the playing field into zones/regions, and only check for collision when a zombie is in the same zone/region. This is an attempt to sort the entities topologically (by distance). What you want is to separate these zombies not simply by geography, but to sort them so that they are only compared when they are 'close' to one another. And you want to ignore empty regions.

Consider a tree structure to your regions. When a region has more than some number N of zombies, you could split the region smaller, until the region radius approaches your collision distance. Use a map to lookup region, and check all zombies in a given region (and any 'close enough' region).

You probably want N to be <= log(n)...