Sign in to follow this  
sakky

Collision Error...!?!?

Recommended Posts

Okay so far so good, my little Asteroids clone is coming together nicely. I’ve noticed a problem in the collision detection algorithm. I knew that this may come up at a later time, but I was crossing my fingers and hoping other wise. I use a similar SAT method for collision detection. If you haven’t guessed already, my problem is the collisions are missed due to the fact for time. Not as if you needed it but to be more descriptive: Example would be the bullet is on the left side of a rock(Asteroid). After updating the position of the bullet it is now at the right side of the rock, successfully passing though the rock, but never successfully detected as a valid collision. I need to know how to fix this problem. Should I save the old position of a sprite and use some ray casting or something? I’m not sure, so that is why I ask.

Share this post


Link to post
Share on other sites
What shapes are your objects that are to collide?

If they are circles then there's a really easy trick to do perfect collision detection. Say you have two moving circles (or spheres if this is 3D):
Circle 1 has radius r1, velocity v1, and position p1.
Circle 2 has radius r2, velocity v2, and position p2.
Now all you do is perform one simple ray/circle hit test:

The ray will be at position p2-p1, and points in the direction of v2-v1.
The circle will have radius r1+r2 and be located at the origin.
Now a simple ray/circle test will give you a perfect hit test.[cool]

From there it's a relatively simple matter to work out the collision response as well. But we can help you with that when you get up to it, if required.

Share this post


Link to post
Share on other sites
Define, simple ray test. My bullets are just dots, soon to be pixels if I can get them that way. And the asteroids are circular, but not pure circular (give or take a few bumps to reality).

[Edited by - sakky on April 30, 2006 4:53:48 AM]

Share this post


Link to post
Share on other sites
For bullets and other fast-moving objects, it's generally a good idea to have a collision test that checks *between* the frames, not just test "before and after". One way to do this, in your case, is to trace a line segment between the "before" and "after" positions of your bullet, and to test if this line segment intersects the asteroid's collision circle.

To test if a line segment intersects a circle, you simply need to calculate the shortest distance between the line segment and the circle's center ; if that distance is smaller than the circle's radius, there is a collision.

Here's one way to calculate the distance between a line segment and a circle:

inline float DistPointToPoint(float p1x, float p1y, float p2x, float p2y) {
float dx = p2x-p1x;
float dy = p2y-p1y;
return sqrt( dx*dx + dy*dy );
}

float DistPointToSegment(float px, float py, float s1x, float s1y, float s2x, float s2y) {
float sdx = (s2x-s1x);
float sdy = (s2y-s1y);
float dotproduct1 = (px-s1x)*sdx + (py-s1y)*sdy;
if (dotproduct1 <= 0) {
return DistPointToPoint(px, py, s1x, s1y);
}

float dotproduct2 = sdx*sdx + sdy*sdy;
if (dotproduct2 <= dotproduct1) {
return DistPointToPoint(px, py, s2x, s2y);
}

float b = dotproduct1 / dotproduct2;
float closestX = s1x + b*sdx;
float closestY = s1y + b*sdy;
return DistPointToPoint(px, py, closestX, closestY);
}




One thing to think about is that if you've got a lot of asteroids floating around the world, doing this check on every one of them can get somewhat slow. What you can do is use a rougher, faster test to quickly eliminate most of the cases before doing the real check. This test is an Axis-Aligned Bounding Box test, or AABB, and it's pretty much the fastest collision test ever ; you can test the asteroid's bounding box against the bounding box of the bullet's trajectory in the last frame.


bool AABBIntersect(int left1, int top1, int right1, int bottom1, int left2, int top2, int right2, int bottom2) {
return ( right1 >= left2 && left1 <= right2 && bottom1 >= top2 && top1 <= bottom2 );
}


Share this post


Link to post
Share on other sites
I’ve updated my site and the game. The collision still has problems, but it’s sort of hard to tell. The game is pretty much done (alsmost). There isn’t much left to do with it. I’m trying to make it as close to the original as I can (with a newer look for graphics).

Anyways, you can download the demo, for lack of better term here!

Here is a preview:

Share this post


Link to post
Share on other sites
Looks pretty nice :)

A couple things, though: make sure to include d3dx9_28.dll with your game, as when I tried the game on my computer it crashed on load complaining about that file. I got that file from another game and it went fine.

Also, your asteroids seem to be missing a graphic frame every rotation... they "disappear" periodically. It's probably just a matter of reducing by one the upper limit on the loop that updates the asteroids' frame.

That also made me notice that asteroids that are spawned together (either at the level start or when you hit a big asteroid) always have the exact same frames at the same time ; randomly offsetting an asteroid's frame number when you spawn them might look better.

Share this post


Link to post
Share on other sites
Yeah, maybe I should also randomize the frame. In answer to you complaint about the ‘disappearing effect’ well, I’ve noticed it before, once in a while, but in most cases it doesn’t happen. The frame numbers are correct, at least every time I check them.

I will think about using your collision approach, but from what I have so far, I won’t need to worry about it to much until I get the other bugs fixed. The collision tests I use currently work; they just miss every now and then.

I don’t know what you mean about asteroids spawning together, unless you are talking about the frame issue. Ooohhhhhhh, I know what you mean.

I try to spawn the asteroids on the edges of the screen. I just slapped something together that uses a random even number plots the rock either on the top, bottom, left or right edges of the screen. Obviously, it’ spawning them together and they are suppose to be spread apart. Like I said, the algorithm is just slapped together nothing really though out at all.

I’m glad you like what you’ve seen and thanks for the advice.

Share this post


Link to post
Share on other sites
Okay, well I just fixed the Direct3D version issue.

NOTE: to others the are as wise as me: Use DIRECT3D_VERSION macro when creating the IDirect3D9 interface apposed to D3D_SDK_VERSION.

I’ve also fixed the problem with the frame issue. The numbers were correct, but the way I was incrementing them: post vs. pre increment. I’ve also added randomized frames, so the rocks won’t always start at frame 0.

Thanks for the help & advice again because it helped.

NOTE : The problem will use a game control if one is available.

Share this post


Link to post
Share on other sites
I fixed the collision detection! Thanks to all you help, I’ve got a pretty well game now. It may not be complete [u]yet[/u], but it will be soon.

I fixed a few other problems in it too. And I also changed a lot of the graphics and sounds. Check it out if you want > here!

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