Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm creating a game and I need to detect collisions between a character and some parts of the environment. Since my character's frames are taken from a sprite sheet with a transparent background, I'm wondering how I should go about detecting collisions between a wall and my character only if the colliding parts are non-transparent in both images.

I thought about checking only if part of the rectangle the character is in touches the rectangle a tile is in and comparing the alpha channels, but then I have another choice to make... Either I test every single pixel against every single pixel in the other image and if one is true, I detect a collision. That would be terribly ineficient.

The other option would be to keep a x,y position of the leftmost, rightmost, etc. non-transparent pixel of each image and compare those instead. The problem with this one might be that, for instance, the character's hand could be above a tile (so it would be in a transparent zone of the tile) but a pixel that is not the rightmost could touch part of the tile without being detected. Another problem would be that in different frames, the rightmost, leftmost, etc. pixels might not be at the same position.

Should I not bother with that and just check the collisions on the rectangles? It would be simpler, but I'm afraid people.will feel that there are collisions sometimes that shouldn't happen.

share|improve this question

1 Answer 1

up vote 10 down vote accepted

I've talked about this a few times before (see related answers at the bottom) but I'll repeat myself.

As you can imagine, checking every pixel against every other pixel would be very inefficient, even if you limited those pixels to the rectangle range that is actually intersecting. But like you mentioned, your second option also has its share of problems.

With that in mind, I'd like to drop two suggestions to solve your problem. The first one is just common practice. The one that really matters is the second:

==================================================

Suggestion #1 - Check rectangles first

==================================================

This suggestion is pretty obvious. Instead of always doing a pixel perfect collision check, start by checking if there's a rectangle-rectangle collision:

  • If there is, you'll still need to perform the pixel perfect collision check. In this case it ends up being a little more expensive because of the added rectangle-rectangle collision check.
  • But if there isn't, you can return false and exit right there, because there's no chance of any pixels intersecting.

In practice you'll see a large performance gain from this, because the amount of tiles that are not colliding is probably a lot larger than those that are colliding.

==============================================

Suggestion #2 - Use collision points

==============================================

Instead of checking every pixel in the environment tile against every pixel in the character sprite, define a small number of collision points on your character, and only check against those points. This is the approach used by classic Sonic games (see link at the end for more information).

Here's an example. Considering the following information:

  1. Tile Collision Mask

    enter image description here

    Nothing special here, it's just a mask created from the opacity values of the tile texture.

  2. Character Collision Points

    enter image description here

    Notice how there are 3 collision points at the bottom, 3 at the top, and 2 in the middle, one on each side. The advantage of having separate collision points is that you can use them for different tasks. For instance, the bottom collision points can be used to detect collisions with the floor, the middle collision points can be used to detect collisions with the walls, and the top collision points can be used to detect collisions with the ceiling.

There's also many other tricks that you can perform with this technique. For example, if only one of the bottom collision points is hitting the floor, you can change to an "out of balance" animation because the player must be near a ledge. Or by varying the height of the middle collision points, you can determine which types of slopes or stairs the character can climb.

Bottom line, with this approach you'll reduce from N x M pixel checks to N x 8 (with the example given) which is almost certainly a lot faster.

You can also define different collision points for each frame of the animation. And by the way you can define a collision point simply as an X and Y offset from the character's origin.

=========================================

Related answers and resources

=========================================

share|improve this answer
    
Wow, this is a great answer and it's definitely going to help me a lot. The example is great too. Thanks a ton, I really appreciate it. –  Adam Smith Jun 20 '12 at 0:47
    
How would the data for the collision points be stored? –  keelerjr12 Nov 5 at 18:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.