## More Collision (again)

distance = sqrt((x2 -x1 * x2 - x1) + (y2 - y1* y2 - y1));

if (distance < 10) {

// collision action here

}

As you can see using the distance formula sometimes doesn't detect the collision and it runs pretty slow. Is there some better equation that can detect a line colliding with a circle? The hard part is how to detect when a rock has collided with the side of a laser.

Thanks,

Iceman

Quote:Originally posted by Iceman

distance = sqrt((x2 -x1 * x2 - x1) + (y2 - y1* y2 - y1));

the first thing I notice is that you need more parens. Your formula as it is now is parsed:

distance = sqrt((x2 -(x1 * x2) - x1) + (y2 - (y1* y2) - y1));

because mults/divs take precidence over adds/subtracts. So try:

distance = sqrt(((x2 -x1) * (x2 - x1)) + ((y2 - y1)*( y2 - y1)));

I dont know why you find this slow - it is one of the fastest ways to collide two spheres. AABB is the only faster code! Is your laser shot a sphere or a point?

One of the problems is that you are checking if there is a collision only on this frame. Its possible that there was a collision between frames - even though there isnt a collision in each surrounding frame. In frame 0 the bullet is on the south side of an object, while in frame 1 the bullet is north of the object. The collision happened sometime between 0 and 1 but your code wont catch it.

There are many articles on handling these collisions on gamasutra.com (I can find the articles if you cant find them doing a search). Also Dave Eberly's book has a lot of good info on how to do this (but be warned - your algebra skills need to be up to snuff). Also if you buy the book you can download his code to handle these kinds of interactions.

hth,

Codemattic

Quote:Originally posted by Icemanalso - you probably dont need to use sqrt. Lets say your bullet has a radius of 1.5 and your meteor has a radius of 20.0

distance = sqrt((x2 -x1 * x2 - x1) + (y2 - y1* y2 - y1));

if (distance < 10) {

// collision action here

}

Code:

`bullet_radius_squared=1.5*1.5;`

meteor_radius_squared=20.0*20.0;

distance_squared = ((x2 -x1 )* (x2 - x1)) + ((y2 - y1)* (y2 - y1));

if (distance_squared < (bullet_radius_squared+meteor_radius_squared)) {

// collision action here

}

So you can avoid the expensive squareroot. If you need the squareroot to get the actual distance - but somehow find it too slow there are fast squareroot functions that use Newton's method.

hth,

Codemattic

Quote:Originally posted by Iceman

distance = sqrt((x2 -x1 * x2 - x1) + (y2 - y1* y2 - y1));

Some performance can be gaind by reducing the number of subtractions (from 4 to 2):

xd = x2 - x1;

yd = y2 - y1;

distance = sqrt((xd * xd) + (yd * yd))

This might be especialy usefull if you run a version that doesn't use sqrt.

Thanks,

Iceman

Quote:Ok sorry I guess I didn't make this clear I'm trying to test a collision with a line segment (the laser) and a circle (the rock). The reason I used the distance formula is because I have no clue how to detect a collision between a line segment and a circle.

There are two ways of doing this, depending on how your laser behaves. Does your laser fire out of the cannon like a projectile (Star Wars style) or does it "blink" on when you fire and "blink" off when you release the trigger (a la old school Star Trek phasers or the lightning gun in Quake 3)?

The first method is to trace a ray from your ship along the path of the laser. As you trace the ray, you can check individual points along the way, using the distance formula you already have. If you find a collision, you can either stop the checking or continue along the ray for penetrating lasers. I would do it this way if you have Star Wars style lasers.

The other method would be to mathematically figure out the shortest distance between the center of the rock (a point) and the laser (the line.) You'll want to find the point on the line that is closest to your rock. Say your line starts at (x1, y1) and ends at (x2, y2), and the center of your rock is at (x3, y3.) We can represent any point on the line by

x = x1 + u(x2 - x1) and

y = y1 + u(y2- y1),

where u is between 0 and 1. The value of u for which the point given by that formula is closest to the center of the rock is given by

u = ((x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2)

Plug that into the equations for x and y above, and you'll have the point on the line that's closest to the rock. Now you can check the distance with the regular distance formula. This method is probably better if you have the Star Trek/Quake 3 style laser.

The mathematical explanation for all that is given here and also contains a link to C code that performs these calculations in 3D.

Good luck,

Joe

Quote:Finally don't I have to pay for a membership or something at gamasutra.com? Every time I try to access an article there it says I have to sign up :-(.

Nope, they have a free membership that you can join. All it requires is an email address, to which you can have them send weekly updates on the game industry. The free membership will also let you check out their features and articles, as well as things like job searching. Good stuff

ICJ

Wow gamasutra sounds pretty nice . Also I'm using star wars type lasers.

Thanks,

Iceman

Thanks,

Iceman

Yep, and after signing up you'll get more SPAM even when you say don't SELL my address. It took me forever to finally get removed from their membership group. Ug! Good luck.

BTW.. Mark's book as info on collision detection.

Cheers

BTW.. Mark's book as info on collision detection.

Cheers

Carlos A. Camacho,

Founder

iDevGames

Thanks,

Iceman

Im glad you solved your slowdown problem - I didnt think it could be because of the math.

Carlos is right - they do send you stuff by email. However I havent found it to be the problem that he has. They send text mail - not html mail - so they dont take up much space/download time. They send out a weekly mailing - which usually spotlights articles I want to read anyway. I havent tried to cancel mine - but I dont doubt that Carlos got the runaround. Its really amazing - I dont expect MLM schemers to take me off their mailing list if I ask (in fact I assume they would take my response as a sign that the email address is 'active' and spam me even worse) - but Im always surprised at the number of 'legitimate' companies that refuse to take you off their mailing lists. I tried to get off of MP3.com and Discovery.com's as well as some others email lists with varying pain-in-the-ass results. Gamasutra.com might very well be the same way. Ive never tried to cancel because I dont mind their email - and I take it as a resonable intrusion in my life to have access to all their great articles. You can always get a free bogus hotmail email address and use that when you sign up.

Anyway - they article to check out is http://www.gamasutra.com/features/200201...el_pfv.htm - it will handle sphere/sphere interactions as well as your laser beam interactions (a laser beam is just a sphere with a really small radius - or a zero radius - and a very very fast speed). It correctly handles interactions with both objects moving - even if they collide only mid-frame.

hth,

Codemattic

Iceman

Update:

u = ((x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2

what are the keyboard commands to make "^"?

Quote:Originally posted by Iceman

u = ((x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2

what are the keyboard commands to make "^"?

The keybord command is [ shift + 6 ], but i assume that ^ means squared (eg 4^2 = 4*4). If you compile this code "^" will mean XOR (bitwise eXlusive OR) and not give you the results you are looking for.

.johan

Thanks,

Iceman

Code:

`if (distance < 13 && distance + 45 < 13) {`

// delete rock

}

Iceman