Problem 163 Colliding Balls

Graeme, thanks for your recomendations!

This problem really is bit to capricious, but I have no idea how to make it better. I believe that the checker does not use such a small steps, so probably there is a small difference in implementation of calculations... I'll try to play a bit with your soultions and see if anything could be improved in checker to make it more robust.

With the test data, I got 369 111 136 62 439 242 261 177 89 64 489 181 573 248 87 128

These are all within 50 of the expected values except for the 3rd line where the expected values are 24 127 416 124 but mine are 89 64 489 181.

However, my program was judged correct with test data of 4 113 107 487 193 180 56 -37 -8 124 97 476 203 155 37 -30 -9 196 70 404 230 155 96 -29 -22 133 68 467 232 141 60 -27 -13

where it gave the answer of 498 119 234 237 572 269 87 235 166 242 509 205 307 21 537 23.

I was lazy and copied the algorithm given. One possible thing that comes to mind is that this does not adjust x and y coordinates for the collision as is done when colliding with the walls.

My code is the almost the same as Quandray's with time interval of 0.001 on the test data i.e. 410 101 95 61 424 259 277 164 26 136 432 108 572 249 86 127

I've found that correct simulation step is dt=0.005. In this case it give exact numbers for the test examples.

But this problem has solution that doesn't require simulation step at all: you can find the time of next colliding of balls by solving of 4th degree equation:

coordinates of ball centers are changing by quadratic law:

x1(t)=x1(0)+t * v1x + t^2 * a1x/2

y1(t)=y1(0)+t * v1y + t^2 * a1y/2

and same for the second ball. And you have to solve (x1(t)-x2(t))^2+(y1(t)-y2(t))^2 = 4 * R^2, that is not difficult.

When you have colliding moment you can move balls to exactly this moment and change speeds there.

I would like to ask about the second part of function,I mean The collision(). My fuction for moving balls A and B works perfectly as i have ontained the result as example from problem, But i can match the new numbers immediatly after collision. Is everything allrighnr with math regarding collision ?

I am reffering mostrly at this part // Collision --------------------------------------------------// //first step---------// dx = Xb - Xa; dy = Yb - Ya; d = Math.sqrt(dxdx+ dydy); //end of first step--//

            // second step---------//
                if(d<=Radius*2){
                    vxc = (Vxa + Vxb) / 2;
                    vyc = (Vya + Vyb) / 2;
                    //-----------------------//
                    ux = Vxa - vxc;
                    uy = Vya - vyc;
                    //u = Math.sqrt(ux*ux + uy*uy);
                    //-----------------------//

                    //------------------------------//
                    ur=(ux*dx + uy*dy) / Math.abs(d);
                    //------------------------------//

                    //------------------------------//
                    uxr = ur * dx / d;
                    uyr = ur * dy / d;
                    //------------------------------//

                    //------------------------------//
                    Vxa = Vxa - 2 * uxr;
                    Vya = Vya - 2 * uyr;
                    Vxb = Vxb + 2 * uxr;
                    Vyb = Vyb + 2 * uyr;
                    //------------------------------//
                }
                 Is everything is right here ? . At least i tried to followe instruction given by this task on collision 

// Collision --------------------------------------------------// //first step---------// dx = Xb - Xa; dy = Yb - Ya; d = Math.sqrt(dxdx+ dydy); //end of first step--//

            // second step---------//
                if(d<=Radius*2){
                    vxc = (Vxa + Vxb) / 2;
                    vyc = (Vya + Vyb) / 2;
                    //-----------------------//
                    ux = Vxa - vxc;
                    uy = Vya - vyc;
                    //u = Math.sqrt(ux*ux + uy*uy);
                    //-----------------------//

                    //------------------------------//
                    ur=(ux*dx + uy*dy) / Math.abs(d);
                    //------------------------------//

                    //------------------------------//
                    uxr = ur * dx / d;
                    uyr = ur * dy / d;
                    //------------------------------//

                    //------------------------------//
                    Vxa = Vxa - 2 * uxr;
                    Vya = Vya - 2 * uyr;
                    Vxb = Vxb + 2 * uxr;
                    Vyb = Vyb + 2 * uyr;
                    //------------------------------//
                }

Then i have no idea what is wrong. I have a incriment of 0.001, in this way i am trying to come very close to collision moment the the code abave start working and give me new values for speeds balls, But i get differents numbers for Xa,Ya,Xb,Yb. Again my code works perfect when to move the balls, because till the very moment of collision i got the same numbers as in gebuging example but after collison a got absoltly differents numbers. That why i doubted the code above (collison cod). I have no clue where to look fo mistakes :(

Hi! Looks loke implementing functions checkCollision(ballA, ballB) following the steps showed in problem is not enough. Should be one more trick here.

Hi guys! As vancea.vladimir wrote on 2018-08-26 the algorithm checkCollision(ballA, ballB) proposed seems to me wrong.

First of all because if the velocity of one ball at collision time is higher then 2*Radius/dt the collision is not detected.

Second because we should try to detect the collision before we move the two balls. It means that when they are already overlapped, the new velocities are wrongly evaluated. The new velocity component (radial and tangential) should be evaluated in the perfect instant of time of collision. Neither before nor later. I'm going to find a formula to evaluate this instant of time and the algorithm should be:

if (checkCollision(ballA, ballB)){
  evaluate the instant t of collision
  calculate new position and new velocity at time=t
  go on with the ball movement
}

Another way could be to correct the new positions and new velocities evaluated after the collision but could be also more complicated.

To avoid this the only simpler way is to reduce dt=0.001 or lesser to reduce the error of evaluating the new position and velocity after the overlapping has already happend.

I'd like to have a feedback regard my analysis and ask to Rodion how did you get the following results?

• t xa ya xb yb
• 0.1: 253 127 362 175
• 0.2: 271 131 358 173
• 0.3: 289 134 355 172
• 0.4: 307 138 352 171
• 0.5: 323 139 350 171
• 0.6: 329 129 359 183

The collision happens between 0.4 and 0.5 but if we apply the collision algorithm in the same way it is described we should get the following values due to the error introduced by the overlapping.

• t xa ya xb yb
• 0.1: 253 127 362 175
• 0.2: 271 131 358 173
• 0.3: 289 134 355 172
• 0.4: 307 138 352 171
• 0.5: 327 138 351 172
• 0.6: 334 129 358 183

Did you reduce dt or just used a different approach?

Thank you for any feedback. Carlo.