# How do I find the point of impact with 2D per-pixel collision detection?

I'm creating a platformer and have implemented per-pixel collision detection. However, this has caused 2 obstacles that I've yet to figure out. The first obstacle, which this question is about, is that I don't know how to efficiently find the point of impact (my other problem will probably be a different question on this StackExchange).

I have my character fall or jump at a given rate in pixels. That is, every frame the character might fall 4 pixels or jump 4 pixels, for instance. If the character falls and intersects an object then the character should land on that object (and vice versa, if they're jumping and hit an object they should start falling again). However, if, for instance, a character falls 4 pixels and this puts them 3 pixels into an object, they'll stop falling but won't be in the proper location. The character should appear to stop at the first pixel of impact.

So, how can I efficiently find the point of impact? I only have a vague idea of only comparing the outline pixels, testing for collision, and incrementing them up or down by one until there's a collision, but it seems like it might be complicated to pull off.

If you want to know the platform, I'm developing using XNA for Windows Phone 7.

• Related, probable dupe (in terms of answers): gamedev.stackexchange.com/questions/2942/… Commented Aug 18, 2011 at 22:48
• @Tetrad, thanks. I hope you can understand why I didn't think to search for a question about missle and terrain collision :P It's not quite the game I'm developing
– Bob
Commented Aug 18, 2011 at 23:00
• Have You considered Box2D physics? Commented Sep 12, 2011 at 6:26
• You might get into problem known as tunneling. Commented Sep 12, 2011 at 6:29
• If you haven’t yet, add “sweep” to your search queries. Dynamic collision detection algorithms often use a sweep parameter to get the earliest collision point. Commented Dec 11, 2011 at 14:08

I've read a really good article before that described how collision detection was implemented in earlier Sonic games.

That article would have been an excellent reference for this thread, but I just can't seem to find it at the moment. If I do I'll update my post. Meanwhile I'll try to take it from memory!

I believe this technique is very interesting and might solve your problems, without needing to change to a physics engine nor let go of per-pixel collision entirely.

Basically what the article described was a tile-based platformer engine where each tile type had per-pixel collision data like this:

But your character only had a limited set of points of contact. For instance in the article I remember there being only 3 pixels near sonic's head (one on the left of the sprite, one in the middle and one on the right) that would be used for collision detection when jumping, 3 pixels near sonic's feet to detect collisions with the floor, and 2 near the middle on each side to detect collisions with walls.

I'll just do a quick mock up of what I recall. Something like (don't rely on the accuracy of my pixel placement, I just made them up):

This way you only need to check for collision using these individual points (which ones depend on the situation, such as jumping or falling) and in case of collision you only need to adjust the sprite based on those points. For instance if one of the upper points collided with some blocked pixel in the ceiling tile, you only needed to bring the sprite down until that spot no longer collided.

Edit

While this is still not the link I originally read, it also mentions the collision points (named sensors) and should give a great deal of information. Read the other sections of the guide too!

http://info.sonicretro.org/SPG:Solid_Tiles

• That leads me to remember when i was younger, like 8 years old and make some games with Multimedia Fusion. We used to use these "sensors" as some bars below, up and by the character. and it managed everything very well! Commented Jan 26, 2012 at 0:42

First of all, I wouldn't go for pixel perfect collision detection in a mobile 2D platform game for obvious performance reasons. These kind of checks are CPU intensive and, unless you perform a broad check to filter separated objects, it'll surely negatively affect your game.

I'd use bounding boxes and/or spheres (depending on your entities shapes). The detection quality would be good enough. You could even use more than one shape to model an entity. Tests between those shapes are easy and you can know points of impact and fix entities positions.

But, if you don't want to implement everything youself, you might want to use Box2DX (C# port of Box2D) and use only the collision detection part of the library.

• Thanks for the link to Box2D, I'll look into it. As for performance, my sprites are very small and "old school", but scaled up so there's not too many pixels to test against. I also first check bounding rectangles and only do per-pixel if the bounds intersect. I do per-pixel because the pixels are so large (being scaled up) that it looks off if they don't interact properly.
– Bob
Commented Jan 25, 2012 at 19:29