Jump to content
  • Advertisement
Sign in to follow this  
thecoast47

2Dparticle System Preformance Issue

This topic is 2720 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a huge problem with the performance of my particle system. The major performance hit seems to occur when i check collision between two objects. I've heard of binary trees and searching but i dont know how to apply those ideas to my program.
Footage is of application is here:


Here is what happens :
  • I start the main thread
  • i set the frame
  • when the frame.repaint method is called the magic happens
    public void LaunchFrame() {
    frame = new JFrame();
    //button = new JButton();
    DrawPanel drawcircle = new DrawPanel();
    frame.setLocation(145, 0);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(800,700);
    frame.setVisible(true);
    frame.addMouseMotionListener(new MouseEvent());
    frame.addKeyListener(new GetKeyPressed());
    frame.getContentPane().add(BorderLayout.CENTER,drawcircle);
    while(DoAnimation){
    try{
    Thread.sleep(30);
    }catch(Exception error){
    error.printStackTrace();
    }
    frame.repaint();
    }
    }//End LaunchFrame() Method

    • This is what happens when the frame is repainted
    • This is the loop the passes the graphics object to all the [shape] objects so that they can be drawn to the screen
    • When the arraylist of shape objects is > 800 the fps drops to 5-10 fps[
      public void paintComponent(Graphics g){
      Graphics2D g2d = (Graphics2D) g;
      DrawFps(g2d);
      CircleList.get(0).setFrameWidth(frame.getWidth());
      CircleList.get(0).setFrameHeight(frame.getHeight());
      for (int i = 0; i < CircleList.size(); i++){
      Graphics2D TempGraphics = (Graphics2D) g2d.create();
      CircleList.get(i).Move(TempGraphics , CircleList ,i);
      }
      }

      /code]
      • Every Shape object has a method called move which handles ...well all the movement of the individual object. it looks like this
        public Graphics2D Move(Graphics2D g , ArrayList <Circle> CircleList,int K){
        double X;double Y;
        double acceleration = 0.05;
        double termVelocity = 20.1;
        double xVel = this.getXvel();
        double yVel = this.getYvel();
        double e= 0.8;
        double f= 0.8;


        X = this.getX();
        Y = this.getY();

        Circle.SearchCollision(CircleList, K);
        if(Y< this.getFrameHeight()-70 ){
        if(this.IgnoreGravity){
        this.IgnoreGravity = false;
        }else{
        yVel= yVel+ (termVelocity-yVel)*acceleration;
        if (yVel>=800){
        yVel = 20;
        }else{
        yVel++;
        }
        //System.out.println(Y);
        Y+=yVel;
        }
        }
        if(Y>=this.getFrameHeight() -70){
        //yVel =yVel* -1;
        yVel =yVel* -1*e;
        Y+=yVel;
        Y = this.getFrameHeight() - 100 ;
        }
        if (Y<=0 ){
        yVel =yVel* -1;
        Y+=yVel;
        }

        if (xVel != 0 ){
        if (xVel >= 200 || xVel <= -200 ){
        xVel = 0;
        }else{
        X+=xVel;
        if (xVel>0){
        xVel--;
        }
        if(xVel<0){
        xVel++;
        }
        }
        }
        if(X>=this.getFrameWidth() - this.getWidth()){
        xVel = xVel * -1;
        X+=xVel;
        }
        if(X<=0){
        xVel =xVel * -1;
        X+=xVel;
        }

        double Angle = 0;
        Angle = Math.atan2(yVel, xVel);
        this.setX(X);
        this.setY(Y);
        this.setYvel(yVel);
        this.setXvel(xVel);
        g.setColor(Color.BLUE);
        g.rotate(Angle ,this.getX() + this.getWidth()/2,this.getY() + this.getHeight()/2);
        g.drawRect((int)this.getX() ,(int)this.getY(), this.getWidth() , this.getHeight() );
        g.fillRect((int)this.getX(),(int) this.getY(), this.getWidth(), this.getHeight());
        g.setFont(new Font("sansserif", Font.BOLD, 8));
        g.setColor(Color.BLACK);
        return g;
        }

        public static void SearchCollision( ArrayList <Circle> CircleList,int K){


        for( int E = 0; E < CircleList.size() ;E++){
        double X1 = 0;
        double Y1 = 0;
        double X2 = (CircleList.get(K).getX() + CircleList.get(K).getWidth()/2);
        double Y2 = (CircleList.get(K).getY() + CircleList.get(K).getHeight()/2);
        X1 = (CircleList.get(E).getX() + CircleList.get(E).getWidth()/2);
        Y1 = (CircleList.get(E).getY() + CircleList.get(E).getHeight()/2);
        if(Math.sqrt( ( ((X2 -X1)*(X2-X1))+((Y2 -Y1)*(Y2-Y1)) ) ) < 5 ){
        Circle.CheckCollision(CircleList, K, E );
        }else{

        }
        }
        }

        public static void CheckCollision(ArrayList <Circle> CircleList,int K ,int J){
        double CurrentBottomLeftX = CircleList.get(K).getBottomLeftX();
        double CurrentBottomLeftY = CircleList.get(K).getBottomLeftY();
        double CurrentBottomRightX = CircleList.get(K).getBottomRightX();
        double CurrentBottomRightY = CircleList.get(K).getBottomRightY();

        double NextBottomLeftX = CircleList.get(J).getBottomLeftX();
        double NextBottomLeftY = CircleList.get(J).getBottomLeftY();
        double NextBottomRightX = CircleList.get(J).getBottomRightX();
        double NextBottomRightY = CircleList.get(J).getBottomRightY();
        double NextTopLeftY = CircleList.get(J).getTopLeftY();
        double NextTopLeftX = CircleList.get(J).getTopLeftX();
        double NextTopRightY = CircleList.get(J).getTopRightY();
        double NextTopRightX = CircleList.get(J).getTopRightX();

        if(CurrentBottomLeftX > NextTopLeftX){
        if(CurrentBottomLeftX < NextTopRightX){
        if (CurrentBottomLeftY > NextTopLeftY){
        if(CurrentBottomLeftY < NextBottomLeftY ){
        double Kyvel = CircleList.get(K).getYvel();
        double Jyvel = CircleList.get(J).getYvel();
        if(CircleList.get(K).IgnoreGravity || CircleList.get(J).IgnoreGravity ){

        }else{
        CircleList.get(J).setYvel(CircleList.get(J).getYvel() *-1);
        CircleList.get(K).setYvel(CircleList.get(K).getYvel() *-1);
        //CircleList.get(K).IgnoreGravity = true;
        //CircleList.get(J).IgnoreGravity = true;
        }
        }
        }
        }
        }//End if
        if (CurrentBottomLeftX > NextBottomLeftX){
        if (CurrentBottomLeftX < NextBottomRightX ){
        if(CurrentBottomLeftY < NextBottomLeftY){
        if(CurrentBottomLeftY > NextTopLeftY){

        if(CircleList.get(J).getXvel() == 0){
        CircleList.get(J).setXvel(CircleList.get(K).getXvel());
        CircleList.get(K).setXvel(CircleList.get(K).getXvel()*-1);

        }else{
        CircleList.get(J).setXvel(CircleList.get(J).getXvel() *-1);
        CircleList.get(K).setXvel(CircleList.get(K).getXvel() *-1);
        }
        }
        }
        }
        }//End if
        if (CurrentBottomRightX > NextBottomLeftX){
        if (CurrentBottomRightX < NextBottomRightX ){
        if(CurrentBottomRightY < NextBottomLeftY){
        if(CurrentBottomRightY > NextTopLeftY){
        if(CircleList.get(J).getXvel() == 0){
        CircleList.get(J).setXvel(CircleList.get(K).getXvel());
        CircleList.get(K).setXvel(CircleList.get(K).getXvel() *-1);
        }else{
        CircleList.get(J).setXvel(CircleList.get(J).getXvel() *-1);
        CircleList.get(K).setXvel(CircleList.get(K).getXvel() *-1);
        }
        }
        }
        }
        }//end if

        }


        Any suggestions on how i can improve performance?

Share this post


Link to post
Share on other sites
Advertisement
Your big problem here is that your collision detection algorithm is O(n^2). This means that, as the number of particles increases, the number of collision checks you have to do is squared. So when you have 8 circles, you do 8*8=64 collision checks. When you have 80 circles, you do 80*80=6400 collision checks. When you have 800 circles, you do 800*800=640000 checks. In other words, going from 80 to 800 circles, even though there are only 10 times as many circles, you are doing 100 times as many checks.

So how do you fix this? Well, basically, you have to come up with a way to get rid of *most* of the collision checks quickly. After all, the fastest code is the code that never runs. There are a few ways to do this, with the binary trees you mention being one of them. No matter what, it will boil down into sorting the circles in some fashion that allows you to only do a collision check against circles that are close. This adds an extra step, but as a sort will generally be much, much faster than brute forcing all possible collision checks, you generally come out WAY ahead performance-wise.

Just to get you started, try this. Before you do your collision checks, sort your circle array list along the x-axis. Do this first, and only once per frame. Also, you will need to determine the maximum width of all of the circles. Once you have your circles sorted along the x-axis, and know the maximum size of the circles, you only need to check for the circles immediately behind and in front of you in the list until you travel the width of the largest circle away! This means you only need to do checks against a small fraction of the other circles, and not every single one. If it isn't immediately apparent why this is the case, try drawing a picture of it. Draw a bunch of random circles on a page, get a ruler, and pick a random circle. Start sliding the ruler back and forth. See how it's impossible to intersect once you're a certain distance away from the circle?

Now, your collision checking algorithm looks like this (in psuedo-java):


sortAllCirclesAlongTheXAxis();

float maximumWidth = 0;
for(int i = 0; i < circleArray.size(); i++)
{
if(circle.getWidth() > maximumWidth)
{
maximumWidth = circle.getWidth();
}
}

for(int i = 0; i < circleArray.size(); i++)
{
Circle thisCircle = circleArray;

// check all circles behind us until we are past the maximum circle width. After we are maximumWidth away, it is impossible to collide!
// we can ignore every other circle from that point back for maximum speedup!
float distanceFromThisCircle = 0;
for(int other = 0; other >= 0 && distanceFromThisCircle < maximumWidth; other--)
{
Circle otherCircle = circleArray[other];
distanceFromThisCircle = otherCircle.distanceTo(thisCircle);
CheckCollision(otherCircle, thisCircle);
}

// now do the same thing, but checking the circles in front of us
distanceFromThisCircle = 0;
for(int other = 0; other < circleArray.size() && distanceFromThisCircle < maximumWidth; other++)
{
Circle otherCircle = circleArray[other];
distanceFromThisCircle = otherCircle.distanceTo(thisCircle);
CheckCollision(otherCircle, thisCircle);
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!