Collision detection with 2-dimensional velocities

Yep, you are heading in the right direction it sounds like.

For single pixel objects (like a bullet if it is one) you can do a "ray cast" from the place where it was, to the place where it wants to be after you add velocity.

you do this by thinking of the path of the bullet as a line, and then seeing what that line intersects with (and how far along the line the intersection happens if you want to know that!)

For larger objects, such as those represented by a bounding square or a bounding circle, there are "moving box" and "moving circle" tests that you can do.

For instance to test the player moving (a moving box) vs a stationary land mine (lets say this is a non moving circle) you would want to do a "moving box vs circle test"

If both things were moving, what you would do is subtract the velocity of one object from the velocity of the other object so that due to relativity, one object was standing still while the other was moving so that you could do a moving object vs non moving object test.

Kind of a high overview of the problem but hopefully it helps! And yes, you are right to worry about this case for collision detection!

Oh btw, a simpler solution to this problem would be to do multiple collision test samples along the path of the object.

So if an object moved 100 units and was 25 units wide, you might do a collision test at 25 units down the path, 50 units down the path, 75 units down the path, and 100 units down the path.

If it didn't hit anything along the way, you know it's safe to move.

The problem with this however comes when 2 objects are moving and have intersecting paths. This method could totally miss the fact that these objects should have collided :P

The "swept shape" / "moving object" collision tests handle this case and would report a collision.

[Edited by - Atrix256 on May 5, 2010 7:37:12 PM]

Quote:

If both things were moving, what you would do is add the velocity of one object to the velocity of the other object

That's the right idea, but you'd actually want to subtract the velocity of one object from the velocity of both objects (not add them together).

Thanks Jyk, edited

Thanks for the help! Between your tips and some articles I've been reading I think I have a decent idea of where to go with this. If someone could please read over this high level overview of my plans and make sure I'm on the right track, that would be great. The whole idea is based on Atrix's notion of calculating the relative velocity of the two objects. I'm assuming every collision hull is circular:

1) For each frame, calculate the relative velocity of two objects. If S is the motion vector for the ship and B is the vector for the bullet, in this example we'll subtract B from S to get the relative velocity vector (R = S - B).
2) Determine the inverse slope of R.
3) Use this inverse slope and the position of the bullet to determine the equation of the line that is perpendicular to R and passes through the bullet's location.
4) Find the intersection of this line and R. This intersection (X) will be the closest point on R to the bullet.
5) Ensure that X lies somewhere on this relative velocity vector (er... technically, on this line segment). If it does...
6) Calculate the distance between the bullet and X. If the distance is less than the combined radii of the bullet and the ship, then there was a collision.

As I wrote this up, I came to realize that I'm completely abusing the term "vector" when I might actually mean "line segment", so I apologize if this causes confusion.

In any case, does this sound sound? I don't want to start coding this up until I check with the pros :) Thanks in advance.

I think you have the right general idea, but you don't want to be doing anything with slopes; everything that you're talking about can (and should) be done with vector math.

The test you're describing sounds like a Boolean swept circle-circle test. The basic idea is similar to what you describe, but the details are a little different (for example, no slopes are involved).

Once you've re-arranged things so that one of the circles is stationary and the other is (possibly) moving, you can reduce the test to a segment-circle test by making the moving circle a point and expanding the other circle by the radius of the moving circle. You now have a segment (representing the motion of the moving circle) and a circle, which you can then test against each other.

To test a segment and a circle for intersection (Boolean only), compute the closest point on the segment to the center of the circle and see if the (squared) distance from the circle center to this point is <= the (squared) radius of the circle.

The algorithm for finding the closest point on a segment to a point is straightforward, and you should be able to find it by searching for (e.g.) 'closest point on segment' (but post back here if you get stuck).