[SDL] Pixel perfect collision detection

Olof Bjarnason olof.bjarnason at gmail.com
Wed Jun 29 03:48:26 PDT 2005


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
> do.
> 
> 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).
> 
> Arne 
> _______________________________________________
> SDL mailing list
> SDL at libsdl.org
> http://www.libsdl.org/mailman/listinfo/sdl
> 
> 
>




More information about the SDL mailing list