Collision System

Introduction

This is a quick attempt to explain the collision system used in "passe trappe".
In this game, there are 2 types of entity: moving circle and static boxes.
There are 2 types of collision test used: sweep test (used for moving objects) and static test.

Sweep Test 1: Circle against circle

Intersection : The goal is to know where 2 moving circles hit each other during a frame. The centers of the circles are moving linearly. Their final point at t=1 is c_end = c_ini + V where V is the speed vector or moved vector during the frame.
If there is an intersection, the distance between the 2 circles is less than the sum of the radius. d < rb + rr.
Where d = cb - cr. cb is the center of the black circle, and cr is the center of the red one.
But this is also true for the sqare, so  d² < (rb + rr)². and so (cb - cr)² < (rb + rr)². The intersection happens when (cb - cr)² = (rb + rr)²
At each time we can know the position of the center of each circle: cb_t = cb_ini + Vb.tb where tb goes from 0 to 1.
This is also true for the red circle. cr_t = cr_ini + Vr * tr
If there is an intersection, the 2 times tr and tb are equals. So let t be tr and tb.
Replacing the position at each time in the intersection equation gives:
(cb_ini + Vb * t - cr_ini - Vr * t)² = (rb + rr)²
This give us a quadratic equation:
a * t² + b * t + c = 0
where
a = (Vb - Vr)²
b = 2 * (Vb - Vr) . (cb_ini - cr_ini)
c = (cb_ini - cr_ini)² - (rb + rr)²

The well known solution of this equation is
delta = b² - 4ac
If delta is equal to 0, only one solution in -b/(2a)
If delta is greater than 0, there are 2 solutions in (-b + sqrt(delta)) / (2a) and (-b - sqrt(delta)) / (2a).
If there are 2 solutions, we have to get the one that minimize the time.

Reaction : The goal is to move the circles where they should be assuming there is time left after collision event time. On the circle, the tangent is always from the center of the circle. So examining what happens at this point. To calculate the reaction we have first to change from the normal basis to the KJ one.
VbK is Vb projected on K and VbK2 is the unknown resultant vector
Then we use the movement conservation : mb*VbK + mr*VrK = mb*VbK2 + mr*.VrK2
and the kinetic energy (mV/2) conservation : mb*VbK²/2 + mr*VrK²/2 = mb*VbK2²/2 + mr*VrK2²/2
So we have a system with 2 unkown data
Solving these equations gives:
VbK2 = ( (mb - mr) / (mb + mr) ) * VbK + ( 2 * mr / ( mb + mr ) ) * VrK
VrK2 = ( 2 * mb / ( mb + mr ) ) * VbK + ( (mr - mb) / (mb + mr) ) * VrK
If the masses are equals, we have VbK2 = VrK and VrK2 = VbK. This is true only for the K axis in the KJ basis.
After that we just have to revert the basis change from the KJ basis to the normal one.

From normal to KJ: (for black velocitie)
VbK = Vbx * Kx + Vby * Ky  with (Kx, Ky) the coordinates of K in the normal basis.
VbJ = Vby * Kx - Vbvx * Ky
with K = (cr - cb) / distance(cr, cb)
and distance(cr, cb) = sqrt( (crx - cbx)² + (cry - cby)² )

From KJ to normal:
Vbx = VbK * Kx - VbJ * Ky
Vby = VbK * Kx + VbJ * Ky

Sweep Test2: Circle against Boxes

Intersection : The goal is to know where (and when) the moving circle hit the box (axis aligned) during a frame.
The time is normalized from 0 to 1. The intersection test is divided in 2: planes case and corners case.
Plane case: All rely on segment / segment test. We made an approximation of the circle with 4 lines (from the initial to the final circle).
For the 4 types of approach (the signs of the speed vector components), we have 4 tests case.
The following image summarize them. The intersection of the red lines are checked, and the same is done for all other cases.
If the circle is moving up we have to test with the bottom line of the axis aligned box.
If the circle is moving to the right we have to test with the left side of the box.
etc...

Segment against segment intersection
The 2 segments are S1 and S2. The 2 points of each segments are P1(x1,y1) and P2(x2,y2)
The line equation is Pt = P1 + (P2-P1)t. This is true for the 2 segments. The intersection is where the 2 lines are "equals".
S1.P1 + (S1.P2 - S1.P1) * res1 = S2.P1 + (S2.P2 - S2.P1) * res2
We can solve this equation for the 2 components x and y.
d  = (S1.x2 - S1.x1) * (S2.y2 - S2.y1) - (S1.y2 - S1.y1) * (S2.x2 - S2.x1)
If d is not equal to zero so the line intersection is:
res1 = ((S1.y1 - S2.y1) * (S2.x2 - S2.x1) - (S1.x1 - S2.x1) * (S2.y2 - S2.y1) ) / d
The intersection is at res1 * (S1.x2 - S1.x1) + S1.x1 for the x coordinate and res1 * (S1.y2 - S1.y1) + S1.y1 for the y coordinate.
If res1 is between 0 and 1 there is a segment intersection (the line S2 cross the segment S1).
We have to do the same for the segment S2.
res2 = ( (S1.y1 - S2.y1) * (S1.x2 - S1.x1) - (S1.x1 - S2.x1) * (S1.y2 - S1.y1) ) / d
So if res1 and res2 are between 0 and 1. The segment S1 intersect the segment S2.

With those tests, we can miss some corner intersection. To check this we change the basis. We work on the basis made with the origin at the center of the circle and we move the corner with the circle made static.
We check that the line described by the corner at the beginning and at the end of the frame, intersect or not the circle.

Segment against circle intersection
Line equation P = P1 + V * t
Circle equation (P - c)² = r²
Here P1 is the corner, V is the speed vector of the circle, c is the center of the circle and r its radius.
Replacing the P in the second equation give us : (P1 + V * t - c)² = r² or
V² * t² + 2 * (P1 - c) . V * t + (P1 - c)² - r² = 0 a well known quadratic form
a * t² + b * t + c = 0
where
a = V²
b = 2 * (P1 - c) . V
c = (P1 - c)² - r²
The well known solution of this equation is
delta = b² - 4ac
If delta is equal to 0, only one solution in -b/(2a). This mean only one intersection between the line and the circle.
If delta is greater than 0, there are 2 solutions in (-b + sqrt(delta)) / (2a) and (-b - sqrt(delta)) / (2a).. This mean 2 intersections betweenline and the circle.
But we are not dealing with a line but a segment. So the solutions must be between 0 and 1 to be valid solutions.

Reaction: The goal is to move the circle where it  should be assuming there is time left after collision event time.
By now we have found the intersection between the circle and the box at a specific date in a normalized time (between 0 and 1).
The reaction of the circle is to change its speed vector relatively to the normal of the surface encountered. If V is the speed vector and N the normal, so the new speed vector is V - 2 * N * (N.V). (Vector reflection equation)

Static Test 1: Circle against circle

Because there are a lot of object, sometimes it is good to start a frame without any intersection.
Even if the sweep test works well for moving object, it can happens that the time left is near zero and so all collisions cannot be solved.
Static test is here when the circles nearly don't move.
When 2 circles overlaps ? When distance(c1, c2) < r1+r2. And this is also true for the square.distance(c1, c2) = sqrt( (c1x - c2x)² + (c1y - c2y)² ).
With (c1x - c2x)² + (c1y - c2y)² < (r1+r2)² , we can avoid a costly square root.

What to do if there is an intersection ? We expulse the 2 circles relatively to their centers.

Static Test 2 : Circle against box

We test the circle center against each side of the box, which is a simple range test.
If the center is not inside, we check with the corners which is a simple distance from 2 points test.

Conclusion

We have presented with simple math the way of doing a simple collision system: circles against circles and some static geometry.
We can note that for not axis aligned box, we can make a basis change.

Back to matthPage