Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

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

Reply to topic
Author Message
  • Joined: 24 Sep 2018
  • Posts: 44
Reply with quote
Pixel Perfect Collision Detection by Testing a Single Bit
Post Posted: Wed Dec 05, 2018 6:56 pm
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.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12510
  • Location: London
Reply with quote
Post Posted: Thu Dec 06, 2018 6:42 am
Could you maybe make some diagrams to explain?
  View user's profile Send private message Visit poster's website
  • Joined: 08 Sep 2018
  • Posts: 75
Reply with quote
Post Posted: Thu Dec 06, 2018 4:49 pm
And show us some code examples
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 415
Reply with quote
Post Posted: Thu Dec 06, 2018 5:02 pm
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.
  View user's profile Send private message
  • Joined: 24 Sep 2018
  • Posts: 44
Reply with quote
Post Posted: Thu Dec 06, 2018 9:21 pm
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.
  View user's profile Send private message Visit poster's website
Reply to topic



Back to the top of this page

Back to SMS Power!