2d collision response between circles

I'm trying to calculate new velocities for 2 colliding balls, but can't really do that before I solve another problem.

Since in digital world a real collision almost never happens, we will always have a situation where the "colliding" balls overlap.

Imagine there is a 100 balls moving randomly so, if I understand it correctly, the procedure should be as follows:

• Move the balls (x += vx;开发者_运维问答 y+= vy;)
• Get the lest overlapping (or perfectly colliding) balls
• Move the balls "back in time" to that moment
• Perform collision calculations

If the above is correct, then, how could I move the balls "back in time" to the point of first collision? Known data:

• All coordinates of the balls (b[i].x, b[i].y)
• Ball X and Y velocities (b[i].vx, b[i].vy)
• Distance between lest overlapping balls (dist)

Should I just calculate how many percent the dist is of the perfect distance to the collision and then simply move back x and y coordinates by the same amount of percent of vx and vy?

For collisions like these, it's usually easiest to look at it from the reference frame of one of the balls.

Let's say you have ball1 and ball2. These balls have positions p1 and p2 respectively, and velocities v1 and v2. Let the relative velocity of ball1 with respect to ball2 be v1-v2=v.

We want to know when ||p1-p2|| is less than ||r1||+||r2||, where r1 is the vector with a length of the radius of the first ball in the direction towards the second ball, and r2 is vice-versa.

From ball2's perspective, ball1 is moving with velocity v1+v2. At time t, ball2 is at position p2+(v1+v2)*t.

The balls collide when:

(p1-(p2+vt)) = (r1+r2)
-(p2+vt) = (r1+r2)-p1
-p2-vt = (r1+r2)-p1
-vt = (r1+r2)-p1+p2
vt = (p1-p2)-(r1+r2)

Now since ||a|| = ||b||+||c|| when a = b+c, we know that

||v||t = ||p1-p2|| - ||r1+r2||
t = (||p1-p2|| - ||r1+r2||)/||v||

For example: p1 = (7,5) and p2=(4,1), ||r1||=1 and ||r1||=2, and v1=(1,2) and v2=(-2,-2) then v=(3,4). The collision happens at:

t = (||(3,4)|| - 3)/||(3,4)||
t = (5-3)/(5) = 2/5 = 0.4

Now that you have the time of the collision, figuring out where the balls are is easy :-)

edit to put the vectormath into pseudocode:

p = p1-p2
v = v1-v2
t = (sqrt(p.x*p.x + p.y*p.y) - (r1+r2)) / sqrt(v.x*v.x + v.y*v.y)

Whether your strategy of move-then-collide makes sense depends on what kind of thing you are trying to simulate, and on the trade-off between accuracy and speed. If you are, say, writing a snooker simulator, or Super Monkey Ball, then move-then-collide is probably not good enough, for three reasons.

First, the balls will have the wrong velocities after collision. The differences will be subtle, but will feel wrong to players:

On the left, velocities at the end of a time-step when balls are allowed to intersect before collision is detected. On the right: velocities immediately after a collision at the correct time and place.

Second, objects moving fast enough may pass through each other without colliding. Or even if you detect the collision, you may eject the objects in the wrong way, causing some kind of illegal motion. (See tasvideos.org for a collection of collision bugs in the Super Mario Bros games that are caused by this move-then-eject strategy.)

Third, objects may end up intersecting at the end of your time step, with no room to move them apart (because other objects get in the way). So you end up having to draw the objects in intersecting position, which looks wrong.

In applications where these issues matter, then it's better to determine the point of collision before moving the balls. See this article of mine for a basic introduction to this collide-then-move approach.

Consider the case of one circle centered at the origin and stationary, and the other moving toward it in, say, the -x direction. (You can transform any collision case into this with some simple vector algebra.)

So the position of the center of the second circle is (x,y), where y is constant and x is decreasing. The collision occurs when x² + y² = (r₁ + r₂)², call that x_crit. But in the simulation we've gone past that, to some x < x_crit. So we have to rewind enough time to bring it back to x_crit, which we can calculate easily since we know x, x_crit and v.

EDIT: nevermind, my algorithm for finding the point of collision is incorrect. I'll think about this a bit more.

EDIT2: Ok, sorry about that. Try this:

1. Find out when they collided. Let's call this T seconds ago. This would be T such that the distance between the two balls is equal to the sum of their radii. The equation is ((x1 - v_x1*T)-(x2 - v_x2*T))^2 = r1 + r2
2. Move the balls back time T
3. Continue with the your collision

I'm sorry, I don't know how to format math equations on SO. :S

After going back to the time of collision, you can calculate their new velocities fairly easily using elementary physics. See http://en.wikipedia.org/wiki/Elastic_collision#Two-_and_three-dimensional