Collision early elimination method

Here is a method for fast collision early elimination.

The idea is to create masks that represent the parts of the screen that the object occupies. Then simply compare the masks to eliminate any objects that are not in the same part of the screen.

16-bit mask

In this example, we'll use 16-bit masks (8-bit for X coordinates and 8-bit for Y). The screen is divided into 32x32 pixel tiles (i.e. 8 pieces across the width).

7  6  5  4  3  2  1  0
└──┴──┴──┴──┴──┴──┴──┴── X coordinate mask (0-255)

7  6  5  4  3  2  1  0
└──┴──┴──┴──┴──┴──┴──┴── Y coordinate mask (0-255)

Others format is also possible (see #8-bit mask).

Method

1. After object position has been updated, generate an objet position mask.
   • Divide X coordinate by 32 (value between 0 and 7) and set corresponding bit to 1.
   • Divide X coordinate + object width by 32 (value between 0 and 7) and set corresponding bit to 1.
   • Divide Y coordinate by 32 (value between 0 and 7) and set corresponding bit to 1.
   • Divide Y coordinate + object height by 32 (value between 0 and 7) and set the corresponding bit to 1.

   u8 maskX = bit[posX / 32] | bit[(posX + width) / 32];

u8 maskY = bit[posY / 32] | bit[(posY + width) / 32];