[SDL] Pixel perfect collision detection

Anders Hansson anders at windev.st
Wed Jun 29 04:23:37 PDT 2005

As a side note: If you don't want to calculate the square root each time
before comparing distance to whatever value, just square the value
compared to. If you're doing a lot of compares this can speed up things
a bit.


Olof Bjarnason wrote:
> If you just want to check if a "circular" PacMan collides with a
> "circular" foe, you might wanna use the distance formula:
> distance = sqrt( (px-fx)*(px-fx) + (py-fy)*(py-fy) );
> .. where (px,py) is the screen location of PacMans center pixel and
> (fx,fy) is the screen location of the foe's center pixel.
> For example, if pacman is 15 pixels wide and the foe 15 too, then they
> collide if their centers are less than or equal 15 pixels away from
> each other:
> if(distance <= 15) {
>   // collision...
> }
> good luck,
> /Olof
> On 6/28/05, Arne Claus <priest at seraphim.info> wrote:
>>How would I do pixel perfect collision detection?
>>As already said numerous times inside this thread - in most cases - don't.
>>But - however - I did some thoughts on that, too, also I never implemented
>>the following Idea:
>>Basically you can use 2color-masks (1 and 0) for your objects.
>>The first thing you do is checking wether those two mask overlap (bounding
>>box intersection).
>>If they do, blit one inside another using AND (I guess you will have to
>>write that yourself - don't know if SDL provides this). Now check your newly
>>created Mask if any Pixel is !=0. If there is -> collision.
>>A z-Pyramid like aproach might speed this up - you can create mipmap like
>>"level of detail masks", meaning you put together blocks of 4 pixels in each
>>step until you end up with a required number of pixels width/height in your
>>image (e.g. 8x8 or sth. similar that's fast enough with brute force). Now
>>you test the smallest map first as described above.
>>On collision go one level deeper but only at the area where the intersection
>>took place(!). If you still have collision at the lowest mask-level ->
>>collision. otherwise - stop where you are.
>>That could speed up things a bit (common hierarchical grid method), although
>>I'm not totally sure about this - depends on the number of operations you
>>However - this method has some downsizes, like speed and the fact, that you
>>can't so easily calculate an accurate penetration depth, but If you have to
>>use it, the above approach might(!) be faster than brute force testing.
>>The best way doing collision detection (IMHO) is using polygons / circles
>>and some kind of hierarchy, like uniform/hierarchical grid or kd-Trees.
>>There are numerous papers on the web about this. The most are 3D, but can be
>>easily derived for 2D-cases (most use 2D examples).
>>SDL mailing list
>>SDL at libsdl.org
> _______________________________________________
> SDL mailing list
> SDL at libsdl.org
> http://www.libsdl.org/mailman/listinfo/sdl

More information about the SDL mailing list