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. In the mask, all parts where the object is located will be set to 1 and the others to 0. 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.

const u8 bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
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) // Test X coordinates
    return FALSE;
  if((o1->maskY & o2->maskY) == 0) // Test Y coordinates
    return FALSE;
  /* do more advanced collision code here... */
  return TRUE;
}

8-bit mask

This method uses 4-bit X coordinates and 4-bit Y coordinates. The screen chinks are then 64x64 pixels.

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

u8 o.mask = bit[o.posX / 64] | bit[(o.posX + o.width) / 64] | (bit[o.posY / 64] | bit[(o.posY + o.height) / 64]) << 4;

bool TestCollision(const object* o1, const object* o2)
{
  u8 mask = o1->mask & o2->mask;
  if((mask & 0x0F) == 0) // Test X coordinates
    return FALSE;
  if((mask & 0xF0) == 0) // Test Y coordinates
    return FALSE;
  /* do more advanced collision code here... */
  return TRUE;
}