Archived

This topic is now archived and is closed to further replies.

Viri-

Collision Detection Questions:

Recommended Posts

Basicly I''m doing a collision detection in a very simple way. Its not always effective however. Sometimes the bullet that shoots the enemy doesn''t hit the enemy. If you want to see what I''ve done so far for an exampel goto http://revolution.valveworld.com/firstgame.zip I''m looking for a better way to do the collision then what I have below. I''ve heard of pixel comparison etc. But how can I learn about all this? Thanks, Phoenix /////////////////////////////// // RECT collision detection.... /////////////////////////////// int Collision_Test(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2) { // this function tests if the two rects overlap // get the radi of each rect int width1 = (w1>>1) - (w1>>3); int height1 = (h1>>1) - (h1>>3); int width2 = (w2>>1) - (w2>>3); int height2 = (h2>>1) - (h2>>3); // compute center of each rect int cx1 = x1 + width1; int cy1 = y1 + height1; int cx2 = x2 + width2; int cy2 = y2 + height2; // compute deltas int dx = abs(cx2 - cx1); int dy = abs(cy2 - cy1); // test if rects overlap if (dx < (width1+width2) && dy < (height1+height2)) return(1); else // else no collision return(0); } // end Collision_Test

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well, I haven''t done any "extensive" reading of your code, but shouldn''t the line:

if (dx < (width1+width2) && dy < (height1+height2))

be replaced with:

if (dx < 1/2*(width1+width2) && dy < 1/2*(height1+height2))

because the distance between the centers for the x component, if the edges are just touching on the x, should be 1/2*width1+1/2*width2. Think about it. the line segment only covers 1/2 of each rectangle.

Hope it works!

Share this post


Link to post
Share on other sites
I''ve never heard the term pixel comparison, but I''m guessing this is what you are talking about:

The most basic form involves using video memory as a giant array (which it is.) When you draw, say a ship, to the screen the values in video memory change at the location of the ship to the color of the ship. So, to see if a laser hits a ship, you need only check all of the pieces of video memory that lie along the path of the laser and see if any of them are the same color as the color of the ship.

Of course, using this naive implementation, every ship would have to be a different color to figure out which ship was hit.

Example:

00000000
00000000
00000000
00000000
00000000

Assume thats the playing field, in video memory.
Assume the ship is only one pixel large, and is drawn in the upper right corner. The ship''s color has a value of 1.

00000001
00000000
00000000
00000000
00000000

The enemy ship has color 2.

00000001
00000000
00000000
00000000
20000000

Enemy ship fires up diagonally to the right. So, using math, you check the following line of pixels:

0000001
00000x0
000x000
0x00000
2000000
Walla, the last pixel we check is equal to 1! We know we''ve hit the ship.

Of course, you must have a very good line function in order to determine which pixels lie along the line in the direction you are facing (this function is easy in games like space invaders, hard in games like asteroids.)

Hope that helps.

DmGoober

Share this post


Link to post
Share on other sites
Hey, I might be the one that he heard about pixel comparison from, since I came up with it on my own when I was first starting my engine (though I switched to collision polygons when I couldn''t get pixels to work^^).
Basically, you have each sprite with a 1-bit collision data layer, and a collision tile set for the maps, then whenever something moves, check if the tile you''re moving onto has any collision data on it (just use col. tile 0 for blank (this step is just to save time)), if it''s not 0, go check each pixelof the col tile against the pixels of the sprite''s obs layer, and if it collides, don''t move. That was the plan, anyway, but polygons are easier, so I''d suggest using them. Here''s a litle "check if the point is inside the polygon" function (which I shamelessly swiped from a tutorial^_^):

bool CheckPointInside(Point p)
{
int i, j;
bool c = false;

for (i = 0, j = vCount - 1; i < vCount; j = i++)
{
if((((v.y <= p.y) && (p.y < v[j].y)) ||
((v[j].y <= p.y) && (p.y < v[i].y))) &&
(p.x < (v[j].x - v[i].x) * (p.y - v[i].y) /
(v[j].y - v[i].y) + v[i].x))
c = !c;
}

return c;
}


Point is just a class with 2 floats (x and y), and vCount is the nimber of vertices in the polygon.




-Deku-chan

DK Art (my site, which has little programming-related stuff on it, but you should go anyway^_^)

Share this post


Link to post
Share on other sites
I don't think you are accounting for movement between frames.

Take this example (b is bullet, x's are something that should be hit):

Frame 1:

b

xxxx
xxxx
xxxx

Frame 2:

xxxx
xxxx
xxxx

b

Now, obviously, b hasn't actually collided with X. But if b travelled a straight line between start and end points, it passed through X. In the code, things are fine, on screen is a different matter.

You need to check a line segment against a bound box, or some sort of equivalent idea.

Edited by - Nova Z on February 3, 2001 5:12:40 AM

Share this post


Link to post
Share on other sites