  SHMUP-DEV » SHMUP DEV FORUMS » Assistance  Efficient 2D Collision Detection of two moving circles

Pages:    Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  January 04, 2006, 11:54:42 AM #0
SnT2k Efficient 2D Collision Detection of two moving circles

Hi, it's my first post here!
I'm coding my own shump howeber, I haven't implemented a *working* algorithm for collision detection. Most of my bullets are round so I'll only need to detect collisions between two moving circles (if they're just statoinary, then I won't have any problems, however, they're moving) I've already read articles such as http://www.gamasutra.com/features/20020118/vandenhuevel_02.htm and http://www.gamedev.net/reference/articles/article1234.asp however, I can't seem to get the code working. I'm using Direct 3D so you could say most of my variables uses D3DX like D3DXVECTOR2 and D3DXVec2LengthSq();

so far, here's the code I did that doesn't work quite well:
Code:
namespace CollisionCheck {
bool Circle2Circle( const D3DXVECTOR2 &pos1, const float &radius1, const D3DXVECTOR2 &vel1,
const D3DXVECTOR2 &pos2, const float &radius2, const D3DXVECTOR2 &vel2 ) {
//This should work

D3DXVECTOR2 RelVel = vel1 - vel2, RelPos = pos1 - pos2; //Get the relative velocity(to simplify the moving to moving collision to a moving to static collition) and position so that we
float velMag = D3DXVec2Length( &RelVel );
float distance = D3DXVec2Length( &RelPos );
if ( velMag < distance - radsum ) return false;
D3DXVec2Normalize( &RelVel, &RelVel );
float dotProd = D3DXVec2Dot( &RelVel, &RelPos );
if ( dotProd <= 0.0f ) return false;
float Perpendicular = distance * distance - dotProd * dotProd;
if ( Perpendicular >= radsum ) return false;
float hitLoc = radsum - Perpendicular;
if ( hitLoc < 0.0f ) return false;
if ( dotProd - sqrt( hitLoc ) < velMag ) return false;
return true;
}
}

It's a quirky.. :\ help would be appreciated...  January 04, 2006, 12:59:08 PM #1
Indiepath Re: Efficient 2D Collision Detection of two moving circles

Ouch, that's kinda not very effiicient - surely you only need to check the distance between two points.

Code:
float Distance2D(float dx,float dy)  //dx is vector from x1 to x2, dy is vector from y1 to y2
{
return sqr(dx*dx+dy*dy);
}
And then work that with the two radii :-
Code:
bool Circle2Circle(float rad1, float x1, float y1, float rad2, float x2, float y2)
{
float dx = x2 - x1;
float dy = y2 - y1;
if (Distance2D(dx,dy) < rx) { return true; }
return false;
}

PS. I have not checked this code, just typed it in.  January 04, 2006, 01:39:21 PM #2
Ape Re: Efficient 2D Collision Detection of two moving circles

Hi I am also using Directx and I have this function for checking collision

Code:
bool Player::CheckBulletCollision()
{
//Check collision with enemy bullets
for(vector<EnemyBullet*>::iterator it = pGAM->GetEnemyBullets()->begin(); it != pGAM->GetEnemyBullets()->end(); it++)
{
if((*it)->IsActive())
{
float32 xDiff = (*it)->GetPos()->x - m_vPos.x;
float32 yDiff = (*it)->GetPos()->y - m_vPos.y;
float32 zDiff = (*it)->GetPos()->z - m_vPos.z;

float32 distance = xDiff * xDiff + yDiff * yDiff + zDiff* zDiff;

{
(*it)->SetActive();
Die();

}

}
}

return true;
}

I calculate the radius when I initialize then check all active bullets, enemies or whatever every Update

www.stgfan.com the number one swedish shmup community  January 04, 2006, 09:20:47 PM #3
oNyx Re: Efficient 2D Collision Detection of two moving circles

Indiepath, there is no need to sqrt (expensive operation) if you only want to know *if* they collide.

You know the two radi and you know how big they are when they are squared. So you only check if the sum of those squared radi are smaller than the squared distance. You dont need the excat distance at all.

(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) < sr1 + sr2

If so, a collision has happend. I used precalculated square radi (sr1 and sr2), because its silly to calculate the same thing over and over again (even if r*r is something very simple... well, its needed a million times).

edit: btw this sort of check is very cheap. You can easily do it 2000 times per frame (yes, in a game... with a 500mhz machine).

edit²: oh and I used < instead of <=, because "touching" (infinitite small distance) isnt a collision.
« Last Edit: January 04, 2006, 09:26:33 PM by oNyx »  January 05, 2006, 08:08:56 AM #4
SnT2k Re: Efficient 2D Collision Detection of two moving circles

Thanks for the post guys however, I already stated that what I need is a detection for two moving circles; I also said that if they're two static circles, I won't have any problem at all (the square of the distance formula is pretty basic).
To illustrate why I cannot use the distance formula for two moving circles, I'll present a simple case:
1) There are two degenerate circles, A(0,0) and B(0,7)
2) To make the problem simpler, let's say that B is stationary while A is moving at a velocity of V(0, 10)
3) Will they hit? Yes of course.
4) using the square of the distance formula:
a) before movement ( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) ) = 0*0 + 7*7 = 49 which is greater than 0
b) after movement ( (A.x-B.x)*(A.x-B.x) + ( (A.y + V.y)-B.y) * ( (A.y + V.y)-B.y) ) = 0*0 + 3*3 = 9 which is also greater than 0
Therefore, the distance formula will not work in this case
5) Let's say that the given velocity is not "fine" enough, meaning, it has to be smaller (i.e. 10px / 10frame  which should just be 1px/frame). So we'll normalize the movement vector.
a) |V| = V/V.Length = V.x/Length, V.y/Length
b) |V|.x = 0/10 = 0, |V|.y = 10/10 = 1
c) So how do we move? we'll multiply |V| by the original length again... right? if we merely increment A by |V|, we won't reach the required speed we need.
d) So our collision detection will go like this:
Code:
for ( float interval = 0.0f, interval < V.Length, interval += 1.0f ) { //A normalized vector will always have a length of 1
if ( ( (A.x+ V.x*interval) - B.x)*( (A.x+ V.x*interval) - B.x) + ( (A.y + V.y*interval)-B.y) * ( (A.y + V.y*interval)-B.y)  > 0 ) return false;
return true;
}.
which MAY work (there are other cases which this may not work) but moreover, what if the vector length was large? let's say 50.0f? The loop will grow... and that's not pretty...
6) So enough ranting about the distance formula... I still can't get the algorithm stated in the articles to work  January 05, 2006, 08:51:37 AM #5
oNyx Re: Efficient 2D Collision Detection of two moving circles

Oh... sweeping... how unusual. Stuff like that is usually used in physic heavy games and not in shoot em ups.

Well, here is another article. Eventually it helps. (I only used it as a reference for sphere-plane sweeping stuff)
http://www.gamasutra.com/features/19991018/Gomez_2.htm  January 05, 2006, 09:13:14 AM #6
SnT2k Re: Efficient 2D Collision Detection of two moving circles

Oh... sweeping... how unusual. Stuff like that is usually used in physic heavy games and not in shoot em ups.
Then how is it usually done? The player's bullets are fast so I'm afraid they'll just pass through enemies.

Anyway, a lot of thanks for pointing that article  January 05, 2006, 10:27:56 AM #7
oNyx Re: Efficient 2D Collision Detection of two moving circles

>Then how is it usually done?

With those simple checks. At 60fps 5-10 pixels per frame are pretty fast and bullets will only miss in extreme special cases. You can compensate for that by making the enemy or bullet hitzone a tad larger if you like.

Just prototype it and check if its accurate enough for your game. (It only needs to look/feel right.)  January 05, 2006, 01:20:24 PM #8
Nexic Re: Efficient 2D Collision Detection of two moving circles

My games run at as many FPS as they possibly can, but multiply all movements by a variable which is worked out each frame. This will slow the movements down if the game is running at a high framerate and speed them up at a slower framerate. So everything stays the same relative speed no matter what the framerate is. I'm guessing your game must do something like this? If so then just:

Obviously this has the problem of then colliding too far width wise. So instead I would calculate collisions using rotated rectangles. The rectangle would always point in the direction the bullet is traveling. Then extend the length collision size by the speedfactor like I did above.

The trouble with that is that rotated rectangle collisions are quite hard to do and can slow the game down a lot if you calculate it often. So the simple solution is to set a fixed minimum framerate of say 20. If the computer can't get 20 then just let the gameplay slow down like it normally would with a fixed framerate game.

This means that you can then make sure none of your bullets can possibly miss a target by adjusting the collision sizes accordingly with the potential speeds. Unless you want almost instant hit bullets this should easily be possible at 20 fps. If you do want instant hit bullets then you need to calculate what it hits from the moment it is fired.  January 06, 2006, 02:13:20 AM #9
solidcube Re: Efficient 2D Collision Detection of two moving circles

Turn the swept area of each circle into a rectangle.  Check for intersection of the four tangent lines (not the internal diameter lines.)

Check for collision of the circles themselves by the point distance method described above. Pages:    Go Up