Sign in to follow this  
matrisking

Collision detection with 2-dimensional velocities

Recommended Posts

I've started writing a basic engine for a space invaders-style shoot em up and am having difficulty determining what the best way will be to handle collision detection. The goal is to create a bullet hell shmup that initially will only support the following collisions: - Player vs enemy - Player vs enemy bullet - Enemy vs player bullet My objects contain x and y coordinates as well as x and y velocities that measure the number of pixels traveled per frame (as described in Lazy_foo's SDL tutorials). However, I'm worried about cases where a high velocity object might "jump" over another object in one frame. In other words, if the player's hitbox is 10x10, and there is a 1x1 bullet with a velocity of 12, it is conceivable that the bullet will skip over the player entirely in one frame. Generally speaking, what are some best practices here? Am I approaching this from the right angle? It seems like having xVel and yVel makes move functions very easy to program, but creates constraints to how big your velocities can be (or how small your objects can be). If this is a valid concern, what are some simple alternatives? Thanks!

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.


Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this