Drawing lots of particles efficiently

Question

I have written a particle system applet; currently I am creating, and drawing each particle separately. (Here is the code)

BufferedImage backbuffer;
Graphics2D g2d;

public void init(){
    backbuffer = new BufferedImage(WIDTH,HEIGHT,BufferedImage.TYPE_INT_RGB);
    g2d = backbuffer.createGraphics();
    setSize(WIDTH, HEIGHT);

    //creates the particles
    for (int i = 0; i < AMOUNTPARTICLES; i++) {
        prtl[i] = new particleO();
        prtl[i].setX(rand.nextInt(STARTX));
        prtl[i].setY(rand.nextInt(STARTY));
        prtl[i].setVel(rand.nextInt(MAXSPEED)+1);
        prtl[i].setFAngle(Math.toRadians(rand.nextInt(ANGLESPREAD)));

        }

    //other code
}



    public void update(Graphics g) {        

    g2d.setTransform(identity);

    //set background
    g2d.setPaint(BGCOLOUR);
    g2d.fillRect(0,0,getSize().width,getSize().height);
    drawp();
    paint(g);           
    }


public void drawp() {

    for (int n = 0; n < AMOUNTPARTICLES; n++) {

    if (prtl[n].getAlive()==true){
            g2d.setTransform(identity);
            g2d.translate(prtl[n].getX(), prtl[n].getY());
            g2d.setColor(prtl[n].getColor());

            g2d.fill(prtl[n].getShape());


            }
    }

}

It's performance was alright, I could get ~40FPS with 20,000 particles (although, I have a decent laptop). But after I added collision detection (see below), that number plummeted to less than 2000,

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = 0; j < AMOUNTPARTICLES; j++) {

                if (i!=j && prtl[j].getAlive()==true){

                     if(hasCollided(i, j)){
                        prtl[i].setcolor(Color.BLACK);
                        prtl[j].setcolor(Color.BLACK);
     }
            }
  }

public boolean hasCollided(int prt1, int prt2){

        double dx = prtl[prt1].getX() - prtl[prt2].getX();
        double dy = prtl[prt1].getY() - prtl[prt2].getY();
        int edges =  prtl[prt1].getRadius() + prtl[prt2].getRadius();

        double distance = Math.sqrt( (dx*dx) + (dy*dy) );
        return (distance <= edges);


    }

I have searched quite a bit for a better way of drawing the particles to the screen, but the examples either confused me, or were not applicable.

I am doing a boat load of calculations (too many). But I couldn’t think of another way of doing it, suggestions are welcome.

Mckay

#13046533 – Merilee

Don't forget to accept an answer once you have decided which one helped you the most. – Gloria

Answer 1

First of all, adding in something like collision detection always takes a lot of memory. However, let's look at your collision detection algorithm

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = 0; j < AMOUNTPARTICLES; j++) {

                if (i!=j && prtl[j].getAlive()==true){

                     if(hasCollided(i, j)){
                        prtl[i].setcolor(Color.BLACK);
                        prtl[j].setcolor(Color.BLACK);
                }
            }
  }

Let's pretend there was only 2 particles, 1 and 2. You will check, in order 1,1 1,2 2,1 2,2

The truth is, you only really needed to check 1 vs 2 in this case. If 1 hits 2, 2 will also hit 1. So change your for loop skip previously tested, and the same number for that matter.

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = i+1; j < AMOUNTPARTICLES; j++) {

Another thing I notice is that you do a sqrt operation, but only to compare to what looks like a static number. If you remove that, and compare it to the number squared, you'll get a large improvement, especially with something you do so much.

    double distance_squared = ( (dx*dx) + (dy*dy) );
    return (distance <= edges*edges);

Keep looking for improvements like this. Then you might carefully look at other options, like using a different class, threading, etc, which all might improve the system. But make sure you optimize the code where you can first. Here is a list of other things that I would try, roughly in order.

1. Check to see if particle i is alive before you even calculate anything else after i comes into view.
2. Do a quick pass over the pairs, only even bothering to check in detail if they are close. A simple way would be to detect if they are within the x and y dimensions first, before taking a sqrt operation. Always do the cheapest test first, before doing complex ones.
3. Look at your code, to see if you really use all of the values calculated, or if you might be able to reduce the number of operations somehow.
4. Perhaps you could cluster the images on a regular basis with a broad stroke, then refine only objects which passed the initial cluster for a period of time, then do a broad cluster algorithm.
5. You could thread the collision detection. However, if you are going to do this, you should only thread the checking to see if something has collided, and after all of those threads are done, update the objects on the view.
6. Look into alternative architectures, which might speed things up some.

Gloria

Thanks alot, I was thinking of something like that (the nested for's) but it wouldnt come out of my head (+1'ed) – Mckay

No problem. Optimizing stuff like this is probably my favorite part of programming:-) – Gloria

Also, how about checking that particles have moved? Only draw particles that have moved since the last frame. The same goes for collisions; 2 particles that haven't moved won't collide into each other. – Genoese

That could be done, but it would be encompassed essentially by sub-dividing the image. It depends on how often the particles won't move. – Gloria

Answer 2

Painting is a complex process and paint requests can be triggered for any number of reasons, the OS might want the window to update, the repaint manager might want to repaint, the programer might want to repaint.

Updating the particles within the paint process is bad idea. What you want to do is update the particles in a separate thread on a separate buffer. When you're ready, request that the component responsible for painting the buffer perform a repaint, passing a new copy of the buffer to repainted (you don't want to be painting on the buffer that is begin updated to the screen, you'll end up with dirty paints).

It's hard to tell from you code, but it would appear you're using java.awt.Applet, personally, I'd upgrade to javax.swing.JApplet.

I'd move the painting to a java.swing.JPanel. Swing components provide double buffering (as well as other buffering strategies). The only job this panel has is to paint a buffer to the screen when the particles engine has a new frame.

The particles engine is responsible for updating all the particles and painting these results to a backing buffer (BufferedImage), this would then be handed to the panel and the panel would make a copy and schedule an update.

Swing is NOT THREAD SAFE. That is, you shouldn't make changes to the UI from any thread other then the Event Dispatching Thread. To this end, you might like to have a read through Concurrency in Swing for solutions to resync the off screen buffer to the client.

Testosterone

Answer 3

You are checking all particless colliding with all particlesand this is quite a requeriment, of the order of n^2 (2,000 particles means 4,000,000 combinations, for each frame).

The issue is not java but the algorithm. There must be better options, but to begin with you could reduce the comparations; if you have a maximum speed S and the time in your world increments by T, with T*S you get the maximum distance D of a particle that can collide with the particle you are considering. Reduce the search to those particle which are at a distance equal or less than that. Maybe it will be easier to restrict the search to those in an square centered in your particle an with height/widht D (this will include some particles that are too far, but will make the checks easier).

Additionally, in your code you are checking collisions of P1 vs P2 and P2 vs P1 which is the same, that is a redundance that you can avoid easily.

Senlac