Difference between revisions of "Collision early elimination method"
From MSX Game Library
(Created page with "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 ma...") |
(→Method) |
||
| (12 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
The idea is to create masks that represent the parts of the screen that the object occupies. | 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. | Then simply compare the masks to eliminate any objects that are not in the same part of the screen. | ||
| Line 18: | Line 19: | ||
=== Method === | === 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"> | |
| + | 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]; | ||
| + | </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) // Test X coordinates | ||
| + | return FALSE; | ||
| + | if((o1->maskY & o2->maskY) == 0) // Test Y coordinates | ||
| + | return FALSE; | ||
| + | /* do more advanced collision code here... */ | ||
| + | return TRUE; | ||
| + | } | ||
| + | </syntaxhighlight> | ||
== 8-bit mask == | == 8-bit mask == | ||
| + | This method uses 4-bit X coordinates and 4-bit Y coordinates. | ||
| + | The screen chinks are then 64x64 pixels. | ||
| + | <syntaxhighlight lang="txt"> | ||
| + | 7 6 5 4 3 2 1 0 | ||
| + | │ │ │ │ └──┴──┴──┴── X coordinate mask (0-15) | ||
| + | └──┴──┴──┴────────────── Y coordinate mask (0-15) | ||
| + | </syntaxhighlight> | ||
| + | <syntaxhighlight lang="c"> | ||
| + | u8 o.mask = bit[o.posX / 64] | bit[(o.posX + o.width) / 64] | (bit[o.posY / 64] | bit[(o.posY + o.height) / 64]) << 4; | ||
| + | </syntaxhighlight> | ||
| + | <syntaxhighlight lang="c"> | ||
| + | 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; | ||
| + | } | ||
| + | </syntaxhighlight> | ||
Latest revision as of 22:41, 7 April 2024
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;
}