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

• 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 corresponding bit to 1.

u8 o.maskX = bit[o.posX / 32] | bit[(o.posX + o.width) / 32];
u8 o.maskY = bit[o.posY / 32] | bit[(o.posY + o.height) / 32];

• In the collision test, simply eliminate all cases where none of their bits are in common.

bool TestCollision(const object* o1, const object* o2)
{
  if((o1->maskX && o2->maskX) == 0)
    return FALSE;
  if((o1->maskY && o2->maskY) == 0)
    return FALSE;
  /* do more advanced collision code here... */
  return TRUE;
}