1[CODE
]
2Calculating a ricochet turns out to be a lot trickier problem than it
3first appears. For those of us who are a decade
or more away from our
4last practice with algebra
and trigonometry it requires some patience
5and perseverance.
6
7First we
're going to concentrate on the collision of two balls. Later
8we'll expand that to the collision of a ball against a wall. Our
9discussion will include mass
and elasticity. At the end we
'll discuss
10some of our ideas on how we might handle simultaneous collisions
11between multiple objects.
12
13First, two balls.
14
15There are six parts to the calculation, with a couple of subparts.
16
17 1) Gross collision detection
18 2) Calculate accurate positions at time of collision
19 3) Calculate the angle of collision vs the velocity vector
20 4) Calculate portion of velocity vector that applies to collision
21 5) Calculate final velocities along collision vector
22 6) Apply final velocities back to the object
23
24---------------------------------------------------------------------
25 1) Gross collision detection.
26
27The purpose of this step is to determine in as few instructions as
28possible whether the objects are close enough together to warrant more
29expensive calculations. There are many ways to accomplish this. The
30one we chose was the simple bounding box (See figures 1a through 1c).
31
32The quickest way to find out if two bounding boxes overlap is to test
33to see if the bounding boxes DON'T overlap. It only takes four tests
34to show that box A is to the right of, left of, above,
or below box B.
35
36// Use this macro in an if statement. Ex.
37// if (bounding_box_test(ibx, ibx1, iby, iby1, jbx, jbx1, jby, jby1))
38// DoSomething();
39// else
40// DoSomethingElse();
41#define bounding_box_test(ibx, ibx1, iby, iby1, jbx, jbx1, jby, jby1) \
42 (!((ibx > jbx1) || (ibx1 < jbx) || (iby > jby1) || (iby1 < jby)))
43
44You
'll need to extend the bounding boxes to include both the beginning
45and ending positions of each object. Otherwise, the objects could
46become overlapped before you detect a collision.
47
48---------------------------------------------------------------------
49 2) Calculate accurate positions at time of collision.
50
51The central trick for this step is the Quadratic equation.
52
53Let's take a moment to define our terms.
(See figure
2a)
54
55 Stuff we know:
56 x1,y1
and x2,y2
- The initial positions of the centers of the two objects
57 dx1,dy1
and dx2,dy2
- The distances the objects moved
this frame
58 r1, r2
- radii of the two objects
59
60 Stuff we calculate:
61 t
- Time of collision
62 cx1,cy1
and cx2,cy2
- The centers at
time of impact
63
64What we
're trying to find is when the centers of the two objects are
65the same distance apart as the sum of their radii. The distance
66formula is sqrt([cx1-cx2]^2 + [cy1-cy2]^2). Therefore, we're looking
67for the
time (t
) when
68 (r1
+r2
)=sqrt([cx1-cx2
]^
2 + [cy1-cy2
]^
2).
69
70How
do we know where will a ball be at any given
time (t
)? Here are
71functions which describe the paths of the centers of the balls over
72time:
73
74 cx1
= x1
+ tdx1 cx2
= x2
+ tdx2
75 cy1
= y1
+ tdy1 cy2
= y2
+ tdy2
76
77The t
's relate all the forumlas to each other. Replacing the cx's
and
78cy
's in the distance forumla with these equations and we end up with:
79
80 r1+r2 = sqrt(((x2 + tdx2)-(x1 + tdx1))^2 + ((y2 + tdy2)-(y1 + tdy1))^2)
81
82Multiply everything out then rearrange and simplify and you end up
83with:
84
85 0 = [(dx2-dx1)^2 + (dy2-dy1)^2] t^2
86 + [2(x2-x1)(dx2-dx1) + 2(y2-y1)(dy2-dy1)] t
87 + [(x2-x1)^2 + (y2-y1)^2 - (r1+r2)^2]
88
89This is a polynomial in the form 0=ax^2+bx+c. We can use the Quadratic
90equation (-b(+|-)sqrt(b^2-4ac))/2a to solve for the variable. The a, b
91and c are all spelled out above. You could plug a, b and c into that
92monster equation, but it turns out you want to calculate it in pieces.
93
94The Quadratic equation will give two answers, call them t1 and t2. One
95for each the plus and minus of the square root portion. There are some
96special cases to check before solving the equation, and some special
97cases that result from the equation. (See figure 2, cases 1-6)
98
99 1) If a=0 the equation goes infinite. Notice that "a" consists of the
100 square of the difference between the direction vectors.
101 Therefore, a=0 if and only if the balls are moving the same
102 direction and the same speed.
103
104 2) If 4ac > b^2 then you end up trying to take the square root of a
105 negative number. In other words, there's no solution. It turns
106 out that
this happens
if and only
if the balls never pass within
107 r1
+r2 of each other. Even though the paths may cross, the balls
108 are far enough apart in
time that they don
't approach close
109 enough to each other to ever actually touch.
110
111 3) If both t's are negative then the balls are receding from each
112 other.
113
114 4) If one t is negative
and the other t is positive then the balls
115 began the frame already overlapped.
116
117 5) If both t
's are positive then the smaller of the two is when they
118 first reach r1+r2 from each other.
119
120 6) If both t's are greater than
1.
0 then the balls
do not collide
121 this frame.
122
123Condition
5 is the only valid collision
and you
continue with the
rest
124of the calculations.
125
126Conditions
1,
2,
3 and 6 indicate that there is
not a valid collision
127this frame
and you therefore can
abort before performing the
rest of
128the calculations. In effect, you discard
this pair of objects since a
129collision didn
't take place.
130
131Ideally, condition 4 should not occur. Whether or not it does occur
132depends on whether or not you handle multiple collisions in one frame.
133If you don't test
for condition
4 then the
rest of the math works out
134that the balls will remain locked together
"arm-in-arm" so to speak.
135
136---------------------------------------------------------------------
137 3) Calculate the angle of collision vs the velocity vector
138
139In order to calculate the momentum transfer later on we need to perform
140the remainder of these steps on both objects.
141
142At first glance it appears that you simply take the angle between the
143paths of the balls. That doesn
't work. Let's take the example of two
144balls headed in the same direction
and one ball is catching up on the
145other. If their centers lie on the same
line then it
's a simple 1D
146collision. But if the center of one ball is offset a little to one
147side then the momentum transfer occurs at an angle even though the
148motion paths are parallel. (See figures 3a and 3b)
149
150What we need to find is the angle formed by the velocity vector and the
151line connecting the centers. We need this angle in order to calculate
152how much of the velocity vector to apply to the collision. In other
153words, if the balls hit head-on, as in figure 3a, then the entire
154velocity vector is applied to the collision. If the balls just nick
155each other, as in figure 3b, then less momentum is transfered between
156the balls.
157
158The mathmatical tool for this problem is the Law of Cosines.
159 a^2 = b^2 + c^2 - 2bc cos(A).
160As written, it's intended
for finding the length of a side when an
161angle is known, but we can flip it around:
162 cos(A
) = ( a^
2 - b^
2 - c^
2 ) / (-2bc)
163
164 Thus the angle is: A
= acos( ( a^
2 - b^
2 - c^
2 ) / (-2bc) )
165
166Note that we can
't use "simple" trig since we're
not guaranteed of
167having a right angle.
(See figure
3c and 3d) This way you won
't have
168to transform coords to some artificial origin.
169
170(-2bc) approaches 0 if and only if the radii of both objects approach
1710. That's a pretty obvious should-not-occur situation.
172
173---------------------------------------------------------------------
174 4) Calculate portion of velocity vector that applies to collision
175
176Once we have angle A
this part turns out to be trivial. The piece of
177the total velocity vector that points toward Ball
2 is:
178 vi
=cos(A
)*sqrt(dx1^
2+dy1^
2)
179
180One obvious optimization is to save
and use
cos(A
) above, rather than
181find A only to immediately take its
cos() again.
182
183---------------------------------------------------------------------
184 5) Calculate final velocities along collision vector
185
186At
this point we can treat the
this as a
1D collision along the
line
187connecting the centers. You can find the momentum transfer equations
188in most first-year college physics texts.
189
190 vf1
=(((m1-m2
)*vi1
)+(((1.
0+(e1
*e2
))*m2
)*vi2
))/(m1
+m2
);
191 vf2
=((((1.
0+(e1
*e2
))*m1
)*vi1
)+((m2-m1
)*vi2
))/(m1
+m2
);
192
193Where: vf1, vf2
- final velocities along collision vector
194 vi1, vi2
- initial velocities along collision vector
195 m1, m2
- mass of each ball
196 e1, e2
- elasticity of each ball
197
198---------------------------------------------------------------------
199 6) Apply final velocities back to the object
200
201Now we need to subtract the off old velocity vector
and add on the
new
202one. That will leave us with an object that
's moving at the new,
203adjusted speed after ricochet.
204
205 angle=atan2(dcy,dcx); // angle of the line connecting the centers
206 sina=sin(angle); cosa=cos(angle);
207 odx=cosa*vi; // subtract off old velocity vector
208 ody=sina*vi;
209 ndx=cosa*vf1; // add on new velocity vector
210 ndy=sina*vf1;
211 dx+=odx-ndx; // signs look reversed but are correct
212 dy+=ody-ndy;
213
214---------------------------------------------------------------------
215 So, that's a ricochet
216
217So, that
's how you ricochet two balls. Whew! It seems like a lot of
218work, but there's no magic involved. Just
break the problem into
219pieces
and use the appropriate tool
for each piece.
220
221We haven
't discussed optimizations, yet. It turns out, collisions
222happen rarely enough that even using floating point and transcendental
223functions like sin and cos don't slow things down noticable. For
224example, an Asteroids clone with
30-40 rocks bouncing around spends
225almost all its
time blting the sprites to the screen. The
time to
226calculate ricochets is completely swamped. Still,
for maximum speed
227you
'll want to use a fixed-point representation and lookup tables for
228the transcendentals.
229
230But my advice is to live with floats while you build your prototype.
231The first rule of optimization: Make it right before you make it faster.
232
233Our implementation uses a dx, dy method to move the balls. An
234angle/norm implementation would perform the same work, it's just
235arranged a little different. See CBENCH.ZIP
for a dx
/dy implementation
236by David Bollinger
and CAROM.ZIP
for an angle
/norm implementation by
237Csaba Markus.
238
239---------------------------------------------------------------------
240 Wall collisions
241
242At the
time of
this writing, we haven
't completed the implementation of
243wall collisions.
244
245Our first pass implies that the trick to finding the collision point is
246to calculate a "shadow wall" one radius distance to each side of the
247wall. Then, simply find the intersection of the path of the center of
248the ball with each shadow wall (see figure 4a). Find which is closer to
249the original location of the ball.
250
251That gives you a possible collision. Next, you need to decide if the
252ball actually hit the wall face, or if it passed beyond the end of the
253wall and possibly hit the endpoint.
254
255To find if the ball hit a wall face, find the distance from the center
256of the ball to each endpoint of the shadow wall. If either distance is
257greater that the distance from one endpoint to the other then the
258center missed the wall face.
259
260To find if the ball hit the endpoint of a wall, treat the wall endpoint
261as an infinitely massive ball of zero size and go through the ball
262collision above (see figure 4b).
263
264---------------------------------------------------------------------
265 Simultaneous collisions
266
267Again, we haven't implemented
this yet. There are two likely
268candidates
for this.
269
270First, go through each pair of objects
and find the pair lowest
time of
271collision. Perform that collision
and then find the next lowest
time,
272taking into account the
new velocities of the objects.
273
274Or, sort the
times and step through them in that order. Resort all
275objects that are
close enough to be affected by each collision as they
276happen.
277
278---------------------------------------------------------------------
279 Wrapping it up
280
281I hope you found
this description useful. I realize it
's ended up a bit
282on the terse side. Hopefully the PCX files will help you visualize what
283I'm trying to describe. If anyone has questions, feedback, suggestions
or
284critique please feel
free to contact me, Drake Christensen
71251,
433.
285
286This file owes its existence to David Bollinger
72510,
3623. He
and I
287spent over a month brainstorming
this surprizingly obscure problem in the
288GAMDEV forum on Compuserve. His CBENCH example is available in GAMDEV.
289Obviously, any mistakes
or obfuscation in
this text are entirely my fault.
290
291Another who provided needed assistance is Csaba Markus
(E-mail:
292ethcms@duna.ericsson.se
). We found his CAROM simulator at just the right
293time to convince ourselves that we were heading down
(one of
) the right
294path.
295
296I can
't give a specific bibliography, but if you want to research this in
297texts, my suggestion is to visit a local college library and look for
298mechanics and physics texts circa 1910 or so. I was unable to find
299anything more recent than those. Apparently, the academic community
300doesn't consider
this an interesting subject anymore.
:-)
301
302Related files:
303 CBENCH.ZIP
- Collision test bench by David Bollinger
72510,
3623
304 CAROM.ZIP
- Carom simulator by Csaba Markus ethcms@duna.ericsson.se
305 CLDTHD.ZIP
- Thread on collision physics by
(mostly
) David Bollinger
306 and Drake Christensen
I'm too lazy to edit the photo. 
