Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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! –  james Dec 3 '11 at 14:25
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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