Circle/ball collision problem....

[scheppy]

Hi Guys,

Im currantly having a problem with simulating balls bouncing of each other in a 2d space, everything is working and all,
but it just doesant seem natural for me...

If we had any math wizzes here now is your time please:)

my circles are painted inside of rectangles.....

This is what is the code im using to find the new x and y coordinates of the circles.

specifically this piece here...

 //Pythagerum theorem, a^2 + b^2 = c^2, to figure out the distance between the two circles' centers.
                    int distance = (int) Math.sqrt(((currantXa - currantXb) * (currantXa - currantXb)) + ((currantYa - currantYb) * (currantYa - currantYb)));

                    if (distance < radiasa + radiasb) {//if the distance is less than both thier radius combined, than they collided

                        int newSpeedXA = (xSpeeda * (massA - massB) + (2 * massA * xSpeedb)) / (massB + massA);
                        int newSpeedYA = (ySpeeda * (massA - massB) + (2 * massA * ySpeedb)) / (massB + massA);
                        int newSpeedXB = (xSpeedb * (massB - massA) + (2 * massB * xSpeeda)) / (massB + massA);
                        int newSpeedYB = (ySpeedb * (massB - massA) + (2 * massB * ySpeeda)) / (massB + massA);

full loop

//here we are detecting collision with other balls...
        int xSpeeda, xSpeedb, ySpeeda, ySpeedb, currantXa, currantXb, currantYa, currantYb, radiasa, radiasb, massA, massB;
        Color Colora, Colorb;
        for (int x = 0; x < CircleRect.size(); x++) {
            for (int y = 0; y < CircleRect.size(); y++) {
                //first checking if the rectangle colide, to save cpu
                if (CircleRect.get(x).intersects(CircleRect.get(y)) && x != y) {//!=y so we dont check the same circle against itself

                    Ball balla, ballb;

                    //getting the objects
                    balla = Circles.get(x);
                    ballb = Circles.get(y);

                    //getting thier data
                    xSpeeda = balla.getxSpeed();
                    xSpeedb = ballb.getxSpeed();
                    ySpeeda = balla.getySpeed();
                    ySpeedb = ballb.getySpeed();
                    currantXa = balla.getX();
                    currantXb = ballb.getX();
                    currantYa = balla.getY();
                    currantYb = ballb.getY();
                    radiasa = balla.getDiameter() / 2;
                    radiasb = ballb.getDiameter() / 2;
                    massA = balla.getMass();
                    massB = ballb.getMass();

                    //Pythagerum theorem, a^2 + b^2 = c^2, to figure out the distance between the two circles' centers.
                    int distance = (int) Math.sqrt(((currantXa - currantXb) * (currantXa - currantXb)) + ((currantYa - currantYb) * (currantYa - currantYb)));

                    if (distance < radiasa + radiasb) {//if the distance is less than both thier radius combined, than they collided

                        Colora = balla.getColor();
                        Colorb = ballb.getColor();

                        int newSpeedXA = (xSpeeda * (massA - massB) + (2 * massA * xSpeedb)) / (massB + massA);
                        int newSpeedYA = (ySpeeda * (massA - massB) + (2 * massA * ySpeedb)) / (massB + massA);
                        int newSpeedXB = (xSpeedb * (massB - massA) + (2 * massB * xSpeeda)) / (massB + massA);
                        int newSpeedYB = (ySpeedb * (massB - massA) + (2 * massB * ySpeeda)) / (massB + massA);

                        balla.setxSpeed(newSpeedXA);
                        balla.setySpeed(newSpeedYA);

                        ballb.setxSpeed(newSpeedXB);
                        ballb.setySpeed(newSpeedYB);

                        //adding thier new speeds so they are not colided anymore and the loops doesant check them twice
                        balla.setX(currantXa + newSpeedXA);
                        balla.setY(currantYa + newSpeedYA);

                        ballb.setX(currantXb + newSpeedXB);
                        ballb.setY(currantYb + newSpeedYB);

                        balla.setColor(Colorb);
                        ballb.setColor(Colora);

                        Circles.set(x, balla);
                        Circles.set(y, ballb);

                        ConvertBallToRect(x, balla);
                        ConvertBallToRect(y, ballb);
                    }
                }
            }
        }

[JamesCherrill]

No time for a proper answer now, but here's some code I use that I modified from something on the web that bounces balls a and b that have position x,y and velocity dx,dy. I gives bounces that look very realistic to me. It's very similar to your code,

        double ra = a.width / 2; // radius
        double rb = b.width / 2; // radius
        double radiiSquared = (ra + rb) * (ra + rb);  // square sum of radii
        double xDist = (a.x + ra) - (b.x + rb);
        double yDist = (a.y + ra) - (b.y + rb);
        double distSquared = xDist * xDist + yDist * yDist;
        if (distSquared > radiiSquared) return false; // balls don't touch

        // circles touch (or overlap) so they bounce off each other...
        double xVelocity = b.dx - a.dx;
        double yVelocity = b.dy - a.dy;
        double dotProduct = xDist * xVelocity + yDist * yVelocity;
        if (dotProduct > 0) { // moving towards each other
            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.width * a.width + b.width * b.width; // mass porp. to area
            double collisionWeightA = 2* b.width * b.width / combinedMass;
            double collisionWeightB = 2* a.width * a.width / combinedMass;
            a.dx += collisionWeightA * xCollision;
            a.dy += collisionWeightA * yCollision;
            b.dx -= collisionWeightB * xCollision;
            b.dy -= collisionWeightB * yCollision;
        }

ps: I did find that running the model calculations in integers doesn't work well, especially when things are moving slowly. I use doubles for the model and just round to int when drawing the objects

[scheppy]

ok thanks for the tip on ints.

also, my circles all have thier own mass.... they could be the same size, but the one could be lead, and one could be foam....

also differant sizes.

I will look at this in depth when i get home:)

[AssertNull]

I did find that running the model calculations in integers doesn't work well, especially when things are moving slowly. I use doubles for the model and just round to int when drawing the objects

Agree. I never use integers for this kind of thing. Too much round-off error. More to the point, too much compounding round-off error. Anytime you're dealing with velocity and acceleration and positions and collisions and time, etc., well the math isn't generally too bad, but you have to think (A LOT) about all the potential round-off error and how to store things and whether/when to use threads. I don't want to get you too overwhelmed too early, but even in a 2D world with a few balls and a few walls, it can potentially get quite computationally intensive and you have to decide how good is "good enough". Stick that thought in the back of your head.

For now, though, I'm assuming this isn't much of an issue until you say otherwise. Or perhaps not?

also, my circles all have thier own mass.... they could be the same size, but the one could be lead, and one could be foam....

also differant sizes.

The nice thing about circles is that it's extremely easy to determine if/when they collide with each other as compared with other object types. It's particularly easy when they crash straight into each other in a head-on collision(the direction of ball 1 is 180 degrees off of the direction of ball 2). If the direction is the same but the velocities are different (ie ball 1 rear-ends ball 2), it's slightly more difficult, but not too bad. Collisions at an angle are much more involved.

Now again, not to get too technical, but there are elastic collisions and inelastic collisions. An elastic collision would be two pool balls colliding or two cars colliding with no damage to either and no springs on either car. That's the easy one to calculate. What that means is that there is Conservation of Momentum and Conservation of Energy. Dust off the Physics book and look those terms up along with "Elastic Collision". Put aside the computer programming and do a few pencil and paper calculations.

Why am I mentioning all of this? Because I am looking at the code and, while I haven't run it, it appears that those are the assumptions (100% elastic collision, 100% Conservation of Motion, 100% Conservation of Energy) and I think it is important to point it out explicitly. This type of problem is tailor made for Java's Object Oriented design and you'll need and want to separate the code (the physics calculations as separate as possible from the ball's color, etc., and all GUI and painting code separate from the calculations and the ball).

Hopefully this doesn't add to the confusion, but rather clarifies things. I can't stress enough the importance of understanding some of the Physics behind this stuff first. It can very quickly get overwhelming when you start making it more complex. I've left off some other issues I see.

[AssertNull]

I'm going to write up a quick functioning Swing implementation using Object Oriented principles to show what I mean, trying to stay as close to your and James' calculation code as possible. Check back in a few hours.

[JamesCherrill]

he nice thing about circles is that it's extremely easy to determine if/when they collide with each other ... Collisions at an angle are much more involved.

Not too bad - the first 7 lines of the code I posted, or lines 30-32 of OP's, do exactly that for the general case.
I agree about the importance of separating the code and the relevance of OO as a way to do it. I tried to steer OP in that direction in an earlier thread.

A couple of years ago I did a demo verion of bouncing balls (etc etc) for a tutorial series, using a lot of subclassing for different kinds of sprites and collisions. More recently I did a new version using pluggable behaviours and a single Sprite class, and I think that scales with complexity a lot better. I'm happy to share if anyone is interested.

even in a 2D world with a few balls and a few walls, it can potentially get quite computationally intensive

I was surprised at how well this stuff can run, even on an unexceptional machine. I was bouncing >50 balls off the sides and each other at 120 updates per sec for the model and 60 fps for the repaints and it ran perfectly with <30% CPU on a 2009 iMac.

ps: I forgot to credit the source for the bounce algorithm. I found it here

[scheppy]

ok thanks guys, hey james, what does your dx and dy veriables mean??
I made them for the x and y speed, but just made the ball go crazy.

nvm, i got it to work now, but its seems to bring some of my circles to a stand still....
how do i keep this from happening?? i want them to be moving at all times...

Thanks

Scheppy.

[Reverend Jim]

I presume delta (change in) x and delta y (calculus terms).

[JamesCherrill]

Yes, in my code dx and dy are the speed in the x and y directions.
If things stop moving that may be a result of using int calculations rather than doubles? (see previous posts)

[scheppy]

No i accually changed everything to doubles.

@AssertNull, as for the colors, the balls each have 1 if 5 possible colors and when they colide i am having them switch colors..

@Reverend Jim what do you mean by this?

[scheppy]

Im still getting into the oop habit btw, guys. learning somthing new everyday. This is my first kinda oop project :). No excuses though.

[AssertNull]

In general, I see two approaches to problems like this. The first one is the one that most people use, is less complicated, less code, less computationally expensive, and is generally considered "good enough". It is also less accurate, sometimes dramatically so.

1. You have n balls inside of a width by height rectangle arena. Each ball has a mass, a radius, a position, and a velocity. Sometimes you have an acceleration value too, but for simplicity, let's say not here. Let's make n equal to 4 balls and the arena be a 1000 by 1000 square. For further ease of calculation, let's give all balls a radius of 100 and a mass of 1. Let's have each of the balls start at one corner of the arena. Thus there are no intersections at the start except for the "intersection" of each ball with the wall since they each touch the wall.
2. We create the Ball objects and an Arena class that contains an ArrayList of Balls and the walls and execute an initial paint of a JPanel that paints the Arena (a 1000 x 1000 box with 4 balls inside).
3. We choose a "refresh rate". You chose 120 per second, but again, for easy math, let's make it 100 per second.
4. We'll give each ball an initial velocity. It could be randomly generated, user specified, or whatever.
5. We set a Timer for 1/100th of a second or use some other technique with an elapsed time. When at least 1/100th of a second has elapsed since the Ball locations were calculated, we call a function in Arena that recalculates the new Ball locations assuming that no collisions have occurred.
6. For each Ball, we compare the new location to make sure it has not intersected with the Wall. If it has, we change the Ball velocity to reflect a bounce. It's an easy calculation. If it has bounced off of a left/right wall, we multiply the x velocity by -1. If a top/bottom wall, we do the same for the y velocity.
7. Pairwise, for each pair of Balls, we check to see if their new positions intersect. If they do, we adjust each Ball's velocity using the math you used, which I assume is correct.
8. Repeat steps 5 through 7.

That's technique 1. You can get a very nice animation that appears quite good to the naked eye. It has all the advantages mentioned. The DIS-advantage is that you can miss some collisions and you can be off on the collision timing by the refresh rate (1/100th of a second) or more. The round-off errror is much greater than the round-off error of the precision of doubles in Java A few examples. Recall a refresh rate of 100 / second and the ball radius of 100.

1. Assume 2 Balls are coming right at each other at a velocity of 100/sec and are infinitesimally close to each other at the last calculation. By the time of the next calculation, they are overlapping by 2 full pixels or more, so the calculation is that far off.
2. Consider 2 balls rushing towards each other which will barely graze each other and collide. They could go right past each other between calculations and a collision that should have occurred will not be detected, with dramatic results.
3. Consider MULTIPLE collisions within the time of a refresh, like 2 pool balls colliding a split second before hitting a 3rd pool ball. To get accurate trajectories, you need to calculate the exact time of each collision and you must know which collision occurs first.

These aren't trivial concerns. It doesn't take much to see how a handful of these "errors" or even one of them could change the Arena enormously.

The designer must think hard about how good is "good enough", which errors are in the tolerable range, and which errors absolutely must be avoided. If it is decided that the first technique's potential error ramifications are unacceptably high, then more complicated techniques must be used to determine for sure whether and when the next collision happens.

One of the commenters in your link commented on this...

if the number of balls is low, you would get better results by never letting the balls overlap in the first place. That is you check for all pairs of balls if they will collide before the next time step. If you find a collision, move the balls to the collision point, resolve the velocities and continue the simulation.

[AssertNull]

I'll let the previous post stand, but from the OP's posts and experience level I believe it is appropriate to use the simple technique (technique 1) and not worry about the potential pitfalls I mentioned.

[AssertNull]

Im currantly having a problem with simulating balls bouncing of each other in a 2d space, everything is working and all,
but it just doesant seem natural for me...

Then...

I made them for the x and y speed, but just made the ball go crazy.

Then...

nvm, i got it to work now

Then...

but its seems to bring some of my circles to a stand still....
how do i keep this from happening?? i want them to be moving at all times...

I'm a little confused OP. What's working? What isn't? You seem to have started out with working code, but you didn't understand WHY it was working. Now it's not working. Or it's working? Might be time for a code and question update. I'm not going to write something up if it's already working. Also, what's your Math/Physics background? You are apparently unfamiliar with Calculus and rates of change? It is going to be hard to understand velocities then. Those are rates of change. You might need to put the project on hold and learn a few Physics concepts.

[scheppy]

Yes i startout with working code... but the angles of reflections, or when the balls bounce apart where not accurate... and if the balls had differant diameters, it would not work iether.

but I know what you mean, sorry about that.

I now have JamesCherrill version working.

Thanks for everything guys.