Collision Detection


fr0z3n

Still Fresh
Joined
Feb 27, 2006
Messages
9
I was wondering if collision detection (simple) was available in SDL libraries. I have two alpha-masked bitmaps and I want to check if a collision occurs. Do I have to do this manually by checking pixels? Or is there a routine available for this?
Also, if I have to implement it myself, can someone point me to a good tutorial on collision detection (in 2D).
 
using the images soruce rect's you can use this function:
Code:
int SDL_Col(SDL_Rect a , SDL_Rect b)
{  
  if(b.x + b.w < a.x)	return 0;  //  No they dont collide
  if(b.x > a.x + a.w)	return 0;                                           
  if(b.y + b.h < a.y)	return 0;  
  if(b.y > a.y + a.h)	return 0;  
   
  return 1;                     // yes they do collide
}

For more on collition i sugesst you goto
http://lazyfooproductions.com/SDL_tutorials/index.php
or
http://www.libsdl.org/tutorials.php
for a list of tutorials
[edit] code was messed up
 
Thanks for the reply. I guess I will stick to simple box collision detection till I figure out how to get more complex collision detection working.

And Thanks for the link - it looks very useful.

:)
 
should be a simple rect function

or, thats what I use in C++

however, if your sprites arent rectangles, then you might have some collision problems with transparencys (spelling sucked on that)

~Octavious

EDIT
a little late on the draw....
well, that code looks good, Ill post a snip from my program if ya need it, but that piece looks good
 
i found this...http://www.ariel.com.au/a/python-point-int-poly.html

don't know how much it'll help.

but what i'm saying is, maybe make a polygon that covers the approximate area of the ship and use that to test? or like ian said with the smaller rectangle.
 
The problem is that the ship is shaped like a triangle. So that would cause a lot of inaccuracy if using a rectangle.
The solution I guess would be to use a Collision Polygon for each sprite.
Thanks for the link rokdcasbah, I think maybe I can use that along with the Collision Polygon idea to make something??
 
By ship, I'm taking this is a sidescrolling shooter of sorts?

All ships usually have a hitbox on most arcade games, a small rectangular box on the cockpit. Usually it works well, best if there's a thousand bullets on screen though :p
 
jaesond posted on Feb 27 2006 at 06:10 PM said:
By ship, I'm taking this is a sidescrolling shooter of sorts?

All ships usually have a hitbox on most arcade games, a small rectangular box on the cockpit. Usually it works well, best if there's a thousand bullets on screen though :p

Ok.. I could try that (Rect covering the cockpit). Thanx a lot! :D
 
Last edited by a moderator:
what would also be possible is use rectangles to check if the objects are close to eachother, and go to more precise methods if they are. then you get accurate collisions, and if there are a lot of objects on the screen, hardly any difference in speed since most will use the very fast rectangle collision check :)
 
JyCet posted on Feb 27 2006 at 08:13 PM said:
fr0z3n, lot of professional games use bounding box ;)

Heh :D
And Racemaniac raises a valid point. I dont need to do a complete check every time. Only when the rects intersect.

:)
 
Last edited by a moderator:
fr0z3n posted on Feb 27 2006 at 08:29 PM said:
JyCet posted on Feb 27 2006 at 08:13 PM said:
fr0z3n, lot of professional games use bounding box ;)

Heh :D
And Racemaniac raises a valid point. I dont need to do a complete check every time. Only when the rects intersect.

:)
I wanna know how a complete check is done. :(
And what if the image is transparent, what then?
 
Last edited by a moderator:
fr0z3n posted on Feb 27 2006 at 09:29 PM said:
JyCet posted on Feb 27 2006 at 08:13 PM said:
fr0z3n, lot of professional games use bounding box ;)

Heh :D
And Racemaniac raises a valid point. I dont need to do a complete check every time. Only when the rects intersect.

:)

True, but keep in mind that when many computing-intensive collision occur, the game may slow down a lot compared to times when there are no collisions.
Anyway, the theory can be expanded by checking only the rectangular area of the two sprites that overlap to cut on the processing time.
 
Last edited by a moderator:
Allegro has an RLE data format for some sprites, where strings of solid pixels (of varying colours) are encoded as a block, and strings of transparent pixels are skipped as a block. It's intended to speed up rendering, but it's also a great way to speed up almost-pixel-perfect collision detection.

If SDL doesn't have something similar, you can still make your own similar structure, storing the X positions of the first and last solid pixel of each horizontal row. This linearizes the collision test - check for X and Y intersection, then loop over the Y intersection checking for a specific X intersection of the solid pixels. This scheme can't deal with holes in objects - it requires a degree of convexness - but it's simple to implement, very fast (O(n) vs O(n^2)), and for many object shapes it's quite an improvement over just checking the bounding box.

It can also speed up detection between an RLE object and a generic object - you only need to check for collision on solid areas of the RLE object. This is a much less significant gain though - the complexity is still the same as checking two bitmaps against each other.

If you absolutely need exact per-pixel checks, it's still most efficient to do those checks using precomputed masks, with one bit per pixel. You can test up to 32 pixels in a single instruction this way. Given plenty of memory you could store 8 preshifted copies of each mask, too. It depends how tight you are, and if you've got better things to use the memory for.
 
I guess for complex objects you could pre-calculate collision maps in the form of .col files that take the structure of the following:

Code:
000011110000
000111111000
001111111100
001111111100
000111111000
000011110000

you can see that it creates a circle... you could load all that data into a mutli-dimmesnional array and check the values accordingly. I think anything that can be pre-calculated should be on a system like the 2X. I think complex per-pixel collision detection could be a but much for the 2X and your game might suffer as a result.

Hope that helps
 
Thanks for all the help guys! I will keep you updated. Just implemented multiple layers yesterday. Some bugs to be ironed out now. :(
 
Back
Top