View source for 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).
<syntaxhighlight lang="txt">
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)
</syntaxhighlight>
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.
<syntaxhighlight lang="c">
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];
</syntaxhighlight>
* In the collision test, simply eliminate all cases where none of their bits are in common.
<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

== 8-bit mask ==