Hi, I''m in the process of writing my first game. An Arkanoid clone, yet I''m having some problems. I''ve learnt that a line segment can be used to time precisely when a collision occurs, newpos - oldpos = lineseg.. however, I''m not sure how to calculate the time.. how do i know what the target is? how do i work it out? at the moment, I''m using bounding boxes for all bricks.. and doing an intersection test for every brick against the ball every frame.. yet I''m having trouble detecting which side of the brick the collision occurs.. can anyone help? :-) Since my ball can be moving at any number of pixels, collision detection seems cumbersome.. ball gets stuck etc.. I''d be thrilled if someone had a solution for these simple problems!

A good question! The idea is that if you''re at position oldpos at time = oldtime, and you''re at position newpos at time = newtime, then maybe there''s a collision at some point between oldtime and newtime. The equation of the line can be used to find the time at which the collision occurs. The scenario works like this:

Given oldpos, newpos, old_time, and new_time, theposition of your moving object can be represented with this equation:

Equation 1: position = oldpos + (newpos - oldpos) * (time - oldtime) / (newtime - oldtime) 

If you plug in time = oldtime, you''ll find that position = oldpos, and if you plug in time = newtime, you''ll find that position = newtime. This is a parametric equation for the line. Points along the line are defined in terms of time.

Now, suppose you want to find the collision with a fixed wall. Well, the edge of the wall can also be represented by a line, say from point A to point B. The equation of this wall line cannot be represented as a parametric function of time, but it can be represented as a function of, say, x or y. Suppose your wall line is represented as a function of x:

Equation 2: wall_y = A.y + (wall_x - A.x) * slope

(alternate for a vertical line:

wall_x = A.x + (wall_y - A.y) * slope
<br><br>Here, slope = (B.y - A.y)/(B.x - A.y) for a non-vertical line or (B.x - A.x)/(B.y - A.y) for a vertical line<br>The point (wall_x, wall_y) is a point along the wall, as long as wall_x is between A.x and B.x and wall_y is between A.y and B.y.<br><br>Just plug The idea is to solve Equations 1 and 2 together to find the value of time where the path intersects the wall.<br><br>Do it this way. Break equation 1 into two parts (and let p = position, op = oldpos, ot = oldtime, etc.):<br><br>[code]<br>p.x = op.x + (np.x - op.x) * (t - ot) / (nt - ot)<br>p.y = op.y + (np.y - op.y) * (t - ot) / (nt - ot)<br> </pre> <br><br>And just plug that into equation 2. Let wall_x = p.x and wall_y = p.y:<br><br><pre><br>op.y + (np.y - op.y) * (t - ot) / (nt - ot) = A.y +<br>(op.x + (np.x - op.x) * (t - ot) / (nt - ot) - A.x) * slope<br> </pre> <br><br>That may be a bit messy, but what you have there is a single equation with &#111;ne unknown, t. Solve it for t, and if t > ot and t < nt, then the path at least intersects the infinite line of the wall within the time period. To solve for t, first collect the (t-ot) terms &#111;n the left, move everything else to the right:<br><br><pre><br>(t-ot)*((np.y-op.y)-slope*(np.x-op.x))/(nt-ot) = A.y-op.y+slope*(op.x-A.x)<br> </pre> <br><br>Then solve for t:<br><br><pre><br>t = ot+(A.y-op.y+slope*(op.x-A.x))/(((np.y-op.y)-slope*(np.x-op.x))/(nt-ot))<br> </pre> <br><br>Now, if t < ot or t > nt there is no collision. If t > ot and t < nt there <b>might </b>  be a collision. You have to use equation 1 to evaluate the (x,y) position of the collision. If the resulting point has x between A.x and B.x, and y between A.y and B.y, then you have a collision with the wall at exactly time t. <br><br>Equation 2 is easier if the wall is horizontal (y = constant) or vertical (x = constant). And that makes the final equation simpler.<br><br>Hope that helps! (I know its a quick derivation of the formulas. If you have specific questions about the details, please ask. But I don''t have time to really develop it for you further. The forum archives may also help, since collision detection has been covered in the past. You can use google to search the gamedev archives.)    <br><br>Graham Rhodes<br>Senior Scientist<br>Applied Research Associates, Inc.    

quote:

---

Equation 1: position = oldpos + (newpos - oldpos) * (time - oldtime) / (newtime - oldtime)

---

That's a great equation, yet its simplicity can sometimes be confusing. Let's apply this equation to an example! Suppose that you leave your house for work at 6 AM and you always get to work at 7 AM (boy I wish ). Let's say that home and work are 10 miles apart (home at position 0, work at position 10), and you travel in a straight line at a constant speed. How far along would you be at 6:15 AM?

Let us apply our equation:

oldpos = 0 (home)
newpos = 10 (work)
time = 6:15 AM
oldtime = 6 AM
newtime = 7 AM

position = 0 + (10 - 0) * (6:15 - 6:00) / (7:00 - 6:00)
position = 10 * 0.25 / 1
position = 2.5


This makes sense. If we are a quarter of the way along timewise, then we are also a quarter of the way along distance-wise. This is the core concept at work here. The ratio of how long we've been traveling to how long the total time should be can be used to solve for our current position based on how far the total distance is ->

Ds = distance from startDse = distance from start to endTs = time from startTse = time from start to end Ds      Ts----- = ----- Dse     Tse   

Here, we create a definite ratio between distance and time. 'Lo and behold, velocity describes such a relationship! Our velocity is constant, so our ratio is as well.

[edited by - Zipster on September 27, 2002 8:00:42 PM]

Wow, that is beautiful! I am having a similar problem and that really cleared it up. Thanks guys!