making particle system more efficient (in particular when they are deleted)

secondsky

Hi all, i'm trying to do a particle system where basically i have a matrix of drops that is gonna fall down. Kind o the simulation of a 3d water courtain.

As in the Shiffman examples, i'm using a OOP approach, where each particle is an object in an arraylist and when they go too fare are deleted to free memory.

The only difference is that the particle system is executed in a parallel thread and the main one just get a copy of the particles to represent them, when is needed.

What i don't understand, is why the sketch slow down so much when the drops approach the distance where they are deleted. After all, the check happen to every loop anyway. Is there some technique to make this more efficient?

import peasy.*;

PeasyCam cam;

ParticleSystem ps;

void setup() {

  size(600, 600, P3D);

  cam = new PeasyCam(this, 15, 30, 15, 100);
  cam.setMinimumDistance(50);
  cam.setMaximumDistance(500);
  ps = new ParticleSystem();
}

void draw() {

  background(255);
  noFill();
  strokeWeight(1);

  pushMatrix();
  translate(15, -5, 15);
  box(30, 10, 30);
  popMatrix();

  pushMatrix();
  translate(15, 50, 15);
  box(30, 30, 30);
  popMatrix();

  pushMatrix();
  strokeWeight(0.1);

  ArrayList<Particle> particles = ps.particles();
  for (int i = 0; i< particles.size(); i++ ) {

    point(
      particles.get(i).position.x, 
      particles.get(i).position.y, 
      particles.get(i).position.z
      );
  }

  popMatrix();
}

public  class ParticleSystem implements Runnable {

  boolean loop = true;
  ArrayList<Particle> particles;

  long lastUpdate;
  int updateInterval = 10;

  float maxTravelDistance = 35 ;
  float pRF = 0.005;  // particlesRandomFactor


  public ParticleSystem() {


    particles = new ArrayList<Particle>();

    for (int x = 0; x < 15; x++) {
      for (int z = 0; z < 15; z++) {
        for (int i = 0; i < 1000; i++)
        {
          particles.add(new Particle(new PVector(x*2, 0, z*2), new PVector(random(-pRF, pRF), random(-pRF, pRF), random(-pRF, pRF))));
        }
      }
    }
    new Thread(this).start();
    println(particles.size());
  }

  @ Override
  public void run() {

    while (loop) {
      if (millis()-lastUpdate > updateInterval && millis() > 3000) {
        if (particles.size() >0) {
          for (int i = particles.size()-1; i>0; i--) {
            if (particles.get(i).position.y > maxTravelDistance) particles.remove(i);
            else  particles.get(i).update();
          }
        }
        lastUpdate = millis();
      }
    }
  }


  ///////////particles
  public synchronized ArrayList<Particle> particles() {
    return particles;
  }




  public synchronized PVector[] getPositions() {

    //ArrayList<Particle>particlesToExport = particles().toArray(new Particle[particles.size()]);

    ArrayList<Particle>particlesToExport = particles;
    PVector[] output = new PVector[particlesToExport.size()];

    for (int i = 0; i < output.length; i++)
    {
      output[i] = particlesToExport.get(i).position();
    }

    return output;
  }
}


public  class  Particle {

  float mass;
  boolean isDead = false;
  float airDrag = 0.95;


  PVector position;
  PVector oldPosition;

  PVector speed;
  PVector acceleration;

  public Particle(PVector p, PVector s) {
    mass = random(0.9, 1.1);
    position = p;
    speed = s;
    acceleration = new PVector(0, 0.02*mass, 0);
  }

  void update() {
    //oldPosition = position;
    if (abs(speed.x) >=0.05 || abs(speed.z) >= 0.05) speed.mult(airDrag);
    if (!(speed.y > 10)) speed.add(acceleration);
    position.add(speed);
  }

  ///////////position
  public synchronized void position(PVector input) {
    position = input;
  }
  public synchronized PVector position() {
    return position;
  }
}

koogs

how many particles are you using?

secondsky

Actually a lot. I mean of course using less particles is gonna be faster. With a faster computer as well. But how to make it more efficient is a general question i guess, and in particular i would like to understand why there is this big slow down when the arraylist delete some component.

Chrisir

Not sure why you start a thread in the constructor of a class.....?

secondsky

To avoid doing it in the main thread after the class creation. Is doing it in the class itself an error?

kfrajer

On a side note, getPositions() can be rewritten like this //See: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html:

public synchronized PVector[] getPositions(){
  return (PVector[])(particles.toArray());   
}

Commenting out the remove(i) above will not affect performance. I agree with @koogs statement, what is slowing down the sketch is the number of particles used.

An additional thought. If you are thinking in generating more particles (hence you want to remove old particles), you could instead recycle them as in resetting their values to some initial state. Not sure if this could be applied to your challenge and this will not improved on your initial problem.

Kf

koogs

when you remove something from an array list, everything behind it is shuffled up one place. with a 1/4 of a million particles this might be a lot of shuffling.

might be better to iterate through them copying live particles into the space occupied by dead particles. then you can change your loops to iterate through the arraylist, stopping at the first null particle.

alternatively, other Lists might be more appropriate, ones with maybe slower create but faster remove. (LinkedHashSet?)

stackoverflow suggests this in place of remove

temp = list.remove(list.size() - 1);
return list.set(index, temp);

which copies the last element into the space of the item being deleted