Pixel Collision Tracing

Question

I have a character that's say, 20 by 10 pixels large and I have a collision map based on pixels (think worms).

What's the best way to trace collision for the character given a velocity greater than 1 pixel per frame. Is there a solution better than iterating through each pixel along the velocity vector?

I'm doing this in Lua (Love 2D) but a generic solution would be ideal.

Answer 1

I would combine bounding box collision and pixel perfection collision.

So all entities in your game would have bounding boxes, just frames equal to the width and height of your sprite. Use this as your first level collision test. After this is done, and you have a collision, then use the collision maps to get a finer level of detail.

This optimization is going to help with speed, and adds the flexibility to the engine that not all collisions have to be pixel perfect.

As for the actual pixel perfect collision algorithm, what you describe would work. However, if you are going for speed, you might want to try this:

come up with a bitmask for each sprite (like a pixel map, but only one bit per pixel) for example:

00000000
00100000
01100000
01110000

when one sprite collides with another, create a new bitmask out of the smaller bitmask of the same size of the larger one, and 'offset' it by the difference in position between sprites.

Once this is done, bit-wise 'and' all the bytes in these two masks. If any byte result > 0, you have a collision.

Answer 2

Your solution is the simplest one - iterate over each pixel.

Just make sure that you only check the "new" pixels on each iteration.

Say the character is moving to the right and down at the same time:

*****   .....       .....        * = "Present"
*****   .*****      .****#       . = "Old and now empty"
*****   .*****  =>  .****#        # = "New"; check these on iteration 2
*****   .*****      .****#
         *****       #####

It. 1   It. 2      "New" pixels

On each iteration along the movement there's little difference on the pixels to check; only the ones marked as "new" need checking for impact. Check on those, and if there's no collision, continue moving. You can use that to optimize away lots of calculations.