Implement Collision Detection

[e_barroga]

How would I go about implementing collision detecting for objects (sprites, if you will)?

[quasius]

How would I go about implementing collision detecting for objects (sprites, if you will)?

Begin by searching these very forums and google.  I'm not trying to be curt, but that's such an insanely broad question as to be unanswerable.  Is there some aspect in particular you're having problems with?

[e_barroga]

Getting things that are drawn on the screen to receive collision events from one another.

[quasius]

Getting things that are drawn on the screen to receive collision events from one another.

Yes, that's the definition of collision detection.  The point is, collision detection is a massive topic you can literally write books and PhD theses on.  So, unless you're more specific, I can't really help you.
If you're just looking for a place to start, I recommend searching these forums and google.  I know there's some information on collision detection on these boards since I wrote it.
You talk about "things" receiving "events."  Do you already have some kind of messaging/event system set up?  If you don't, a much simpler approach is  to just have a method on objects that checks for collision you call when you care.
I'd start by seeing if you can detect when 2 non-rotated, rectangular sprites collide.  Then you can worry about more complex shapes, spatial partitioning, multi-phase collision detection, etc.  (All of which are necessary for an effective, scalable collision detection system.)
And that's just detection.  Collision *handling* is a completely different matter.

[e_barroga]

Thank you for no help, but I already did research before I made this post.

http://www.google.com/search?hl=en&q=site%3Awww.sfml-dev.org%2Fforum+%22collision%22

[Wizzard]

You don't have to be rude to him, he's just trying to help.

http://www.sfml-dev.org/forum/viewtopic.php?t=575

[e_barroga]

You don't have to be rude to him, he's just trying to help.

http://www.sfml-dev.org/forum/viewtopic.php?t=575

Thank you for the advice, however, I am already aware of this sort of method. I was wondering if it would be possible to perform pixel-perfect collisions. Such as non-basic primitive sprites.

[EDIT:]
I've managed to find an article explaining the process of pixel-perfect collisions: http://www.gamedev.net/reference/articles/article735.asp

Basically, you test collisions via bounding boxes, then you get the offsets and start testing pixel by pixel.

[quasius]

You don't have to be rude to him, he's just trying to help.

http://www.sfml-dev.org/forum/viewtopic.php?t=575

Thank you for the advice, however, I am already aware of this sort of method. I was wondering if it would be possible to perform pixel-perfect collisions. Such as non-basic primitive sprites.

That's what I was trying to get you to ask.   i.e. A specific question I can actually answer.
Basically, no.  You *can* doing it by brute-force comparing (the alpha?) of every pixel in the 2 overlapping sprites, but this is way too expensive to be practically useful if you are comparing large numbers of objects.  You need to approximate your sprite into shape "primitives" (assuming 2D: circle, rectangle, triangle, etc.)  Then you need separate hand-optimized algorithms for each possible collision (circle-to-rectangle, circle-to-circle, etc.)  This is not "pixel perfect," but if done correctly, it won't be noticeable.  This type of method is used on modern games where good collision detection/physics is important.
You *might* be able to get away with brute-force methods by just throwing a bunch of hardware at a 2D game that should be able to run much faster, but what I said above is much closer to "real-world."

[quasius]

I've managed to find an article explaining the process of pixel-perfect collisions: http://www.gamedev.net/reference/articles/article735.asp

Basically, you test collisions via bounding boxes, then you get the offsets and start testing pixel by pixel.

Yes, before doing *any* collision detection, you would at-least make sure the bounding boxes overlapped.  Ideally, you'd be checking through some kind of spatial partitioning structure first if the 2 objects are even in the same "ballpark."
But the actual collision detection of comparing each pixel is dog-slow and not scalable.  But if you're just trying to do a simple demo or whatever, you can try that method.

[e_barroga]

I've managed to find an article explaining the process of pixel-perfect collisions: http://www.gamedev.net/reference/articles/article735.asp

Basically, you test collisions via bounding boxes, then you get the offsets and start testing pixel by pixel.

Yes, before doing *any* collision detection, you would at-least make sure the bounding boxes overlapped.  Ideally, you'd be checking through some kind of spatial partitioning structure first if the 2 objects are even in the same "ballpark."
But the actual collision detection of comparing each pixel is dog-slow and not scalable.  But if you're just trying to do a simple demo or whatever, you can try that method.

I know that pixel-perfect collision detection is slow, but I don't assume that it is that slow.

[quasius]

I know that pixel-perfect collision detection is slow, but I don't assume that it is that slow.

It is that slow.  I doubt you'd find it in any commercial product.  You might be able to get away with it for 2D if you're not doing a whole lot of collisions since we have hardware that can run stuff like Crysis, but if you go that route, you'll be articifically inflating your CPU requirements.  A lot.
Collision detection is correctly done by reducing your shape to some kind of geometric primitives (in order of speed fastest to slowest: circle, rectangle, convex polygon, concave polygon) and then using geometrically-intelligent algorithms instead of just brute-force testing each pixel.

Edit:  And since you can get what appears to be pixel-perfect collision detection except under the closest scrutiny with correct methods, there's no reason to use the method you're going for unless you're just making a demo to learn, don't care about speed, and aren't interested in researching much collision detection.  But if that is the case, then go for it.  (It's possible to get lost/overwhelmed in learning projects if you worry about stuff like this too much.  Just keep in mind that if you're serious about making games, it's a topic you'll have to come back to later.)

Edit Edit:  If you actually really, really need pixel-perfect CD for some kind of exacting simulation or whatever, it would best be implmented as a "final check" that's only done if it's tested positive for "normal" collision detection.  But that would still just be a waste of CPU for 90% of games.  Remember, games don't need to be perfect simulations- they just need to look like it.

Edit Edit Edit:  And that's assuming completely untransformed (except translation) collision detection.  If you have to scale and rotate each pixel before testing, you'll end up with something that will bring a NASA super computer to it's knees.

[Dig]

Pixel perfect collision detection isn't that slow as long as its done right.  I've recently implemented it in Flash and that's GOT to be slower than SFML.

Basic premise:

Do bounding box detection (rectangles) to see if the objects you are testing are even near each other, if not don't bother continuing.

Calculate the rectangle created by the overlap (if this is run ever frame or every n frames for slow moving objects then it'll be a small rectangle we're not working with).

Compare the alpha of the pixels to find pixel perfect collision, there is at most going to be a few hundred to compare, and you can register a hit and bail out at the first pixel that's overlapping.

Done.  Doesn't waste much in CPU time, doesn't even get done unless there is a chance that there will be a collision and only runs through the union of the two boxes to ensure the quickest possible comparison.

Obviously if things are a simple primitive shape its better to use that for collision detection as over hundred or thousands of objects it WILL be slower to a pixel level test each time, but its not as doom and gloom aas some people seem to be suggesting.  

My SFML game engine will have pixel perfect collision as an option, I image the player sprite will always have it on and other sprites colliding with each other may not need to be so accurate.

Cheers,
Nick

[Dig]

Just an update on this approach,

With 20 objects with pixel perfect collision as implemented above in a debug build of Flash it takes up to 2 milliseconds to test the collisions (out of a total of 16-20 millseconds per frame, with Flash locked at 24 frames per second anyways).  This is perfectly acceptable for my game, may not be good if you need more objects.  This includes includes rotated and occasionally scaled sprites.

Obviously it only detects collisions with a boolean (yes or no) and dispatches events to the collided objects, it doesn't process any information on location of the collision but that can be calculated in the onCollide functions once its necesary.

I know its a completely different story from using SFML and OpenGL, but if Flash can do it, then SFML/OpenGL can do it better I'm sure.  It'll be a few months before I'm back working in SFML but I'll share my results when I get there if anyone's interested.

[quasius]

Just an update on this approach,

With 20 objects with pixel perfect collision as implemented above in a debug build of Flash it takes up to 2 milliseconds to test the collisions (out of a total of 16-20 millseconds per frame, with Flash locked at 24 frames per second anyways).

That doesn't really mean anything without your machine specs.

[Dig]

Its 'less than a NASA supercomputer'

1.6ghz AMD Laptop with a rubbish video card.  

While I appreciate it doesn't mean a whole lot for comparison purposes, the point I'm trying to make is that, when necessary, pixel perfect collision detection is perfectly feasible in a game.  

Of course any shortcuts such as bounding boxes etc., should be preferred but there are times (and plenty of times outside of just physics simulations) where pixel perfect detection is required.

I'm sure (without any proof to be honest) plenty of 2D commercial games use pixel perfect collision detection in combination with other methods, and a large number of established 2D game engines do.

3D is a whole other story, but as the OP mentioned sprites to start with I'm assuming we're just talking about 2D here

Anyway without backing things up with actual SFML related advice I'm contributing to this thread getting off track.  When I have some OpenGL / SFML collision detection to share I'll be back.