# Thread: Collision Test - 2D

1. ## Collision Test - 2D

Hey, I'm working on an asteroids game.

I am storing the location of an asteroid as a single point: x and y. And the asteroid is drawn centered on that point. So when I check for collision I can just add the size of the asteroid to the the specific point to get something like a box shape.

This worked when checking collision between shots fired and asteroids, but proved more difficult to do between the ship and the asteroids. Here is my statement:

xShip = the x coordinate of the ship
yShip = the y coordinate of the ship
asteroidX = the x coordinate of the asteroid
asteroidY = the y coordinate of the asteroid
collisionFactor = The the size the asteroid extends from the actual point
The 0.6f is the size the ship extends from its point
Code:
```if (((xShip + 0.6f < asteroidX + collisionFactor || xShip + 0.6f < asteroidX - collisionFactor) &&
(xShip - 0.6f > asteroidX + collisionFactor || xShip - 0.6f > asteroidX - collisionFactor)) &&
((yShip + 0.6f < asteroidY + collisionFactor || yShip + 0.6f < asteroidY - collisionFactor) &&
(yShip - 0.6f > asteroidY + collisionFactor || yShip - 0.6f > asteroidY - collisionFactor)))```
edit: fixed some the of greater then less then signs to what I intended, but still does not work

So this isn't working.
Should I even be using a statement this long? Should it be broken into several statements?
Also it isn't working properly, because you will just die at random times, even when you are not hitting an asteroid.

Thanks,
David

2. Well you could try calculating the dimensions of the two bounding boxes, so you have ship.top and asteroid.bottom as meaningful variable names to play with.

3. OK, could you explain a little bit more. When you say calculate the dimensions, do you mean get each of the four points that make the bounding box?

Also I don't understand why the variable name would be ship.top, or asteroid.bottom?
Do you mean I should have a variable like that for each vertex of the box. ship.topleft, topright, bottomleft and bottomright?

Sorry, it's just not clear to me.

4. Yes, you create two bounding boxes

Like
ship.right = xShip + 0.6f;

The actual test in the code is much simpler
Code:
```if ( ship.right < roid.left || ship.left > roid.right ||
ship.top < roid.bottom || ship.bottom > roid.top ) {
// no overlap
} else {
// overlap
}```

5. Hey thanks, In the mean time I hacked my own method, but your is much easier. I will implement it soon. Here it is so far:

6. Since your asteroids are not box-shaped, you could easily do a sort of collision detection that'll look a bit nicer here - assume that the asteroids are circles. In pseudocode:

int distance = Pythagoras( asteroidX, asteroidY, shipX, shipY); //calculate the distance

if( distance-asteroidRadius-shipRadius > 0 ) // collision

7. The distance formula is not something you want to calculate on the fly for every asteroid to ship combination there may be present in the system.

You DON'T want to do this:

Code:
```float fPlayerX=Player->GetX();
float fPlayerY=Player->GetY();

for (int i=0;i<m_iNumAsteroids;i++)
{
float fAstX=Asteroids[i]->GetX();
float fAstY=Asteroids[i]->GetY();

float fDistX=fAstX-fPlayerX;
float fDistY=fAstY-fPlayerY;
float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);

if (fDist<=fSomeConstantDist)
{
//Wham, collide
}
}```

8. > float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);
If you pre-square the constant ( fSomeConstantDist *= fSomeConstantDist), then you can avoid the square root altogether.

float fDist=fDistX*fDistX+fDistY*fDistY;
if (fDist<=fSomeConstantDist) /* compare squares */

9. Yes and I always work in terms of the square where I can. I was showing a simple example of what most would do at first but would be wrong in doing so.

But perhaps I'm making a mountain out of a molehill since computers are fast enough that even 200 square root calculations probably isn't going to make any big difference.

10. So, then your saying it would be good to use the circle calculation if I pre-square the constant like Salem said?

11. Considering the fact that you are getting 8xx FPS from your game, stuff like pre-squaring the constant is a good idea, but not necessarily required. You'd get a bigger difference from replacing your draw statements with 2d ones (glVertex2f, etc.) or replacing display lists with VBOs, etc.

Just because I like to perform insane close flybys in games of this style, why not do exact collision detection? Check the circle test, and then if within it, do a line by line test.

For a line:
Code:
```struct Point
{
float x, y;
}
struct Line
{
Point a, b;
}
bool counterClockwise(Point a, Point b, Point c)
{
return ((b.y - a.y) * (c.x - b.x) < (c.y - b.y) * (b.x - a.x));
}
bool testIntersection(Line a, Line b) //Returns true if the segments intersect eachother
{
return (counterClockwise(a.a, a.b, b.a) != counterClockwise(a.a, a.b, b.b) &&
counterClockwise(b.a, b.b, a.a) != counterClockwise(b.a, b.b, a.b));
}```
So, check the lines of the ship against the lines of the asteroid you are detecting a possible collision with. (If you are feeling performance crazy, you could store the lines of the asteroid within a binary search tree and pass the lines of the ship relative to it)

12. Originally Posted by Bubba
But perhaps I'm making a mountain out of a molehill since computers are fast enough that even 200 square root calculations probably isn't going to make any big difference.
Not to mention making programming a little more difficult for people just learning something. You'd be better off partitioning the playfield into a series of segments and limiting collision detection between objects to the segments they are in.

13. Originally Posted by Salem
> float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);
If you pre-square the constant ( fSomeConstantDist *= fSomeConstantDist), then you can avoid the square root altogether.

float fDist=fDistX*fDistX+fDistY*fDistY;
if (fDist<=fSomeConstantDist) /* compare squares */
Ok, I'm trying to do this. I guess I didn't understand it as well as I thought I did, because I'm not sure how to implement it.

Right now I pretty much have what Bubba said not to do:

Code:
```    float distance;
distance = sqrtf((asteroidX - xShip)*(asteroidX - xShip) + (asteroidY - yShip)*(asteroidY - yShip));
if (distance < collisionFactor + 0.6f)
{
if (GetTickCount() - spawnprot > 5000)
{
hit();
}
game_over();
}```
It works this way, and still gets pretty much the same fps, but I still want to know what constant I need to pre-square.

14. You don't pre-square a constant, you work in terms of the square of the distance. Since you know the desired distance you want to test, simply square it and test against that.

So if you have a bounding box in 2D that has a width and height of 50 pixels, you would need a 50x50 or perhaps a 40x40 bounding box. Now take 40 and square it and that is the distance you check when doing your calculations.

Code:
```if ((distX*distX+distY*distY)<(40*40))
{
//wham
}```
You can store the bounding box squared distance in a class data member and use it later in your calculations.

It works this way, and still gets pretty much the same fps, but I still want to know what constant I need to pre-square.
This pretty much confirms my statement about making a mountain out of a molehill and what Salem has been warning all of us about many many times. Optimizing where it really doesn't make a difference is a waste of time.
However if you were creating this for a 3D game that also had to do scripting, models, textures, effects, etc,. then you would need some type of spatial partitioning for your trivial rejection collision test. If the object passed that then you would move on to your more expensive but also more accurate bounding test. If that passed you could even move on to a point-in-poly test which is extremely expensive but very accurate.

15. Alright, thanks for all your help, guys. Right now I have a bounding box around the ship, If the asteroid is within the box, then it does circle collision test. Then if it's inside that I want to do the line by line Norman was talking about.

I read the code he gave me several times, and I'm still don't really understand it. What is the counterClockwise function doing?

Oh, and I Googled "collision line test" and Normans post came up

Popular pages Recent additions