Pixel by pixel collision detection

Hello there ...

In the Army Defence Android Game, I had to implement a very simple collision detection method to tell if an enemy or if my tank was hit by a bullet or not. The technique works by finding out if the rectangle that the objects occupy collide with each other. This technique works well in general, and it is very fast, however one drawback of this method is that sometimes the bullet registers a hit when it does not touch the enemy.

A solution to this issue is using pixel by pixel collision detection. This means the game registers a hit if and only if two pixels from the two object are above one another. To implement this method I created byte array for storing what I call "a collision map". Simply put, if there is a visible pixel in the sprite/object texture, then 1 is stored at the corresponding location in the collision map. If there is not, zero is stored instead. 

The first stage in implementing this method is writing a simple function that receives the texture, and extract the collision map for the object. A check on the Alpha value of the pixel is being used to determine if the pixel is visible or not, and hence if the value in the collision map should be 0 or 1. Next every time a the sprite sheet of an object changes, a variable for the collision map that represents the sprite sheet is updated. This helps identifying which collision map to use quickly. Finally the collision is detected. 

For the collision detection, the old collision method is first applied. If no collision happened there, there is no need to perform pixel by pixel check because we are sure there is not pixel collision possible. Otherwise, the program calculates the number of pixels in each object, and selects the one with the fewer pixels. This is done to reduce the number of checks. Next a loop is done on every pixel in the selected object. If the pixel for that object is visible, then the location of the other object's pixel is determined, and if that is visible too, then we got a collision. The method could be summerized as follows:

• If Object1 and Object2 rectangles do not intersect, then return false.
• If number of pixels in Object1 smaller than Object2 then select Object1 otherwise select Object2
• Loop over every pixel location in the selected object
• If the pixel in the selected object is visible then
• Calculate the location of the corresponding pixel for the other object
• If pixel in the other object is visible return true.
• end if
• End loop
• Return false

Hope someone would find this useful.

Take care and have a wonderful day.

Sincerely yours

mkaatr