5
\$\begingroup\$

I have a program which simulates many bouncing balls. The balls can bounce off each other and off the sides of the container.

The problem I am having is that sometimes when two balls collide, they get stuck together, overlapping very slightly. They will not come apart on their own, but may disperse if another ball knocks into them.

Here is my collision detection and resolution code:

public void handleCollisions(){
        double xDist, yDist, distanceBetween;
        for(int i = 0; i < balls.size(); i++){
            Ball A = balls.get(i);
            for(int j = i+1; j < balls.size(); j++){
                Ball B = balls.get(j);
                xDist = Math.abs(A.getCenterX() - B.getCenterX());
                yDist = Math.abs(A.getCenterY() - B.getCenterY());
                distanceBetween = Math.sqrt(xDist*xDist + yDist*yDist);
                if(distanceBetween <= (A.radius + B.radius)){           
                        double dx = A.getCenterX() - B.getCenterX();
                        double dy = A.getCenterY() - B.getCenterY();
                        double collisionAngle =  Math.atan2(dy, dx);
                        double magnitudeA =  Math.sqrt(A.xVel*A.xVel + A.yVel*A.yVel);
                        double magnitudeB =  Math.sqrt(B.xVel*B.xVel + B.yVel*B.yVel);
                        double directionA =  Math.atan2(A.yVel, A.xVel);
                        double directionB =  Math.atan2(B.yVel, B.xVel);
                        double xVelOnCollisionAxisA = magnitudeA*Math.cos(directionA - collisionAngle);
                        double yVelOnCollisionAxisA = magnitudeA*Math.sin(directionA - collisionAngle);
                        double xVelOnCollisionAxisB = magnitudeB*Math.cos(directionB - collisionAngle);
                        double yVelOnCollisionAxisB = magnitudeB*Math.sin(directionB - collisionAngle);
                        double postCollisionXVelA = ((A.mass - B.mass)*xVelOnCollisionAxisA + (B.mass*2)*xVelOnCollisionAxisB) /(A.mass + B.mass);
                        double postCollisionXVelB = ((A.mass*2) * xVelOnCollisionAxisA + (B.mass - A.mass)*xVelOnCollisionAxisB)/ (A.mass + B.mass); 
                        A.xVel =  (Math.cos(collisionAngle)*postCollisionXVelA + Math.cos(collisionAngle+Math.PI/2)*yVelOnCollisionAxisA);
                        A.yVel =  (Math.sin(collisionAngle)*postCollisionXVelA + Math.sin(collisionAngle+Math.PI/2)*yVelOnCollisionAxisA);
                        B.xVel =  (Math.cos(collisionAngle)*postCollisionXVelB + Math.cos(collisionAngle+Math.PI/2)*yVelOnCollisionAxisB);
                        B.yVel =  (Math.sin(collisionAngle)*postCollisionXVelB + Math.sin(collisionAngle+Math.PI/2)*yVelOnCollisionAxisB);                          
                }
                }
            }
        }              

So essentially, the method iterates through all possible combinations of two balls. If the distance between them is less than the sum of their radii then a collision is detected and the velocities of each ball are changed.

The next method to run will update the positions of the balls, before the above method is called again.

It appears that my problem occurs when a collision is detected, but on the next pass of the function, the ball is still seen as being inside the other ball and receives a collision whilst trying to get out.

I have tried adding this code when a collision is detected. I expected this to solve the problem by moving the balls to their last position before the collision, but the problem persists

                        A.posX -= A.xVel;
                        A.posY -= A.yVel;
                        B.posX -= B.xVel;
                        B.posY -= B.yVel;

Actually for multiple balls, I'm not sure the above snippet is a good idea anyway.

\$\endgroup\$
10
\$\begingroup\$

The very simple solution:
Check whether the balls are moving towards or away from one another, perform the collision only if they are moving towards one another.

The badly needed change:
Your code is pretty much walking circles around the concept of vector maths, you do not need the trigonometric functions at all.

public void handleCollisions(){
    double xDist, yDist;
    for(int i = 0; i < balls.size(); i++){
        Ball A = balls.get(i);
        for(int j = i+1; j < balls.size(); j++){
            Ball B = balls.get(j);
            xDist = A.getCenterX() - B.getCenterX();
            yDist = A.getCenterY() - B.getCenterY();
            double distSquared = xDist*xDist + yDist*yDist;
            //Check the squared distances instead of the the distances, same result, but avoids a square root.
            if(distSquared <= (A.radius + B.radius)*(A.radius + B.radius)){
                double xVelocity = B.xVel - A.xVel;
                double yVelocity = B.yVel - A.yVel;
                double dotProduct = xDist*xVelocity + yDist*yVelocity;
                //Neat vector maths, used for checking if the objects moves towards one another.
                if(dotProduct > 0){
                    double collisionScale = dotProduct / distSquared;
                    double xCollision = xDist * collisionScale;
                    double yCollision = yDist * collisionScale;
                    //The Collision vector is the speed difference projected on the Dist vector,
                    //thus it is the component of the speed difference needed for the collision.
                    double combinedMass = A.mass + B.mass;
                    double collisionWeightA = 2 * B.mass / combinedMass;
                    double collisionWeightB = 2 * A.mass / combinedMass;
                    A.xVel += collisionWeightA * xCollision;
                    A.yVel += collisionWeightA * yCollision;
                    B.xVel -= collisionWeightB * xCollision;
                    B.yVel -= collisionWeightB * yCollision;
                }
            }
        }
    }
}

Since it is Java I haven't tested this code, so if it behaves strange, there is a bug somewhere.

Go and learn some vector maths, it is incredibly useful.

\$\endgroup\$
  • \$\begingroup\$ I've just done a quick run of the code. I'm quite surprised, given the far greater simplicity of the code you posted. I very much appreciate the time it must have taken you. Thanks! \$\endgroup\$ – james Dec 3 '11 at 14:25
  • \$\begingroup\$ This doesn't prevent balls flighting through each other when the velocity is a value that doesn't create any overlap between the two balls. The ball can simply skip over the other ball. \$\endgroup\$ – Christopher Done Feb 26 '17 at 20:15
  • 2
    \$\begingroup\$ @ChristopherDone Clipping is another issue entirely; this code only looks at handling collisions when they exist, and does so very well. \$\endgroup\$ – ArtOfCode Mar 10 '17 at 13:27
  • \$\begingroup\$ No, I mean that a logical collision is being missed. Try it on paper. Draw two balls sliding towards eachother, the first travelling at 1cm per frame, and the second ball travels at -10cm per frame, you might have a frame where they collide, or the second might just jump over the first. You think that makes sense? No, they collided alright, your code just didn't take it into account. \$\endgroup\$ – Christopher Done Mar 11 '17 at 14:31
1
\$\begingroup\$

Handling simultaneous collisions between more than two balls (e.g. balls A and B simultaneously colliding with C) is hard. And yet it's bound to happen when you have a lot of balls in a small space. You want to think not just in terms of separating pairs of balls but in terms of conserving energy and momentum while respecting each collision's restitution.

I'm not sure whether SIGGRAPH has published anything more recent, but the paper which I used as a basis for multiple collision handling in my most physics-demanding game was

Complementarity Based Multiple Point Collision Resolution
Thanh Giang, Gareth Bradshaw and Carol O'Sullivan
Eurographics Ireland Workshop, pp1 - 7 (2003)
http://isg.cs.tcd.ie/cosulliv/Pubs/GiangEgirl03.pdf

\$\endgroup\$
1
\$\begingroup\$

I had a similar problem and just added a loop after updating the velocities that fixed it. The loop checks whether the two balls are colliding and moves both of them if they are, until they are no longer within each other's range.

Something like:

 while (distanceBetween <= (A.radius + B.radius)) {
 A.move();
 B.move();
 }

That should follow immediately after updating the velocities to make sure the balls move away from each other.

\$\endgroup\$
0
\$\begingroup\$

I would say you have to get the balls out of each others radius first. Let's say push the target ball 1pixel out of the second ball's radius so the collision detection won't happen in the next loop. Then you can reverse the velocities.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.