Archived

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

theSeby

[SDL] Collision

Recommended Posts

Kylotan    9860
Loop through that intersection rectangle (2 nested loops), look up the appropriate pixel in each sprite (a multiply and an offset), compare them (if both are ''solid'', you have a collision). It''s easy when you break it down.

Share this post


Link to post
Share on other sites
SuperRoy    109
Why does that seem extremely slow? Looping through every pixel in each sprite...

Maybe you should have a bounding box and when the boxes intersect, you should only do that pixel-pixel collision detection in that resulting rectangle. Hmmm, I'm stupid anyway.

[edited by - SuperRoy on August 7, 2003 7:08:04 AM]

Share this post


Link to post
Share on other sites
MichaelCarr    122
I''ve found there are extreamly few times when pixel perfect collision is 100% necessary especially in games.

If rectangles aren''t cutting it try using circles instead, or maybe capsules.

Just a thought.

Michael

Share this post


Link to post
Share on other sites
Neen10do    122
if your bounding box collision is giving you "fake" collisions. then make the bounding box for that sprite smaller, only containing the main part (ie body or fluesilage) so the arms and wings may not detect damage, but neither will the huge empty space above them.

----------------------
i code therefore i am.

Aero DX - Coming to a bored Monitor near you!

Share this post


Link to post
Share on other sites
superpig    1825
Or, allow a sprite to use more than one bounding rectangle.

If you''re really going for gold (though possibly slowness as well) you could write code for a ''collection'' of arbitrary collision shapes - so you can use bounding rectangles, circles, and polygons in the same sprite.

Of course, it''s almost totally unnecessary.

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4

Share this post


Link to post
Share on other sites
Kylotan    9860
SuperRoy, there''s no reason why it has to be slow. Think about software 3D renderers that perform calculations for every single pixel on the screen. That is fast enough to get many frames per second, so performing a similar exercise on a tiny fraction of that many pixels when there has been a collision between the bounding boxes will be trivial.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Try this:
http://www.ifm.liu.se/~ulfek/projects/2d_Collision_Detection.html
Its a fast pixel-perfect collision detection library for SDL

- Wyzfen

Share this post


Link to post
Share on other sites
theSeby    122
Thank you very much for your feed back !
I think I can do a box-box collision detection, with box that are a little bit smaller than the entire sprite.

Please check the demo, that's with a box-box col. det., and the box are the same size of the picture (I have to reduce the box). Do you think the box collision with smaller box will be enough ?

my demo

------------------------
- Seby -
www.dfhi-bomber.fr.st

[edited by - theSeby on August 8, 2003 3:32:35 AM]

Share this post


Link to post
Share on other sites
Zefrieg    316
It is such a waste of time doing collision based on pixels. The best thing to do is to just use a 2d polygon and outline the sprite with the polygon. Then, just use the polygon for collision. Here is a set of polygon functions that are really fast.

These are ripped from my polygon class and simplified.



template <class T>
struct Vertex2d
{
T x;
T y;
};

//::///////////////////////////////////////////////////////////////////////////

//:: Function Name:

//:: Precondition:

//:: Postcondition:

//:: ///////////////////////////////////////////////////////////////////////////

template <class T>
bool IsPolygonPolygonCollision(Vertex2d<T>* polygon1, int size1, Vertex2d<T>* polygon2, int size2)
{
bool bIsCollision = false;
int size;
size = size1;
while(size--)
{
if(IsVertexPolygonCollision(polygon2, size2, polygon1[size]))
{
bIsCollision = true;
break;
}
}
if(!bIsCollision)
{
size = size2;
while(size2--)
{
if(IsVertexPolygonCollision(polygon1, size1, polygon2[size]))
{
bIsCollision = true;
break;
}
}
}
return bIsCollision;
}

//::///////////////////////////////////////////////////////////////////////////

//:: Function Name:

//:: Precondition:

//:: Postcondition:

//::///////////////////////////////////////////////////////////////////////////

template <class T>
bool IsVertexPolygonCollision(Vertex2d<T>* polygon, int size, Vertex2d<T>& vertex)
{
bool bIsInside = false;
bool bIsYTop;
bool bLastY;
T prevX;
T prevY;

// Get the last vertex in polygon

prevX = polygon[size - 1].x;
prevY = polygon[size - 1].y;

if(prevY >= vertex.y)
{
bLastY = true;
}
else
{
bLastY = false;
}

for(int i = 0; i < size; i++)
{
if(polygon[i].y >= vertex.y)
{
bIsYTop = true;
}
else
{
bIsYTop = false;
}

if(bLastY != bIsYTop)
{
if(((polygon[i].y - vertex.y) * (prevX - polygon[i].x) >= (polygon[i].x - vertex.x) * (prevY - polygon[i].y)) == bLastY )
{
bIsInside = !bIsInside;
}
}

prevX = polygon[i].x;
prevY = polygon[i].y;
bLastY = bIsYTop;
}

return bIsInside;
}



BTW... This polygon test is so effecient I can render a polygon by creating a bounding box around ANY polygon no matter how complex, and test each pixel if it is inside the polygon. It is pixel perfect, and the rendering isn't that slow considering I'm checking every pixel. Obviously I just render it using the collision detection to check that it works well.

[edited by - Zefrieg on August 8, 2003 5:00:09 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I dont think pixel collision detection is necessarily bad or slow ...
I was originally working on having polygon/circle based collision areas - but then i found a way to check multiple pixels at once :
The link i gave above talks about using masks to check 32 - 64 pixels at a time (after the initial bound-box check)
Very fast, very accurate.

Since in my application, sprites are usually 32x32 or 64x64 and collision areas are usually much smaller (8x8 at most), the checks are usually just a handful of ANDs and shifts.

The reason i''m using that method now rather than the polygons, is then i dont need to work out a bounding region for each sprite. And i dont need to stuff around doing polygon-polygon intersection checks (which looking at Zefrieg''s post isn''t as bad as i thought) - i just load the sprites from an image file and can check them as is.

Currently i''m working on a version that creates a mask using alpha values at load time (allows semi-transparent pixels to collide etc) that works with an ''imagelist'' rather than single images, based on that link. The mask only needs to be created once and can be re-used.

- Wyzfen

Share this post


Link to post
Share on other sites
superpig    1825
quote:
Original post by Anonymous Poster
I dont think pixel collision detection is necessarily bad or slow ...
I was originally working on having polygon/circle based collision areas - but then i found a way to check multiple pixels at once :
The link i gave above talks about using masks to check 32 - 64 pixels at a time (after the initial bound-box check)
Very fast, very accurate.

Since in my application, sprites are usually 32x32 or 64x64 and collision areas are usually much smaller (8x8 at most), the checks are usually just a handful of ANDs and shifts.


Mmm, that''s cool.

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4

Share this post


Link to post
Share on other sites
Zefrieg    316
Well, the method I provided is both the fastest and simplest method to determine if a collision has occured. Basically, draw any type of 2d polygon you can think of, then put a point inside or outside of that polygon. Next, draw a line to the right. If you intersect with an odd number of lines then the point is inside, and if you intersect with an even number of lines then the point is outside.

If you want to determine which edge of the polygon was hit, then it is pretty easy to do. Treat the collision vertex as a perpendicular to each of the edges, and the edge that the vertex collided with would be the one that creates the largest angle.

Share this post


Link to post
Share on other sites
theSeby    122
Thank you all !
Zegrif, your methode (with polygons) is pretty good ! But I think I'm gonna use the bitmask library (I've got a lot of sprites, so that'll be a lot of work to determine the polygons for each sprite).

How does this library work ? Have I to build a mask for each Surface I create, before the game begin ?

------------------------
- Seby -
www.dfhi-bomber.fr.st

[edited by - theSeby on August 10, 2003 8:30:39 AM]

Share this post


Link to post
Share on other sites
Wyzfen    288
Zegrif - there are exceptions to that rule (the line to infinity). When a line crosses a corner of a polygon, you need to change the behaviour.

theSeby - yes, create when you load.
Looking at the header file that comes with that collision library, it looks like you create a bitmask using
''bitmask_create'' that is the same size as your image,
Then you step through your image and set the bits using
''bitmask_setbit''.
Since that will be time consuming and you only need to do it once, just do it at load time - i made a routine that loads the image and creates the bitmasks with one call.
I created a class to store the result - the struct equiv is:

struct {
SDL_Surface * image;
bitmask * mask;
int x,y;
bool visible;
} Sprite;

then when you have a collision you just do :
if ( bitmask_overlap(sprite1.mask, sprite2.mask, int xoffset, int yoffset) != 0 ) {}

it also has funcntions to work out what direction the collision was, if you need it. Looks like a pretty useful library.

Hope that helps

Wyzfen

Share this post


Link to post
Share on other sites