Ball to Ball Collision - Detection and Handling

Question

With the help of the Stack Overflow community I ve written a pretty basic-but fun physics simulator     You click and drag the mouse to launch a ball   It will bounce around and eventually stop on the  floor    My next big feature I want to add in is ball to ball collision   The ball s movement is broken up into a x and y speed vector   I have gravity  small reduction of the y vector each step   I have friction  small reduction of both vectors each collision with a wall   The balls honestly move around in a surprisingly realistic way   I guess my question has two parts    What is the best method to detect ball to ball collision  Do I just have an O n 2  loop that iterates over each ball and checks every other ball to see if it s radius overlaps  What equations do I use to handle the ball to ball collisions  Physics 101 How does it effect the two balls speed x y vectors   What is the resulting direction the two balls head off in   How do I apply this to each ball      Handling the collision detection of the  walls  and the resulting vector changes were easy but I see more complications with ball-ball collisions   With walls I simply had to take the negative of the appropriate x or y vector and off it would go in the correct direction   With balls I don t think it is that way   Some quick clarifications  for simplicity I m ok with a perfectly elastic collision for now  also all my balls have the same mass right now  but I might change that in the future     Edit  Resources I have found useful  2d Ball physics with vectors  2-Dimensional Collisions Without Trigonometry pdf 2d Ball collision detection example  Adding Collision Detection    Success   I have the ball collision detection and response working great   Relevant code   Collision Detection   for  int i   0  i  lt  ballCount  i              for  int j   i   1  j  lt  ballCount  j                      if  balls i  colliding balls j                            balls i  resolveCollision balls j                        This will check for collisions between every ball but skip redundant checks  if you have to check if ball 1 collides with ball 2 then you don t need to check if ball 2 collides with ball 1   Also  it skips checking for collisions with itself    Then  in my ball class I have my colliding   and resolveCollision   methods   public boolean colliding Ball ball        float xd   position getX   - ball position getX        float yd   position getY   - ball position getY         float sumRadius   getRadius     ball getRadius        float sqrRadius   sumRadius   sumRadius       float distSqr    xd   xd     yd   yd        if  distSqr  lt   sqrRadius                return true             return false     public void resolveCollision Ball ball           get the mtd     Vector2d delta    position subtract ball position        float d   delta getLength           minimum translation distance to push balls apart after intersecting     Vector2d mtd   delta multiply   getRadius     ball getRadius   -d  d             resolve intersection --        inverse mass quantities     float im1   1   getMass         float im2   1   ball getMass            push-pull them apart based off their mass     position   position add mtd multiply im1    im1   im2         ball position   ball position subtract mtd multiply im2    im1   im2             impact speed     Vector2d v    this velocity subtract ball velocity        float vn   v dot mtd normalize             sphere intersecting but moving away from each other already     if  vn  gt  0 0f  return          collision impulse     float i    - 1 0f   Constants restitution    vn     im1   im2       Vector2d impulse   mtd normalize   multiply i           change in momentum     this velocity   this velocity add impulse multiply im1        ball velocity   ball velocity subtract impulse multiply im2         Source Code  Complete source for ball to ball collider     If anyone has some suggestions for how to improve this basic physics simulator let me know   One thing I have yet to add is angular momentum so the balls will roll more realistically   Any other suggestions   Leave a comment

User · Answer

As a clarification to the suggestion by Ryan Fox to split the screen into regions, and only checking for collisions within regions...

e.g. split the play area up into a grid of squares (which will will arbitrarily say are of 1 unit length per side), and check for collisions within each grid square.

That's absolutely the correct solution. The only problem with it (as another poster pointed out) is that collisions across boundaries are a problem.

The solution to this is to overlay a second grid at a 0.5 unit vertical and horizontal offset to the first one.

Then, any collisions that would be across boundaries in the first grid (and hence not detected) will be within grid squares in the second grid. As long as you keep track of the collisions you've already handled (as there is likely to be some overlap) you don't have to worry about handling edge cases. All collisions will be within a grid square on one of the grids.

User · Answer

This KineticModel is an implementation of the cited approach in Java

User · Answer

Improving the solution to detect circle with circle collision detection given within the question  float dx   circle1 x - circle2 x        dy   circle1 y - circle2 y         r   circle1 r   circle2 r  return  dx   dx   dy   dy  lt   r   r    It avoids the unnecessary  quot if with two returns quot  and the use of more variables than necessary

User · Answer

A good way of reducing the number of collision checks is to split the screen into different sections  You then only compare each ball to the balls in the same section

User · Answer

I found an excellent page with information on collision detection and response in 2D  http   www metanetsoftware com technique html  web archive org  They try to explain how it s done from an academic point of view  They start with the simple object-to-object collision detection  and move on to collision response and how to scale it up  Edit  Updated link

User · Answer

Well  years ago I made the program like you presented here  There is one hidden problem  or many  depends on point of view       If the speed of the ball is too high  you can miss the collision    And also  almost in 100  cases your new speeds will be wrong  Well  not speeds  but positions  You have to calculate new speeds precisely in the correct place  Otherwise you just shift balls on some small  error  amount  which is available from the previous discrete step   The solution is obvious  you have to split the timestep so  that first you shift to correct place  then collide  then shift for the rest of the time you have

User · Answer

I found an excellent page with information on collision detection and response in 2D  http   www metanetsoftware com technique html  web archive org  They try to explain how it s done from an academic point of view  They start with the simple object-to-object collision detection  and move on to collision response and how to scale it up  Edit  Updated link

User · Answer

I implemented this code in JavaScript using the HTML Canvas element  and it produced wonderful simulations at 60 frames per second   I started the simulation off with a collection of a dozen balls at random positions and velocities   I found that at higher velocities  a glancing collision between a small ball and a much larger one caused the small ball to appear to STICK to the edge of the larger ball  and moved up to around 90 degrees around the larger ball before separating    I wonder if anyone else observed this behavior    Some logging of the calculations showed that the Minimum Translation Distance in these cases was not large enough to prevent the same balls from colliding in the very next time step   I did some experimenting and found that I could solve this problem by scaling up the MTD based on the relative velocities   dot velocity   ball 1 velocity dot ball 2 velocity   mtd factor   1    0 5   Math abs dot velocity   Math sin collision angle    mtd multplyScalar mtd factor     I verified that before and after this fix  the total kinetic energy was conserved for every collision   The 0 5 value in the mtd factor was the approximately the minumum value found to always cause the balls to separate after a collision   Although this fix introduces a small amount of error in the exact physics of the system  the tradeoff is that now very fast balls can be simulated in a browser without decreasing the time step size

User · Answer

You have two easy ways to do this  Jay has covered the accurate way of checking from the center of the ball   The easier way is to use a rectangle bounding box  set the size of your box to be 80  the size of the ball  and you ll simulate collision pretty well   Add a method to your ball class   public Rectangle getBoundingRect        int ballHeight    int Ball Height   0 80f     int ballWidth    int Ball Width   0 80f     int x   Ball X - ballWidth   2     int y   Ball Y - ballHeight   2      return new Rectangle x y ballHeight ballWidth       Then  in your loop      Checks every ball against every other ball      For best results  split it into quadrants like Ryan suggested      I didn t do that for simplicity here  for  int i   0  i  lt  balls count  i          Rectangle r1   balls i  getBoundingRect         for  int k   0  k  lt  balls count  k                   if  balls i     balls k                         Rectangle r2   balls k  getBoundingRect                 if  r1 Intersects r2                                     balls i  collided with balls k

User · Answer

As a clarification to the suggestion by Ryan Fox to split the screen into regions, and only checking for collisions within regions...

e.g. split the play area up into a grid of squares (which will will arbitrarily say are of 1 unit length per side), and check for collisions within each grid square.

That's absolutely the correct solution. The only problem with it (as another poster pointed out) is that collisions across boundaries are a problem.

The solution to this is to overlay a second grid at a 0.5 unit vertical and horizontal offset to the first one.

Then, any collisions that would be across boundaries in the first grid (and hence not detected) will be within grid squares in the second grid. As long as you keep track of the collisions you've already handled (as there is likely to be some overlap) you don't have to worry about handling edge cases. All collisions will be within a grid square on one of the grids.

User · Answer

One thing I see here to optimize   While I do agree that the balls hit when the distance is the sum of their radii one should never actually calculate this distance   Rather  calculate it s square and work with it that way   There s no reason for that expensive square root operation   Also  once you have found a collision you have to continue to evaluate collisions until no more remain   The problem is that the first one might cause others that have to be resolved before you get an accurate picture   Consider what happens if the ball hits a ball at the edge   The second ball hits the edge and immediately rebounds into the first ball   If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle   As for the O n 2   all you can do is minimize the cost of rejecting ones that miss   1   A ball that is not moving can t hit anything   If there are a reasonable number of balls lying around on the floor this could save a lot of tests    Note that you must still check if something hit the stationary ball    2   Something that might be worth doing   Divide the screen into a number of zones but the lines should be fuzzy--balls at the edge of a zone are listed as being in all the relevant  could be 4  zones   I would use a 4x4 grid  store the zones as bits   If an AND of the zones of two balls zones returns zero  end of test   3   As I mentioned  don t do the square root

User · Answer

I found an excellent page with information on collision detection and response in 2D  http   www metanetsoftware com technique html  web archive org  They try to explain how it s done from an academic point of view  They start with the simple object-to-object collision detection  and move on to collision response and how to scale it up  Edit  Updated link

User · Answer

To detect whether two balls collide  just check whether the distance between their centers is less than two times the radius  To do a perfectly elastic collision between the balls  you only need to worry about the component of the velocity that is in the direction of the collision  The other component  tangent to the collision  will stay the same for both balls  You can get the collision components by creating a unit vector pointing in the direction from one ball to the other  then taking the dot product with the velocity vectors of the balls  You can then plug these components into a 1D perfectly elastic collision equation    Wikipedia has a pretty good summary of the whole process  For balls of any mass  the new velocities can be calculated using the equations  where v1 and v2 are the velocities after the collision  and u1  u2 are from before          If the balls have the same mass then the velocities are simply switched  Here s some code I wrote which does something similar   void Simulation  collide Storage  Iterator a  Storage  Iterator b           Check whether there actually was a collision     if  a    b          return       Vector collision   a position   - b position        double distance   collision length        if  distance    0 0                    hack to avoid div by zero         collision   Vector 1 0  0 0           distance   1 0            if  distance  gt  1 0          return          Get the components of the velocity vectors which are parallel to the collision         The perpendicular component remains the same for both fish     collision   collision   distance      double aci   a velocity   dot collision       double bci   b velocity   dot collision           Solve for the new velocities using the 1-dimensional elastic collision equations         Turns out it s really simple when the masses are the same      double acf   bci      double bcf   aci          Replace the collision velocity components with the new ones     a velocity       acf - aci    collision      b velocity       bcf - bci    collision      As for efficiency  Ryan Fox is right  you should consider dividing up the region into sections  then doing collision detection within each section  Keep in mind that balls can collide with other balls on the boundaries of a section  so this may make your code much more complicated  Efficiency probably won t matter until you have several hundred balls though  For bonus points  you can run each section on a different core  or split up the processing of collisions within each section

User · Answer

One thing I see here to optimize   While I do agree that the balls hit when the distance is the sum of their radii one should never actually calculate this distance   Rather  calculate it s square and work with it that way   There s no reason for that expensive square root operation   Also  once you have found a collision you have to continue to evaluate collisions until no more remain   The problem is that the first one might cause others that have to be resolved before you get an accurate picture   Consider what happens if the ball hits a ball at the edge   The second ball hits the edge and immediately rebounds into the first ball   If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle   As for the O n 2   all you can do is minimize the cost of rejecting ones that miss   1   A ball that is not moving can t hit anything   If there are a reasonable number of balls lying around on the floor this could save a lot of tests    Note that you must still check if something hit the stationary ball    2   Something that might be worth doing   Divide the screen into a number of zones but the lines should be fuzzy--balls at the edge of a zone are listed as being in all the relevant  could be 4  zones   I would use a 4x4 grid  store the zones as bits   If an AND of the zones of two balls zones returns zero  end of test   3   As I mentioned  don t do the square root

User · Answer

I found an excellent page with information on collision detection and response in 2D  http   www metanetsoftware com technique html  web archive org  They try to explain how it s done from an academic point of view  They start with the simple object-to-object collision detection  and move on to collision response and how to scale it up  Edit  Updated link

User · Answer

As a clarification to the suggestion by Ryan Fox to split the screen into regions, and only checking for collisions within regions...

e.g. split the play area up into a grid of squares (which will will arbitrarily say are of 1 unit length per side), and check for collisions within each grid square.

That's absolutely the correct solution. The only problem with it (as another poster pointed out) is that collisions across boundaries are a problem.

The solution to this is to overlay a second grid at a 0.5 unit vertical and horizontal offset to the first one.

Then, any collisions that would be across boundaries in the first grid (and hence not detected) will be within grid squares in the second grid. As long as you keep track of the collisions you've already handled (as there is likely to be some overlap) you don't have to worry about handling edge cases. All collisions will be within a grid square on one of the grids.

User · Answer

You should use space partitioning to solve this problem    Read up on  Binary Space Partitioning and Quadtrees

User · Answer

You should use space partitioning to solve this problem    Read up on  Binary Space Partitioning and Quadtrees

User · Answer

One thing I see here to optimize   While I do agree that the balls hit when the distance is the sum of their radii one should never actually calculate this distance   Rather  calculate it s square and work with it that way   There s no reason for that expensive square root operation   Also  once you have found a collision you have to continue to evaluate collisions until no more remain   The problem is that the first one might cause others that have to be resolved before you get an accurate picture   Consider what happens if the ball hits a ball at the edge   The second ball hits the edge and immediately rebounds into the first ball   If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle   As for the O n 2   all you can do is minimize the cost of rejecting ones that miss   1   A ball that is not moving can t hit anything   If there are a reasonable number of balls lying around on the floor this could save a lot of tests    Note that you must still check if something hit the stationary ball    2   Something that might be worth doing   Divide the screen into a number of zones but the lines should be fuzzy--balls at the edge of a zone are listed as being in all the relevant  could be 4  zones   I would use a 4x4 grid  store the zones as bits   If an AND of the zones of two balls zones returns zero  end of test   3   As I mentioned  don t do the square root

User · Answer

You should use space partitioning to solve this problem    Read up on  Binary Space Partitioning and Quadtrees

User · Answer

Well  years ago I made the program like you presented here  There is one hidden problem  or many  depends on point of view       If the speed of the ball is too high  you can miss the collision    And also  almost in 100  cases your new speeds will be wrong  Well  not speeds  but positions  You have to calculate new speeds precisely in the correct place  Otherwise you just shift balls on some small  error  amount  which is available from the previous discrete step   The solution is obvious  you have to split the timestep so  that first you shift to correct place  then collide  then shift for the rest of the time you have

User · Answer

This KineticModel is an implementation of the cited approach in Java

User · Answer

A good way of reducing the number of collision checks is to split the screen into different sections  You then only compare each ball to the balls in the same section

User · Answer

After some trial and error  I used this document s method for 2D collisions   https   www vobarian com collisions 2dcollisions2 pdf  that OP linked to  I applied this within a JavaScript program using p5js  and it works perfectly  I had previously attempted to use trigonometrical equations and while they do work for specific collisions  I could not find one that worked for every collision no matter the angle at the which it happened  The method explained in this document uses no trigonometrical functions whatsoever  it s just plain vector operations  I recommend this to anyone trying to implement ball to ball collision  trigonometrical functions in my experience are hard to generalize  I asked a Physicist at my university to show me how to do it and he told me not to bother with trigonometrical functions and showed me a method that is analogous to the one linked in the document  NB   My masses are all equal  but this can be generalised to different masses using the equations presented in the document  Here s my code for calculating the resulting speed vectors after collision         you just need a ball object with a speed and position vector      class TBall           constructor x  y  vx  vy                this r    x  y               this v    0  0                          throw two balls into this function and it ll update their speed vectors       if they collide  you need to call this in your main loop for every pair of        balls      function collision ball1  ball2            n      ball1 r  0  -  ball2 r  0    ball1 r  1  -  ball2 r  1             un    n 0     vecNorm n   n 1    vecNorm n              ut     -un 1   un 0                v1n   dotProd un   ball1 v            v1t   dotProd ut   ball1 v             v2n   dotProd un   ball2 v             v2t   dotProd ut   ball2 v             v1t p   v1t  v2t p   v2t          v1n p   v2n  v2n p   v1n          v1n pvec    v1n p   un 0   v1n p   un 1              v1t pvec    v1t p   ut 0   v1t p   ut 1              v2n pvec    v2n p   un 0   v2n p   un 1              v2t pvec    v2t p   ut 0   v2t p   ut 1             ball1 v   vecSum v1n pvec  v1t pvec   ball2 v   vecSum v2n pvec  v2t pvec

User · Answer

You should use space partitioning to solve this problem    Read up on  Binary Space Partitioning and Quadtrees

User · Answer

After some trial and error  I used this document s method for 2D collisions   https   www vobarian com collisions 2dcollisions2 pdf  that OP linked to  I applied this within a JavaScript program using p5js  and it works perfectly  I had previously attempted to use trigonometrical equations and while they do work for specific collisions  I could not find one that worked for every collision no matter the angle at the which it happened  The method explained in this document uses no trigonometrical functions whatsoever  it s just plain vector operations  I recommend this to anyone trying to implement ball to ball collision  trigonometrical functions in my experience are hard to generalize  I asked a Physicist at my university to show me how to do it and he told me not to bother with trigonometrical functions and showed me a method that is analogous to the one linked in the document  NB   My masses are all equal  but this can be generalised to different masses using the equations presented in the document  Here s my code for calculating the resulting speed vectors after collision         you just need a ball object with a speed and position vector      class TBall           constructor x  y  vx  vy                this r    x  y               this v    0  0                          throw two balls into this function and it ll update their speed vectors       if they collide  you need to call this in your main loop for every pair of        balls      function collision ball1  ball2            n      ball1 r  0  -  ball2 r  0    ball1 r  1  -  ball2 r  1             un    n 0     vecNorm n   n 1    vecNorm n              ut     -un 1   un 0                v1n   dotProd un   ball1 v            v1t   dotProd ut   ball1 v             v2n   dotProd un   ball2 v             v2t   dotProd ut   ball2 v             v1t p   v1t  v2t p   v2t          v1n p   v2n  v2n p   v1n          v1n pvec    v1n p   un 0   v1n p   un 1              v1t pvec    v1t p   ut 0   v1t p   ut 1              v2n pvec    v2n p   un 0   v2n p   un 1              v2t pvec    v2t p   ut 0   v2t p   ut 1             ball1 v   vecSum v1n pvec  v1t pvec   ball2 v   vecSum v2n pvec  v2t pvec

User · Answer

You have two easy ways to do this  Jay has covered the accurate way of checking from the center of the ball   The easier way is to use a rectangle bounding box  set the size of your box to be 80  the size of the ball  and you ll simulate collision pretty well   Add a method to your ball class   public Rectangle getBoundingRect        int ballHeight    int Ball Height   0 80f     int ballWidth    int Ball Width   0 80f     int x   Ball X - ballWidth   2     int y   Ball Y - ballHeight   2      return new Rectangle x y ballHeight ballWidth       Then  in your loop      Checks every ball against every other ball      For best results  split it into quadrants like Ryan suggested      I didn t do that for simplicity here  for  int i   0  i  lt  balls count  i          Rectangle r1   balls i  getBoundingRect         for  int k   0  k  lt  balls count  k                   if  balls i     balls k                         Rectangle r2   balls k  getBoundingRect                 if  r1 Intersects r2                                     balls i  collided with balls k

User · Answer

I see it hinted here and there  but you could also do a faster calculation first  like  compare the bounding boxes for overlap  and THEN do a radius-based overlap if that first test passes     The addition difference math is much faster for a bounding box than all the trig for the radius  and most times  the bounding box test will dismiss the possibility of a collision   But if you then re-test with trig  you re getting the accurate results that you re seeking     Yes  it s two tests  but it will be faster overall

User · Answer

I would consider using a quadtree if you have a large number of balls  For deciding the direction of bounce  just use simple conservation of energy formulas based on the collision normal   Elasticity  weight  and velocity would make it a bit more realistic

User · Answer

I would consider using a quadtree if you have a large number of balls  For deciding the direction of bounce  just use simple conservation of energy formulas based on the collision normal   Elasticity  weight  and velocity would make it a bit more realistic

User · Answer

Well  years ago I made the program like you presented here  There is one hidden problem  or many  depends on point of view       If the speed of the ball is too high  you can miss the collision    And also  almost in 100  cases your new speeds will be wrong  Well  not speeds  but positions  You have to calculate new speeds precisely in the correct place  Otherwise you just shift balls on some small  error  amount  which is available from the previous discrete step   The solution is obvious  you have to split the timestep so  that first you shift to correct place  then collide  then shift for the rest of the time you have

User · Answer

To detect whether two balls collide  just check whether the distance between their centers is less than two times the radius  To do a perfectly elastic collision between the balls  you only need to worry about the component of the velocity that is in the direction of the collision  The other component  tangent to the collision  will stay the same for both balls  You can get the collision components by creating a unit vector pointing in the direction from one ball to the other  then taking the dot product with the velocity vectors of the balls  You can then plug these components into a 1D perfectly elastic collision equation    Wikipedia has a pretty good summary of the whole process  For balls of any mass  the new velocities can be calculated using the equations  where v1 and v2 are the velocities after the collision  and u1  u2 are from before          If the balls have the same mass then the velocities are simply switched  Here s some code I wrote which does something similar   void Simulation  collide Storage  Iterator a  Storage  Iterator b           Check whether there actually was a collision     if  a    b          return       Vector collision   a position   - b position        double distance   collision length        if  distance    0 0                    hack to avoid div by zero         collision   Vector 1 0  0 0           distance   1 0            if  distance  gt  1 0          return          Get the components of the velocity vectors which are parallel to the collision         The perpendicular component remains the same for both fish     collision   collision   distance      double aci   a velocity   dot collision       double bci   b velocity   dot collision           Solve for the new velocities using the 1-dimensional elastic collision equations         Turns out it s really simple when the masses are the same      double acf   bci      double bcf   aci          Replace the collision velocity components with the new ones     a velocity       acf - aci    collision      b velocity       bcf - bci    collision      As for efficiency  Ryan Fox is right  you should consider dividing up the region into sections  then doing collision detection within each section  Keep in mind that balls can collide with other balls on the boundaries of a section  so this may make your code much more complicated  Efficiency probably won t matter until you have several hundred balls though  For bonus points  you can run each section on a different core  or split up the processing of collisions within each section

User · Answer

A good way of reducing the number of collision checks is to split the screen into different sections  You then only compare each ball to the balls in the same section

User · Answer

You have two easy ways to do this  Jay has covered the accurate way of checking from the center of the ball   The easier way is to use a rectangle bounding box  set the size of your box to be 80  the size of the ball  and you ll simulate collision pretty well   Add a method to your ball class   public Rectangle getBoundingRect        int ballHeight    int Ball Height   0 80f     int ballWidth    int Ball Width   0 80f     int x   Ball X - ballWidth   2     int y   Ball Y - ballHeight   2      return new Rectangle x y ballHeight ballWidth       Then  in your loop      Checks every ball against every other ball      For best results  split it into quadrants like Ryan suggested      I didn t do that for simplicity here  for  int i   0  i  lt  balls count  i          Rectangle r1   balls i  getBoundingRect         for  int k   0  k  lt  balls count  k                   if  balls i     balls k                         Rectangle r2   balls k  getBoundingRect                 if  r1 Intersects r2                                     balls i  collided with balls k

User · Answer

A good way of reducing the number of collision checks is to split the screen into different sections  You then only compare each ball to the balls in the same section

User · Answer

To detect whether two balls collide  just check whether the distance between their centers is less than two times the radius  To do a perfectly elastic collision between the balls  you only need to worry about the component of the velocity that is in the direction of the collision  The other component  tangent to the collision  will stay the same for both balls  You can get the collision components by creating a unit vector pointing in the direction from one ball to the other  then taking the dot product with the velocity vectors of the balls  You can then plug these components into a 1D perfectly elastic collision equation    Wikipedia has a pretty good summary of the whole process  For balls of any mass  the new velocities can be calculated using the equations  where v1 and v2 are the velocities after the collision  and u1  u2 are from before          If the balls have the same mass then the velocities are simply switched  Here s some code I wrote which does something similar   void Simulation  collide Storage  Iterator a  Storage  Iterator b           Check whether there actually was a collision     if  a    b          return       Vector collision   a position   - b position        double distance   collision length        if  distance    0 0                    hack to avoid div by zero         collision   Vector 1 0  0 0           distance   1 0            if  distance  gt  1 0          return          Get the components of the velocity vectors which are parallel to the collision         The perpendicular component remains the same for both fish     collision   collision   distance      double aci   a velocity   dot collision       double bci   b velocity   dot collision           Solve for the new velocities using the 1-dimensional elastic collision equations         Turns out it s really simple when the masses are the same      double acf   bci      double bcf   aci          Replace the collision velocity components with the new ones     a velocity       acf - aci    collision      b velocity       bcf - bci    collision      As for efficiency  Ryan Fox is right  you should consider dividing up the region into sections  then doing collision detection within each section  Keep in mind that balls can collide with other balls on the boundaries of a section  so this may make your code much more complicated  Efficiency probably won t matter until you have several hundred balls though  For bonus points  you can run each section on a different core  or split up the processing of collisions within each section

User · Answer

Well  years ago I made the program like you presented here  There is one hidden problem  or many  depends on point of view       If the speed of the ball is too high  you can miss the collision    And also  almost in 100  cases your new speeds will be wrong  Well  not speeds  but positions  You have to calculate new speeds precisely in the correct place  Otherwise you just shift balls on some small  error  amount  which is available from the previous discrete step   The solution is obvious  you have to split the timestep so  that first you shift to correct place  then collide  then shift for the rest of the time you have

User · Answer

To detect whether two balls collide  just check whether the distance between their centers is less than two times the radius  To do a perfectly elastic collision between the balls  you only need to worry about the component of the velocity that is in the direction of the collision  The other component  tangent to the collision  will stay the same for both balls  You can get the collision components by creating a unit vector pointing in the direction from one ball to the other  then taking the dot product with the velocity vectors of the balls  You can then plug these components into a 1D perfectly elastic collision equation    Wikipedia has a pretty good summary of the whole process  For balls of any mass  the new velocities can be calculated using the equations  where v1 and v2 are the velocities after the collision  and u1  u2 are from before          If the balls have the same mass then the velocities are simply switched  Here s some code I wrote which does something similar   void Simulation  collide Storage  Iterator a  Storage  Iterator b           Check whether there actually was a collision     if  a    b          return       Vector collision   a position   - b position        double distance   collision length        if  distance    0 0                    hack to avoid div by zero         collision   Vector 1 0  0 0           distance   1 0            if  distance  gt  1 0          return          Get the components of the velocity vectors which are parallel to the collision         The perpendicular component remains the same for both fish     collision   collision   distance      double aci   a velocity   dot collision       double bci   b velocity   dot collision           Solve for the new velocities using the 1-dimensional elastic collision equations         Turns out it s really simple when the masses are the same      double acf   bci      double bcf   aci          Replace the collision velocity components with the new ones     a velocity       acf - aci    collision      b velocity       bcf - bci    collision      As for efficiency  Ryan Fox is right  you should consider dividing up the region into sections  then doing collision detection within each section  Keep in mind that balls can collide with other balls on the boundaries of a section  so this may make your code much more complicated  Efficiency probably won t matter until you have several hundred balls though  For bonus points  you can run each section on a different core  or split up the processing of collisions within each section

User · Answer

I implemented this code in JavaScript using the HTML Canvas element  and it produced wonderful simulations at 60 frames per second   I started the simulation off with a collection of a dozen balls at random positions and velocities   I found that at higher velocities  a glancing collision between a small ball and a much larger one caused the small ball to appear to STICK to the edge of the larger ball  and moved up to around 90 degrees around the larger ball before separating    I wonder if anyone else observed this behavior    Some logging of the calculations showed that the Minimum Translation Distance in these cases was not large enough to prevent the same balls from colliding in the very next time step   I did some experimenting and found that I could solve this problem by scaling up the MTD based on the relative velocities   dot velocity   ball 1 velocity dot ball 2 velocity   mtd factor   1    0 5   Math abs dot velocity   Math sin collision angle    mtd multplyScalar mtd factor     I verified that before and after this fix  the total kinetic energy was conserved for every collision   The 0 5 value in the mtd factor was the approximately the minumum value found to always cause the balls to separate after a collision   Although this fix introduces a small amount of error in the exact physics of the system  the tradeoff is that now very fast balls can be simulated in a browser without decreasing the time step size

User · Answer

One thing I see here to optimize   While I do agree that the balls hit when the distance is the sum of their radii one should never actually calculate this distance   Rather  calculate it s square and work with it that way   There s no reason for that expensive square root operation   Also  once you have found a collision you have to continue to evaluate collisions until no more remain   The problem is that the first one might cause others that have to be resolved before you get an accurate picture   Consider what happens if the ball hits a ball at the edge   The second ball hits the edge and immediately rebounds into the first ball   If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle   As for the O n 2   all you can do is minimize the cost of rejecting ones that miss   1   A ball that is not moving can t hit anything   If there are a reasonable number of balls lying around on the floor this could save a lot of tests    Note that you must still check if something hit the stationary ball    2   Something that might be worth doing   Divide the screen into a number of zones but the lines should be fuzzy--balls at the edge of a zone are listed as being in all the relevant  could be 4  zones   I would use a 4x4 grid  store the zones as bits   If an AND of the zones of two balls zones returns zero  end of test   3   As I mentioned  don t do the square root

User · Answer

As a clarification to the suggestion by Ryan Fox to split the screen into regions, and only checking for collisions within regions...

e.g. split the play area up into a grid of squares (which will will arbitrarily say are of 1 unit length per side), and check for collisions within each grid square.

That's absolutely the correct solution. The only problem with it (as another poster pointed out) is that collisions across boundaries are a problem.

The solution to this is to overlay a second grid at a 0.5 unit vertical and horizontal offset to the first one.

Then, any collisions that would be across boundaries in the first grid (and hence not detected) will be within grid squares in the second grid. As long as you keep track of the collisions you've already handled (as there is likely to be some overlap) you don't have to worry about handling edge cases. All collisions will be within a grid square on one of the grids.

User · Answer

I see it hinted here and there  but you could also do a faster calculation first  like  compare the bounding boxes for overlap  and THEN do a radius-based overlap if that first test passes     The addition difference math is much faster for a bounding box than all the trig for the radius  and most times  the bounding box test will dismiss the possibility of a collision   But if you then re-test with trig  you re getting the accurate results that you re seeking     Yes  it s two tests  but it will be faster overall

User · Answer

Improving the solution to detect circle with circle collision detection given within the question  float dx   circle1 x - circle2 x        dy   circle1 y - circle2 y         r   circle1 r   circle2 r  return  dx   dx   dy   dy  lt   r   r    It avoids the unnecessary  quot if with two returns quot  and the use of more variables than necessary

User · Answer

You have two easy ways to do this  Jay has covered the accurate way of checking from the center of the ball   The easier way is to use a rectangle bounding box  set the size of your box to be 80  the size of the ball  and you ll simulate collision pretty well   Add a method to your ball class   public Rectangle getBoundingRect        int ballHeight    int Ball Height   0 80f     int ballWidth    int Ball Width   0 80f     int x   Ball X - ballWidth   2     int y   Ball Y - ballHeight   2      return new Rectangle x y ballHeight ballWidth       Then  in your loop      Checks every ball against every other ball      For best results  split it into quadrants like Ryan suggested      I didn t do that for simplicity here  for  int i   0  i  lt  balls count  i          Rectangle r1   balls i  getBoundingRect         for  int k   0  k  lt  balls count  k                   if  balls i     balls k                         Rectangle r2   balls k  getBoundingRect                 if  r1 Intersects r2                                     balls i  collided with balls k

[graphics] Ball to Ball Collision - Detection and Handling

Examples related to graphics

Examples related to language-agnostic

Examples related to collision-detection

Examples related to physics