Share your collisiondetection techniques!

[Haikarainen]

I'd thought you guys could share the techniques and algorithms you use for collision detection here, i wont be able to upload any of mine atm since im not home.

It is, in my point of view, a really confusing bit wich can be achived thru many ways, Share !

[Groogy]

What do you mean with techniques? Anything from speeding up the process to how to design an entire system? Or just specific "SphereVsBox" algorithms?

This subject is pretty huge

[Haikarainen]

What do you mean with techniques? Anything from speeding up the process to how to design an entire system? Or just specific "SphereVsBox" algorithms?

This subject is pretty huge

Hehe yup, thats why i created this thread. I guess anything goes, but my specific thought was regarding game-development. Like platform, top down, anything from box to pixel perfect.

[danman]

Hehe yup, thats why i created this thread. I guess anything goes, but my specific thought was regarding game-development. Like platform, top down, anything from box to pixel perfect.

To summary, anythings   .

I'll try later if I'll recall this post, but you can use google search code to find the heaven door .

[Disch]

My latest [serious] game attempt (2D platformer) does everything line based.  The map itself is not tile based like many platformers.  Instead it consists of a series of line segments forming the walls/ground.  This allows for slopes at any angle.

Objects are represented by "a bounding box with a twist".  Basically the bottom-center point represents the "foot".  The bottom left and right corners are raised.  So it ends up looking kind of like this:

Code: [Select]


__
||
\/


How steep the 'V' at the bottom is determines how steep a slope the object is able to climb.


The actual collision detection is all based on line-line collisions.  When an object moves, I draw lines from each of the corners moving in the direction the object wants to move.  If those lines intersect with any wall lines, then I stop the object.

There are other tricks to get it all working, but that's the general idea.

[OniLinkPlus]

I use the Separating Axis Theorem. It works for any two convex polygons, is incredibly fast, and the bounding box check is a special case of it.

[Disch]

Can you elaborate on that?

I know the separating axis theorum is that any two convex polygons that do not intersect have an line that separates them.  However I never understood how you'd go about finding that line and/or whether or not it exists.

I'd be very interested in a more detailed explanation and/or example code.

EDIT:  and I can see how it could apply to object/object collision, but how could you apply it to object/world collision?

[Nexus]

Here is a tutorial about the Separating Axis Theorem:
http://www.metanetsoftware.com/technique/tutorialA.html

[OniLinkPlus]

I'd be very interested in a more detailed explanation and/or example code.

EDIT:  and I can see how it could apply to object/object collision, but how could you apply it to object/world collision?

There's some example code in the Utilities.cpp file of my Terra Game Engine. It's the function IsColliding().

If you're doing a tile-based world, just treat the tiles like objects.

[Haikarainen]

Time to share mine! This is basically for a platformer, where i have a collisionbox for the player, that collides with subrects of sf::Images(aka tiles).

It has 4 boolean functions: OverlapsLeft(), OverlapsRight(), OverlapTop(), and OverlapsBottom(). What they do is they first check if the tile intersects with any side(wich is 1px on one axis, and width/height of the collisionbox for the other, so for OverlapsLeft i have x=1, and y = height), if they do, it iterates the tiles pixels in that intersection. If any of the pixels has an alphavalue of 128 or greater, it returns true.

Code for Overlaps top is found here:
https://legacy.sfmluploads.org/index.php?page=view_code&id=53

Then i just check for collisions when moving left or right, and pretty much every frame for top/bottom.

[Sui]

When I profiled my first game (Gravity Core) I found that a major CPU drain was collision checking.

The game was checking every game entity against every other which is an exponential growth problem.

i.e.
Checking 5 objects against 4 (excl self) = 20 checks
Checking 10 objects against 9 = 90 checks
Checking 100 objects against 99 = 9900 checks!!

To help with this, I implemented a heuristic algorythm that clusters together entities so that only relevant groups need to be checked.

It was based on an excellent article in Game Programming Gems 2. (These are great books - just not cheap!)
http://www.amazon.co.uk/Game-Programming-Gems-Vol-CD/dp/1584500549/ref=sr_1_1?ie=UTF8&s=books&qid=1310893296&sr=8-1

If you shop around, there are some reasonably priced second hand ones knocking around (e.g. Amazon resellers on Amazon.COM).

It's well worth investigating.

If anyone's interested I can try to dig out some sourcecode, though it will need some rework as it's tied into my sprite interface.