## More Collision (again)

Member
Posts: 196
Joined: 2002.04
Post: #1
I'm having trouble calculating collision between a laser and a rock. This is what I'm doing now:
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
Member
Posts: 304
Joined: 2002.04
Post: #2
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
Member
Posts: 304
Joined: 2002.04
Post: #3
Quote:Originally posted by Iceman
distance = sqrt((x2 -x1 * x2 - x1) + (y2 - y1* y2 - y1));
if (distance < 10) {
// collision action here
}
also - 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

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
Member
Posts: 39
Joined: 2002.04
Post: #4
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.
Member
Posts: 196
Joined: 2002.04
Post: #5
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. Although, the distance formulas you gave above will work great for my ship and rock collision. Also I suspect the reason the collision is slower is because the laser is traveling very fast over a big area of the map. 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 :-(.

Thanks,
Iceman
Ice Cream Joe
Unregistered

Post: #6
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
Ice Cream Joe
Unregistered

Post: #7
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
Member
Posts: 196
Joined: 2002.04
Post: #8
Wow gamasutra sounds pretty nice . Also I'm using star wars type lasers.

Thanks,
Iceman
Founder
Posts: 1,141
Joined: 2002.04
Post: #9
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

Carlos A. Camacho,
Founder
iDevGames
Member
Posts: 196
Joined: 2002.04
Post: #10
Oh well I already signed up hehe :eek:. I found some good articles anyway, so it's worth it. Also I found out why the lasers were firing so slow; I forgot to put the return NO; for -(BOOL)resignsFirstResponder; . Mark's game programming book sounds interesting; I'll check it out.

Thanks,
Iceman
Member
Posts: 304
Joined: 2002.04
Post: #11
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
Member
Posts: 196
Joined: 2002.04
Post: #12
Thanks for the link. Yeah I guess you're going to get spamed one way or another. You wouldn't believe how much yahoo spams there own e-mail accounts .

Iceman

Update:
u = ((x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2
what are the keyboard commands to make "^"?
Apprentice
Posts: 5
Joined: 2009.01
Post: #13
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
Member
Posts: 196
Joined: 2002.04
Post: #14
Sorry yeah I just looked at my keyboard . I was thinking it was an option+shift or option font.

Thanks,
Iceman
Member
Posts: 196
Joined: 2002.04
Post: #15
I'm still having some problems. Ok this is what I'm doing now:
Code:
```if (distance < 13 && distance + 45 < 13) { // delete rock }```
Is there any way I can have distance be a continuous bubble like "if ( (0.0 < distance < 45) < 13 ?) {}" instead of having two collision bubbles where one adds 45?

Iceman