Performance optimization for p5.js sketch?

testnia

I have managed to get my processing sketch working pretty well. However, the sketch doesn't run at a constant a FPS. I'm new to javascript and am hoping that someone could run through my code to see if i can eek out any more optimization.

var flock;

function setup() {
    createCanvas(windowWidth, windowHeight);
    flock = new Flock();
    // Add an initial set of boids into the system
    for (var i = 0; i < 200; i++) {
        var b = new Boid(random(0,width), random(0,height));
        flock.addBoid(b);
    }
}

function draw() {
    background(51);
    flock.run();
}

function windowResized() {
    resizeCanvas(windowWidth, windowHeight);
}


function Flock() {
    // An array for all the boids
    this.boids = []; // Initialize the array
}

Flock.prototype.run = function () {
    for (var i = 0; i < this.boids.length; i++) {
        this.boids[i].run(this.boids);  // Passing the entire list of boids to each boid individually
    }
}

Flock.prototype.addBoid = function (b) {
    this.boids.push(b);
}

function Boid(x, y) {
    this.velocity = createVector(random(-0.6, 0.6), random(-0.6, 0.6));
    this.position = createVector(x, y);
}

Boid.prototype.run = function (boids) {
    this.connect(boids);
    this.update();
    this.borders();
}

Boid.prototype.update = function () {
    this.position.add(this.velocity);
}

Boid.prototype.render = function (alpha) {
    noStroke();
    fill(255,50+alpha);
    ellipse(this.position.x, this.position.y, 1.5+alpha*0.002, 1.5+alpha*0.002);
}


// Wraparound
Boid.prototype.borders = function () {
    if (this.position.x < 0) this.velocity.x *= -1;
    if (this.position.y < 0) this.velocity.y *= -1;
    if (this.position.x > width) this.velocity.x *= -1;
    if (this.position.y > height) this.velocity.y *= -1;
}

Boid.prototype.connect = function (boids) {

    var cD = 10000;
    var i = boids.length;
    var alpha;

    while (i--) {
        var d = p5.Vector.dist(this.position, boids[i].position);

        if (boids[i] == this) {
            continue;
        } 
        if (d < cD) {
            cD = d;
        }

        var alpha = 255 - map(cD, 0, 75, 0, 255);

        if (d < 51) {
            stroke(255, alpha);
            strokeWeight(0.08 + alpha * 0.002);
            line(this.position.x, this.position.y, boids[i].position.x, boids[i].position.y);
        }
    }

    if (cD < 51) {
        alpha = 255 - map(cD, 0, 75, 0, 255);
        cD = 10000;
    } else {
        alpha = 0;
    }

    this.render(alpha);
}

Any help will be greatly appreciated.

KevinWorkman

Step 1 is to do some profiling. Where is your program spending most of its time?

But just looking at your code, I notice that you're looping through the entire list of Boids and then for each Boid you're looping through the entire list again. With 200 Boids, that's 200*200 = 40000 comparisons every single frame!

If you're just comparing the magnitude of the distance, you might want to use distance squared instead.

GoToLoop

I've got this online sketch which features a more optimized double loop within draw(): :(|)
http://studio.SketchPad.cc/sp/pad/view/ro.989GaZC5t7EkE/latest

testnia

Thanks for the suggestions.

I have implemented a dist squared function which did help the performance a bit. Appreciate it.

The reason why I am iterating through the entire list is each individual point has to know the distance between it and every particle to figure out who is the closest. This gives rises to a algorithm solution of O(dn^2). I am trying to find a better algorithm for the above kinetic visualization.

I looked through the online sketch as well. However I don't believe it fits my case as the bouncing ball sketch does no account for distance between balls. Rather, it simply draws a line to the origin of any ball that fits its criteria, whereas the concept I am trying has to take into account the relative proximity between both particle.

Cheers.

KessonDalef

Maybe a look at Nature of Code by Shiffman can help, paragraph 6.14 (it if about interaction between a lot of particles in a particle system)

http://natureofcode.com/book/chapter-6-autonomous-agents/

KevinWorkman

The reason why I am iterating through the entire list is each individual point has to know the distance between it and every particle to figure out who is the closest.

This is true if you're storing them in a basic array without any other lookup information. But could you add to this to make the lookup faster?

You might use something like a quadtree or an R-tree to avoid checking every point.

More simply, you could change your program so it only rechecks the closest neighbor every X frames. Or manually split your world space into quadrants and only check against points in the same quadrant.

koogs

If I understand the connect code then it's drawing lines between a and B and then later between b and a. Which it doesn't need to do. It really only needs to check the boids after itself in the list (the connection to any boids earlier than itself was done when that boid was processed)

This changes that from O(n^2) to O(.5n(n-1)), slightly less than half as many

testnia

This is true if you're storing them in a basic array without any other lookup information. But could you add to this to make the lookup faster?

You might use something like a quadtree or an R-tree to avoid checking every point.

More simply, you could change your program so it only rechecks the closest neighbor every X frames. Or manually split your world space into quadrants and only check against points in the same quadrant.

Thanks for the tips, I looked into some of the algorithms mentioned including things like closest neighbour and kinetic closest pair, but the implementations are too abstract for me to grasp. I'll try to see if i can figure them out. Thanks.

If I understand the connect code then it's drawing lines between a and B and then later between b and a. Which it doesn't need to do. It really only needs to check the boids after itself in the list (the connection to any boids earlier than itself was done when that boid was processed)

I tried mitigating the number of lines drawn as per your suggestion but the performance overhead of checking the array seems to be slightly higher, about a 1-2fps drop as opposed to simply drawing them twice. It could be due to poor implementation. I've attached my method below, maybe someone could point out if there's something I could have done more efficiently.

            var j = boids.indexOf(this);
            //get index of current element i array.
            if (j < boids.length) {
                // if the index is lower than the overall length of the array (e.g. check traverse the array to elements infront of the current element, ignoring those behind)
                stroke(255, alpha);
                strokeWeight(0.06 + alpha * 0.004);
                line(this.position.x, this.position.y, boids[i].position.x, boids[i].position.y);
                j++;

            } else {
                continue;
            } */