Pixel Collision Tracing

Question

I have a character that says 20 by 10 pixels big, and I have a pixel-based conflict map (think worms).

What is the best way to track a character’s collision at a given speed of more than 1 pixel per frame. Is there a better solution than repeating through each pixel along the velocity vector?

I do this in Lua (Love 2D), but a general solution would be ideal.

Answer 1

I would combine a collision with a bounding box and a pixel perfect collision.

Thus, all objects in your game will have bounding rectangles, but only frames equal to the width and height of your sprite. Use this as a first level collision test. After that, and you have a collision, use the collision maps to get a finer level of detail.

This optimization will help speed up and add flexibility to the engine so that not all collisions need to be perfect for pixels.

As for the real perfect pixel collision algorithm, what you described will work. However, if you are going for speed, you can try the following:

come up with a bitmask for each sprite (for example, 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 from a smaller bit mask of the same size and larger and “shift” it by the difference in position between the sprites.

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

Answer 2

Your solution is the simplest - iterate over each pixel.

Just make sure you check only the “new” pixels at each iteration.

Suppose a character moves left and right:

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

At each iteration along the movement, there is a slight pixel difference for validation; only those designated as “new” need exposure testing. Check them, and if there is no collision, continue driving. You can use this to optimize a lot of calculations.