Forums

Hi; this spins off prior discussions of collision detection while being a bit of a detour — maybe the result is well-known but nobody seemed to have mentioned it, so...

If you can afford it then at a storage cost of ((sprite a width) + (sprite b width)) * ((sprite a height) + (sprite b height)) bits, you can perform a pixel-perfect collision detection between the two sprites by looking up a single bit.

Formally you're going to compute the Minkowski sum of sprite A and the 180 degree rotation of sprite B. But that's unnecessarily wordy, so:

You have a collision is there is any point, A, within sprite a and a corresponding point, B, within sprite b, that are in the same location. Or, to put it another way, A - B = 0.

So what you're going to precompute is the mask that results from a double loop like:

for all points A in a:
for all points B in b:
set bit in mask image at A - B

It'll look like you drew around the outline of a with a rotated copy of b. You can even compute it that way if it's easier.

Here's the clever part: sprites a and b, on screen at locations (a.x, a.y) and (b.x, b.y) currently overlap if the bit within your precomputed mask at (a.x - b.x, a.y - b.y) is set because that means that the images of a and b, shifted according to their current position, had at least one A and B for which A - B = 0.

So if both sprites are 8 pixels by 8 pixels, your precomputed mask occupies 16x16 pixels = 32 bytes. And if you've already gone through your broad phase and included an axis-aligned bounding box test, you already know that the bit you're going to look up is within that 16x16 range. Or the range check is the bounding box check. Whichever way around you want to phrase it.

That also gives you some flexibility in exactly how you want to mask off bits to arrange your 32 bytes — as naively described above, the 16x16 bit mask is centred on (0, 0) so half the coordinates are prima facie negative.

Bonus observation: suppose you found two sprites that were overlapping and wanted to find the minimum amount you'd need to move one or the other so that they were no longer overlapping. Then you'd just find whichever empty bit is closest to the one you tested, and the vector between them is the minimum separation vector.

Precompute that, and you're half way to very low-budget but reasonably convincing physics, upon which it would probably be a digression to expand.

Could you maybe make some diagrams to explain?

And show us some code examples

It seems an interesting concept, but I wonder why you would want pixel perfect collision detection in the first place.

In my games I always go to some lengths to make sure that collision detection always works in the player's favour, being more generous when an enemy touches him and more strict when an enemy is attacked by the player.

Maxim wrote

Could you maybe make some diagrams to explain?

It strikes me with hindsight that in the 2d case, if you don't want to worry about minimum separation distances, you can describe the idea a lot more simply:

If two 8x8 objects, one at position a, one at position b, pass a bounding-box check then:

a - b must be in the range (-7, -7) to (+7, +7) inclusive; and
if you know a - b then you know enough to say whether a collision occurred.

So you can just build a lookup table indexed by a-b.

I guess that's a fairly obvious idea if, unlike me, you're smart enough not to worry about the more formal aspects of it — I got here by mapping the idea back from geometry but if you're doing it discretely in pixels then either way of phrasing it will do.

Obvious enough not to require a diagram?

IllusionOfMana wrote

And show us some code examples

As per the description above, assuming you build the lookup table in a high-level language, something like the following, which is obtusely fixated on making indexing convenient for the Z80:

// i.e. 32 bytes of storage, all explicitly initialised to 0
std::vector<uint8_t> collision_table(32, 0);

for(int x = -7; x <= 7; ++x) {
for(int y = -7; y <= 7; ++y) {
bool does_collide = your_generic_pixel_collision_test(
sprite_a_image,
0, 0, // position of sprite a image
sprite_b_image,
x, y, // position of sprite b image
);

if(does_collide) {
int bit = x & 7;
int bit_index = ((x & 8) << 1) | (y & 15);
collision_table[index >> 3] |= 1 << (index & 7);
}
}
}

Then look up as e.g.:

LD A, (<sprite 1, x position>)
LD B, (<sprite 2, x position>)
SUB B
LD C, A ; so c = x1 - x2
AND 8
ADD A, A
LD D, A ; d = ((x1 - x2) & 8) << 1

LD A, (<sprite 1, y position>)
LD B, (<sprite 2, y position>)
SUB B
AND 15 ; a = ((y1 - y2) & 15)
OR D ; a = ((y1 - y2) & 15) | (((x1 - x2) & 8) << 1)
LD E, A
XOR A
LD D, A ; de = (byte index into 32-byte lookup table)

LD A, C
AND 7
LD L, A
LD H, <top byte of a convenient 256-byte-aligned table of bit masks>
LD A, (HL) ; a = 1, 2, 4, 8, 16, 32, 64 or 128 as per bit to test

LD HL, <address of collision lookup table>
ADD HL, DE
AND (HL)

JR Z, .no_collision

.collision:
; do something

... which is probably suboptimal, being typed extemporaneously.

The lookup table it refers to is just `1, 2, 4, 8, 16, 32, 64, 128`, i.e. from indices to bit masks.

Kagesan wrote

It seems an interesting concept, but I wonder why you would want pixel perfect collision detection in the first place.

Without trying to be physicsy, I think it's good for things like bullets, of any shape, against sprites which are not necessarily boxy.

If being physicsy, you can go back to the Minkowski view of the world and store minimum separation vectors rather than simple collision test bits. You probably want subpixel accuracy so call it two bytes per coordinate in a 4.4 fixed point scheme, 128 total per tile. Physics bonus: if you model the main sprite as a ball then the separation vector will always also be parallel to the surface normal at the point of contact, so you might prefer to store separation as angle + scale.

... and therefore use case #2 is something like a pinball game with 'real' physics.

Author	Message
TomHarte Joined: 24 Sep 2018 Posts: 66	Pixel Perfect Collision Detection by Testing a Single Bit Posted: Wed Dec 05, 2018 6:56 pm
TomHarte Joined: 24 Sep 2018 Posts: 66	Hi; this spins off prior discussions of collision detection while being a bit of a detour — maybe the result is well-known but nobody seemed to have mentioned it, so... If you can afford it then at a storage cost of ((sprite a width) + (sprite b width)) * ((sprite a height) + (sprite b height)) bits, you can perform a pixel-perfect collision detection between the two sprites by looking up a single bit. Formally you're going to compute the Minkowski sum of sprite A and the 180 degree rotation of sprite B. But that's unnecessarily wordy, so: You have a collision is there is any point, A, within sprite a and a corresponding point, B, within sprite b, that are in the same location. Or, to put it another way, A - B = 0. So what you're going to precompute is the mask that results from a double loop like: for all points A in a: for all points B in b: set bit in mask image at A - B It'll look like you drew around the outline of a with a rotated copy of b. You can even compute it that way if it's easier. Here's the clever part: sprites a and b, on screen at locations (a.x, a.y) and (b.x, b.y) currently overlap if the bit within your precomputed mask at (a.x - b.x, a.y - b.y) is set because that means that the images of a and b, shifted according to their current position, had at least one A and B for which A - B = 0. So if both sprites are 8 pixels by 8 pixels, your precomputed mask occupies 16x16 pixels = 32 bytes. And if you've already gone through your broad phase and included an axis-aligned bounding box test, you already know that the bit you're going to look up is within that 16x16 range. Or the range check is the bounding box check. Whichever way around you want to phrase it. That also gives you some flexibility in exactly how you want to mask off bits to arrange your 32 bytes — as naively described above, the 16x16 bit mask is centred on (0, 0) so half the coordinates are prima facie negative. Bonus observation: suppose you found two sprites that were overlapping and wanted to find the minimum amount you'd need to move one or the other so that they were no longer overlapping. Then you'd just find whichever empty bit is closest to the one you tested, and the vector between them is the minimum separation vector. Precompute that, and you're half way to very low-budget but reasonably convincing physics, upon which it would probably be a digression to expand.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14726 Location: London	Posted: Thu Dec 06, 2018 6:42 am
	Could you maybe make some diagrams to explain?

IllusionOfMana Joined: 08 Sep 2018 Posts: 270	Posted: Thu Dec 06, 2018 4:49 pm
IllusionOfMana Joined: 08 Sep 2018 Posts: 270	And show us some code examples

Kagesan Joined: 01 Feb 2014 Posts: 875	Posted: Thu Dec 06, 2018 5:02 pm
Kagesan Joined: 01 Feb 2014 Posts: 875	It seems an interesting concept, but I wonder why you would want pixel perfect collision detection in the first place. In my games I always go to some lengths to make sure that collision detection always works in the player's favour, being more generous when an enemy touches him and more strict when an enemy is attacked by the player.

TomHarte Joined: 24 Sep 2018 Posts: 66	Posted: Thu Dec 06, 2018 9:21 pm
TomHarte Joined: 24 Sep 2018 Posts: 66	Maxim wrote Could you maybe make some diagrams to explain? It strikes me with hindsight that in the 2d case, if you don't want to worry about minimum separation distances, you can describe the idea a lot more simply: If two 8x8 objects, one at position a, one at position b, pass a bounding-box check then: a - b must be in the range (-7, -7) to (+7, +7) inclusive; and if you know a - b then you know enough to say whether a collision occurred. So you can just build a lookup table indexed by a-b. I guess that's a fairly obvious idea if, unlike me, you're smart enough not to worry about the more formal aspects of it — I got here by mapping the idea back from geometry but if you're doing it discretely in pixels then either way of phrasing it will do. Obvious enough not to require a diagram? IllusionOfMana wrote And show us some code examples As per the description above, assuming you build the lookup table in a high-level language, something like the following, which is obtusely fixated on making indexing convenient for the Z80: // i.e. 32 bytes of storage, all explicitly initialised to 0 std::vector<uint8_t> collision_table(32, 0); for(int x = -7; x <= 7; ++x) { for(int y = -7; y <= 7; ++y) { bool does_collide = your_generic_pixel_collision_test( sprite_a_image, 0, 0, // position of sprite a image sprite_b_image, x, y, // position of sprite b image ); if(does_collide) { int bit = x & 7; int bit_index = ((x & 8) << 1) \| (y & 15); collision_table[index >> 3] \|= 1 << (index & 7); } } } Then look up as e.g.: LD A, (<sprite 1, x position>) LD B, (<sprite 2, x position>) SUB B LD C, A ; so c = x1 - x2 AND 8 ADD A, A LD D, A ; d = ((x1 - x2) & 8) << 1 LD A, (<sprite 1, y position>) LD B, (<sprite 2, y position>) SUB B AND 15 ; a = ((y1 - y2) & 15) OR D ; a = ((y1 - y2) & 15) \| (((x1 - x2) & 8) << 1) LD E, A XOR A LD D, A ; de = (byte index into 32-byte lookup table) LD A, C AND 7 LD L, A LD H, <top byte of a convenient 256-byte-aligned table of bit masks> LD A, (HL) ; a = 1, 2, 4, 8, 16, 32, 64 or 128 as per bit to test LD HL, <address of collision lookup table> ADD HL, DE AND (HL) JR Z, .no_collision .collision: ; do something ... which is probably suboptimal, being typed extemporaneously. The lookup table it refers to is just `1, 2, 4, 8, 16, 32, 64, 128`, i.e. from indices to bit masks. Kagesan wrote It seems an interesting concept, but I wonder why you would want pixel perfect collision detection in the first place. Without trying to be physicsy, I think it's good for things like bullets, of any shape, against sprites which are not necessarily boxy. If being physicsy, you can go back to the Minkowski view of the world and store minimum separation vectors rather than simple collision test bits. You probably want subpixel accuracy so call it two bytes per coordinate in a 4.4 fixed point scheme, 128 total per tile. Physics bonus: if you model the main sprite as a ball then the separation vector will always also be parallel to the surface normal at the point of contact, so you might prefer to store separation as angle + scale. ... and therefore use case #2 is something like a pinball game with 'real' physics.

Forums

View topic - Pixel Perfect Collision Detection by Testing a Single Bit