i''ve got a game with a variable time-frame -- ie, each update iteration is not a fixed period of time. what i''d like to do is check for 2D collisions over a given period of time (since the last update cycle). let''s presume i''ve got 2D outlines for my game entities (tanks). each outline is series of line segments. each tank has a previous position/orientation and current position/orientation. what i''d like to figure out is if any two of the line segments intersect as the tanks move from previous to current positions. and if they do, when they did. here''s what i''ve figured out so far... given two line segments that change over course of a single interation (let''s call them A(t) and B(t)), what is the smallest value of t at which A & B intersect? A(t) is defined as the line segment between points (x1(t),y1(t)) and (x2(t),y2(t)) B(t) is defined as the line segment between points (a1(t),b1(t)) and (a2(t),b2(t)) x1(t) = x1.previous * (1-t) + x1.current * t y1(t) = y1.previous * (1-t) + y1.current * t x2(t) = ... etc da(t) = a2(t)-a1(t) db(t) = b2(t)-b1(t) dx(t) = x2(t)-x1(t) dy(t) = y2(t)-y1(t) u = (da(t)*(b1(t)-y1(t)) - db(t)*(a1(t)-x1(t))) . ------------------------------------------ . dy(t)*da(t) - db(t)*dx(t) i figure that plugging these values into a 2D intersection formula would give me something that i could take the derivative of (with respect to t) but i''m a little uncertain of what to do with "u" (the indicator of whehter they even intersect). is this a valid method? what do I do next? i''m a bit stuck, i think... possible solutions i can see are scrapping the line-line intersections and making it check for line-point intersections (since two line segments moving from non-intersecting to intersecting must hit one endpoint, it seems)...but I dunno that makes things any easier -- i''m still solving for two variables (u and t). thoughts?

I think the best solution is to calculate the intersection of the two lines, if they intersect, see if the intersection is in one of the segmentes (one is enough) (x and y cordenates between the x1,x2 and y1,y2 from the segment).

Then you want to know if they intersected in time. So you have the space function for an object (its position in time), and you have the coordinates of the possible intersection. Calculate the time that passes from the start of the cicle until the intersection in that point.

Then, calculate the time until the intersection point for the other object (or its position when that time passed) and compare the two times (or the two positions). If both are equal or near then a collition has suceeded.

The segments may or may not be intersecting at the end of the update cycle. Imagine the problem of two fast moving bodies. If they approach each other at sufficient speed, they will "skip over" each other without any segments overlapping at the ends of the update cycle.

I suspect I''m going for the home run approach as opposed to the quick and dirty approach.

I''ve been thinking most recently of considering the problem as a point to line distance problem... dunno if that''s any better...

What you did would work for the collision between two particles, i.e. points. You have lines segments moving. Your line segment can be represented as a vector equation p(s)=(x1,y1)+(dx,dy)*s where s varies from 0 to 1. (dx,dy) is a displacement vector from the start of your line segment to the end of it. Assuming the line segment doesn't rotate or scale then that is constant. (x1,y1) is the start of your line segment, but since the line segment is moving it changes over time. So (x1,y1)=r(t)=(x0,y0)+(vx,vy)*t where (x0,y0) is the position of the starting point at time zero and (vx,vy) is a velocity vector for a point on the line. So your equation is actually p(s,t)=(x0,y0)+(dx,dy)*s+(vx,vy)*t. Time is time so t is the same parameter in both equations, but s is differant for the two lines. So you really have three unknowns. You only have two equations so it is impossible to solve. Just kidding, well sort of.

You can't solve the equation as in this is the point of intersection because chances are if they collide they do not do so at a single point. They may intersect at a single point at a single point in time, but over time there is a whole series of points of intersection. So the best you can do is find an equation in terms of t that will give you the point of intersection at a given time. Complicating matters is that if the lines are parallel there may be multiple points of intersection at a given time.

So your equation is actually p1(r,t)=p2(s,t) where p1(r,t)=(x10,y10)+(d1x,d1y)*r+(v1x,v1y)*t and p2(s,t)=(x20,y20)+(d2x,d2y)*s+(v2x,v2y)*t. Those are actually two equations each, i.e. one for x and one for y. You solve one for r and substitute it into the other then solve the other for s. That gives you an s(t). You want to find where 0<=s<=1 for t0<=t<=t1. That all gets pretty nasty.

Rather than doing that every frame it would be best to just check first if it is possible for the two objects to collide. If you take the center point of the tank then some circle encloses the entire tank. You can come up with a formula for the distance between the centers of the two tanks as a function of time. If you subtract the sum the radii of their enclosing circles then you have that is zero when they first collide and after they pass through one another and stop colliding, i.e. a quadradic. So you check that first because it is relatively fast. Then instead of checking every line in the tank you just check a box outline of the tank. That should be good enough for a game.

Oh yes, an alternative is to just break your frame down into subintervals and check for collision at the start/end of each subinterval. It isn't perfect, but how is the user going to prove you wrong. He never sees the tanks collide and you will catch the vast majority of the tanks passing through one another. Assuming your frame rate is high and the tanks are slow what's it matter.

[edited by - LilBudyWizer on May 30, 2002 8:32:14 AM]

Thanks, bud. But actually, it''s even more complicated than that. (dx,dy) aren''t constant, because the line might (and probably will) rotate -- so it varies over the same t.

The thing that''s getting me, really, is that unless the lines are parallel, they ALL intersect. Of course, if the value of u and v are not 0-1, then they don''t intersect on the line segment. Not sure how to consider that "if" statement in the scheme of things...

Right now, I''m doing (sorta) simple circle intersections. You guys actually helped me figure out how to do this in the same sorta scheme -- two center points moving, when are they closest, are they close enough to have collided. That works fine, but it isn''t quite right for certain things -- namely I have to model my tanks to sorta fill a circle in order to keep them from colliding with dead air.

Does changing the problem to a distance from point to line or point-line intersection help anything?

Well, just don''t get so caught up in the collision detection that you don''t finish the game. It is entertaining to dink around with this type of stuff, but more often than not it doesn''t actually add anything to the game. Does the player have a compelling reason to ram his tank into another? What is being simulated could be quite complex, but what is really going on is the player is playing a game. Don''t lose sight of that little detail for all the trees in the way.

Yeah, it''s playable right now, but I''d like to have a little more freedom in tank design. Also, because the collisions are all circle based, the reactions are as well. Not too important, I suppose, but a little bit of a drag when you''re trying to push something and it keeps "rolling" off your tank because the tank is considered round for collisions...

I may just go with an iterative process...

In my original post, is there any way to take the derivative with respect to t in that equation?

Hmm... that derivative question is actually bogus. I realize, now, that I don''t have any exponents to make the derivative meaningful. I was thinking it was a t^2 issue (so I could find the lowest valyue of t by finding where the derivative is 0). No dice.

Damn.

Rather than using the circle as your only and final test use it as a preliminary test. When two circles traveling on straight line paths pass through one another there are two times when they are just touching one another. That establishs and interval where more elaborate testing might be needed. You can test for the intersection of the lines, but it is going to be relatively costly so you don''t want to do it all the time. An iterative approach is a nice simple way because you are testing stationary lines at a single point in time.

You don''t have to do it that way. The only way for your line segments to collide is for the end of one line segment to hit the other line segment. If you were in 3D they could hit side on like hitting one pencil against another, but in 2D they can''t do that. Using the analogy of the pencil they have to stay on the table top. So there are basically two tests you care about. First is whether the time at which an end point strikes the other line within the interval you care about. Second is whether it is within the interval of the line you care about, i.e. your line segment. You will have four times. That will be the times at which each end of each segment strikes the line containing the other segment. You only want the ones actually within your interval and then the earliest one.

With your equation u will be 0 and 1. If you switch the x''s and a''s as well as the y''s and b''s you get a differant u. You want when that one is 0 and 1 also. To actually find the times though you need to solve that equation for t. Nasty because of all the variables, but there is only one unknown.

Are you saying it migh tbe doable? I understand the pencil analogy. It was something I was considering to make this a bit simpler -- check when a point (end-point) intersects a line. Do you think that might be solvable as I was hoping? Or were you saying it''s solvable in the iterative case...?