gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Beginners > Does anyone know of any good collision detection resources.

#22381 - mr_schmoe - Sat Jun 19, 2004 8:10 pm

There's two things I really look for. First off, my game isn't 3D exactly so I don't need polygon collision. It's more of a 2.5D, like Mario RPG, so it's more than just sprite collision. I was thinking of doing bounding boxes, but sometimes the boxes need to be at odd angles like a 45 degree downward tilt. But then that might get a little complecated, so I could just not allow odd angle objects. There also sphere or ellipsoid collision, that could solve my angle probelm, but that would require a bit more CPU expensive calculation. But the point is, because it's not completely 3D, I need something simpler than polygon collision.

And second, I was wondering how all this is implemented. I suppose what would be the simplest way is have an array of pointers to the each objects data such as position, size and shape. And when detection time comes around, you check the object in question against the rest of the objects in the array and if collision is detected there is does the appropreate reaction. And if you want, you can go so far as to use a pseudo object of where the real object would be the next frame to catch a future collision with a wall or something before it happens and stop it. But you run the risk of a collision with itself. I use ID's for my objects so it can just skip over itself in the array.

So, I am hoping someone read something somewhere along the lines of what I just said in some artical somewhere that they would like to share with me so I can learn from those who wrote the artical, maybe. Anyone?
_________________
How many boards could the Mongols hoard, if the Mongol Hored got bored

#22382 - sajiimori - Sat Jun 19, 2004 8:20 pm

I've had a similar problem. The available articles seem to either deal with orthogonal rectangular collision and pixel-based sprite collision, or full-blown 3D polygon collision detection dealing with bones and subdivision surfaces and NURBS and all that.

Where's all the in-between material, like rotated rectangles colliding with tile backgrounds (for driving games)? What about fast collisions between two circles, or between a circle and a collision map? Circles/rectangles and line segments?

#22383 - mr_schmoe - Sat Jun 19, 2004 8:31 pm

Perhaps we can just discuss it here. What do you think would work best of those kind of scenarios?
_________________
How many boards could the Mongols hoard, if the Mongol Hored got bored

#22387 - sajiimori - Sat Jun 19, 2004 9:17 pm

To collide a rotated rectangle with a collision map, I needed to know which tiles the rectangle is inside. I represented that information as an array of horizontal strips of tiles, where each strip is represented as a starting column and an ending column.

To calculate the start/end columns of each row, I rotated and then translated the corners of the rectangle into their world coordinates, then found the slope of each side, and walked from the topmost corner (on the screen) to the bottom corner, storing the furthest leftward and rightward extents as I went.

#22401 - pentagram - Sun Jun 20, 2004 12:20 pm

This is an open source library that tries to reduce the number of object-to-object tests using axis sorting:

http://www.cs.lth.se/home/Flavius_Gruian/projects/GET/index.shtml

This is an article about geometric tests:

http://www.gamasutra.com/features/19991018/Gomez_1.htm

#22423 - keldon - Sun Jun 20, 2004 10:37 pm

Tell me more about your room, tile sizes, number of y-plane collision levels (look at 3 level diagram below). This will detirmine the smaller details of collision, but one simple method is to define an array representing [x][y][levels], for example with the diagram below, levels is 3. Now for the diagonal blocks you tackle it the same way you do with 2d 45 degree angles.


Code:
_____                       |
    /|                      |
L2 / |______                |
  / /      /|_______________|
_| /  L1  //               /
 L_______//               /
_________/               /
                        /
             L0        /
                      /
                     /
____________________/


Being a sort of isometric game (I guess) that is perfect for floors and levels, enemies can be tackled differently since they are moving, as a basic collision test on (x,z) and then a collision test on (y) for example

P.S. get hold of (gameboy) darkman - and there are other games using the same engine, if I can find them I'll tell you - it's pretty interesting how it switches between 2.5-d and 2-d when you are climbing up ladders and jumping over gaps