How can I make this Process.org thumbnail more efficient?
I have a simple sketch (in Processing ), basically a bunch of dots wander around if they come in contact with each other they fight (each has a strength value, increases every time they win, if equal to the winner, randomly selected)
It works well with around 5000 12px "zombies" (there is a slight slowdown of half a second while the zombies collide with each other first), the problem is that the zombies are made smaller, they don't collide with each other as quickly as possible. and the deceleration can take much longer.
The code is really simple - basically every zombie is a class that has an X / Y coordinate. Each frame of all zombies is nudged one pixel, randomly rotating lurching
degrees (or not). I think the biggest reason for the slowness is collision detection - every zombie checks all the others (so zombie 1 checks 2-5000, zombie 2 checks 1.3-5000, etc.).
I would like to keep everything simple and "normal processing" (not using external libraries which might be more efficient and lightweight, 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);
}
}
source to share
As 1800 INFORMATION mentions, for some reason you need to reduce the number of comparisons.
Dividing the play area into zones is a good idea. I would suggest that the time it takes to compare the current location with the zone boundaries and add / remove zombies from their respective collections is worth it. Assuming they usually follow straight lines, they shouldn't change too often.
We have a problem, although collisions between zones are possible. To deal with this idea, you can divide the screen into 4 zones and then 9 zones. Think of a tick-tock-finger on the cross. This is a bad drawing, but:
| ! |
| ! |
----+--!-+----
| ! |
====|==x=|====
----+--!-+----
| ! |
| ! |
Thus, each zombie is in two zones at the same time, and each border in one scheme is covered by another zone. You wouldn't even have to check all the same zombies, because either we would be dead or we would be. So the only double processing is a single check others[i].dead
.
Another thing I can see quickly is that you are still scrolling through the rest of the elements, even if you are dead:
if (i == id || dead || others[i].dead){
continue;
}
This may not save a lot of processing, but it can of course shorten some of the instructions if you:
if (dead) return;
instead.
Also as a side note, would you like to check the diameter or radius from a distance?
source to share
You have complexity O(n^2)
and it kills your algorithm. It is correct that every zombie that moves has to check with everyone else if they collide, which results in quadratic complexity.
A matrix representing your screen can be created in one direction, and instead of repeating all the other zombies, just update the zombie's current location on the matrix and check there if another zombie is already occupying the same cell.
source to share
Your basic collision detection algorithm has O (n ^ 2) complexity .
You need an approach that will reduce the number of comparisons.
One approach that has already been mentioned is to divide the playing field into zones / areas and only check for collisions when the zombie is in the same zone / region. This is an attempt to sort features topologically (by distance). You want to separate these zombies not only by geography, but also to sort them so that they are compared only when they are "close" to each other. And you want to ignore empty areas.
Consider the tree structure in your regions. If the area has more than several N zombies, you can subdivide the area less until the area's radius approaches your collision distance. Use the map for the search area and check for all zombies in the area (and in any area "close enough").
You probably need N to be <= log (n) ...
It reminds me of this thread: I don't know what the problem is !! ... And help for collision detection where I quote an article on collision detection on Wikipedia.
Quadtrees seems to be often used to split in two.
source to share