#27961 - Celeryface - Mon Oct 25, 2004 10:35 am
Hello,
Is there a way to do collision detection on the bit maks (where the transparent colour is black and the sprite image is white), and test the collisions on the actual sprite data?
I have it currently checking collisions between sprites using their sprite bounding areas, but I'd like to get a little more accurate if possible.
Thanks!
#27963 - pyros - Mon Oct 25, 2004 1:31 pm
Yes, but it's not entirely simple.
Assuming that a bit is set to one if it is part of the sprite, then if you AND the bitmasks, and the result does not equal zero, then the images overlap.
However:
You must use the corrosponding Y coordinates.
Shift the sprite data depending on the X coordinates.
Remember that this will (obviously) not work for rotated sprites.
I have working code for this, but even i can't understand it too well anymore, so there's not much point posting, but i could p/m it to you if you like.
Basically you need to do something a bit like....
| Code: |
x = left-of-overlap
for y=top-of-overlap to bottom-of-overlap
if (mask[y-sprite1.ycoord] << (x-sprite1.xcoord)
&& mask[y-sprite2.ycoord] ) == 0
then no overlap
else there is an overlap. |
That's off the top of my head, there well could be a mistake or two in there.
#27964 - Celeryface - Mon Oct 25, 2004 2:31 pm
What bit do you have to check for the sprite mask?
Seeing the code would be sweet. Thanks :)
#27981 - pyros - Mon Oct 25, 2004 6:19 pm
| Celeryface wrote: |
| What bit do you have to check for the sprite mask? |
I have no idea what that question is asking.
Perhaps there has been a misunderstanding. The pseudo-code written above describes (accurately i hope) how to check whether two sprite masks overlap (i.e. a collision has occured).
It does this using bit masks, where each bit represents a pixel.
Each mask described is an array. The size of the array is 'equal' to the height of the sprite (mask). Each value of the array contains a row of the sprite mask
Thus, each && checks whether a row of the sprites has 'collided'. This way, you can effectively check up to 32 pixels at a time, and is particularly useful if your sprites are concave.
I had presumed that when you used the terms 'black' and 'white', you meant that bits of the masks were set to '0' and '1' respectively.
#27999 - Celeryface - Mon Oct 25, 2004 9:17 pm
| pyros wrote: |
| Celeryface wrote: | | What bit do you have to check for the sprite mask? |
I have no idea what that question is asking.
Perhaps there has been a misunderstanding. The pseudo-code written above describes (accurately i hope) how to check whether two sprite masks overlap (i.e. a collision has occured).
It does this using bit masks, where each bit represents a pixel.
Each mask described is an array. The size of the array is 'equal' to the height of the sprite (mask). Each value of the array contains a row of the sprite mask
Thus, each && checks whether a row of the sprites has 'collided'. This way, you can effectively check up to 32 pixels at a time, and is particularly useful if your sprites are concave.
I had presumed that when you used the terms 'black' and 'white', you meant that bits of the masks were set to '0' and '1' respectively. |
What I meant was is there a way to detect which part of the sprite is transparent? Is it just a simple check of the transparent colour to see if that pixel is part of the collision data?
Thanks for the help.
#28001 - Lord Graga - Mon Oct 25, 2004 9:50 pm
You could bitcompress your sprites to make a mask and include that binary along with the GFX. That would be a mighty funky way to do it.
#28005 - Celeryface - Mon Oct 25, 2004 11:43 pm
| Lord Graga wrote: |
| You could bitcompress your sprites to make a mask and include that binary along with the GFX. That would be a mighty funky way to do it. |
I've been talking to a programmer who did some PlayStation 1 programming, and he was saying that they used to just switch a bit in the sprite to make the mask and use that data to test for collisions. Anyone hear of similar method on GBA?
#28007 - sajiimori - Tue Oct 26, 2004 12:13 am
You mean checking a single bit in the pixel data? Well, a pixel is transparent if all the bits are 0, so you can't really check just one.
Well, actually I can think of a way you could check only one. If you never use any colors in the first half of the palette besides color 0, then the top bit of each pixel will be 0 if and only if that pixel is transparent. Obviously, that's a total waste of colors.
Either check all the bits of each pixel, or make a seperate buffer with 1 bit per pixel (which is almost always the right choice).
#28009 - DekuTree64 - Tue Oct 26, 2004 2:59 am
| Celeryface wrote: |
| I've been talking to a programmer who did some PlayStation 1 programming, and he was saying that they used to just switch a bit in the sprite to make the mask and use that data to test for collisions. Anyone hear of similar method on GBA? |
Hmm, I don't know for sure what you mean, but it sounds like he's talking about doing a per-pixel check, which is slow.
I'd say go with what everyone else has said and precompute the bitmask for each sprite and store it in ROM.
To give a better explanation of the idea behind it (and for anyone else here who would like to know), say your sprite looks like this:
| Code: |
---XX---
--XXXX--
-XXXXXX-
XXXXXXXX |
Where -'s are transparent (color 0) and X's are any other color. Then your bitmasks would look like this:
| Code: |
0x18
0x3C
0x7E
0xFF |
On the first one, bits 3 and 4 are set (the middle 2 bits, corresponding to the middle 2 pixels in the picture), then the second has bits 2, 3, 4 and 5 set, and so on.
Then say you have 2 of those sprites overlapping a little, we'll say one is at position (0,1) and the other is at (4, 0), then they look like this:
| Code: |
-------OO-------
---XX-OOOO------
--XXX#OOOOO-----
-XXX###OOOOO----
XXXXXXXX-------- |
Then to figure that they're overlapping using the bitmasks, take the third row from the top here, where there's one pixel of overlap. If you count the rows from the top of each sprite, row 1 of the X sprite is overlapping row 2 of the O sprite. Go up to the bitmasks we made before and you see that row 1 is 0x3C (X's mask), and row 2 is 0x7E (O's mask). Since O is 4 pixels to the right of X, we shift O's mask right 4 bits and get 0x07. Then AND them together:
0x07 & 0x3C = 0x40
It's not 0, meaning that some bits of X's mask overlapped with the bits of O's mask, so they're overlapping.
Once you know something overlaps, there's really no need to continue checking, so just bail now and report the collision.
Just incase you're curious though, if you did continue and checked the row with 3 pixels of overlap, you'd get mask row 2 and mask row 3, which are 0x7E and 0xFF. Then shift O's mask right again, to get 0x0F, AND with 0x7E, to get 0x0E. 3 bits set, corresponding to the 3 pixels (not that it matters, all we care is that it's not 0).
You can also make O the 'main' sprite, and shift X relative to it, so shift X's mask left 4 bits instead. So for this row, it would be 0x7E<<4, or 0xE0, & 0xFF, which is still 0xE0. Both show that they're overlapping just the same, so it doesn't matter which mask you shift and which one you don't, as long as you shift in the right direction.
I wouldn't suggest trying this on sprites wider than 32 pixels though, since GBA only has 32-bit integers, and doing it in multiple strips could get very confusing.
Well, I guess you could use an unsigned long long to make the compiler do the fancy shifting work for you, but it'd still be a lot slower.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#28016 - Gene Ostrowski - Tue Oct 26, 2004 4:57 am
Although I know it's what you were asking for, I'm wondering if per-pixel collision detection is the best approach for what you are trying to solve.
Unless it's done in hardware for you, I cannot imagine a scenario where you'd really want to do this, unless you have a very specific need for it, and even then it would be questionable.
Hardware collision detection is a great way for a system to perform this CPU intensive process for you, and is good for systems that don't have the CPU to spare, but it's actually a bad thing: collision detection is a "game-logic" function, not a "presentation" function. Emulate this HW pixel collision via software and you just tied your game logic to the display, which is never a good thing.
I remember a certain video game from the old days that had robots with 2 pixel transparent necks. The player's missile was two pixels thick, and it was fun to watch your missle fly right through the transparent "slot" in the robot's neck if you lined it up right. Weeee!
that said, if you decide you still need it, do what DekuTree said. Make sure you still use your bounding boxes for your initial check, and clip it to the overlap region to minimize the amount of pixel checking you need to perform. Plus, if you know something about the shape of the objects in question or the "direction" it's traveling, you may be able to use this to speed up your checking (e.g. if a missile hits hits a ship from the upper left, begin your loop with the lower right corner of the overlap region, which is likely to be where the collision will register first).
_________________
------------------
Gene Ostrowski
#28027 - Celeryface - Tue Oct 26, 2004 10:04 am
Thanks for the explaination, DekuTree64.
Is this the ideal way to do collision detection on the GBA, or is there a simpler and just-as-effective way?
#28029 - col - Tue Oct 26, 2004 10:40 am
| Celeryface wrote: |
Thanks for the explaination, DekuTree64.
Is this the ideal way to do collision detection on the GBA, or is there a simpler and just-as-effective way? |
There is no one 'ideal way'
The best way to detect collisions between entities depends on the game design specs.
One thing for sure: mask based 'pixel perfect' detection is very unlikely to be the ideal way whatever the application.
Apart from being slow, and the difficulty to catching the 'missile through neck' issue that Gene described, mask based detection has other problems...
When your player character jumps, and one pixel of his big hair touches one pixel of a baddies loose clothing, to you really want a collision - I wouldn't.
The mask technique also makes it very tricky to (efficiently) determine the point and time of contact between two entities. This is often necessary when developing your collision response code - which is usually much more hassle than the detection code.
A better alternative is to use geometric primitives such as circles and/or rectangles.
If you want more detail than a rectangle or square can give, use an arrangement of multiple primitives.
(On any reasonable sized project you would really need some sort of visual editing tool so that you can easily build and edit these collision maps...)
HTH
Col
#28031 - Celeryface - Tue Oct 26, 2004 11:22 am
| col wrote: |
| Celeryface wrote: | Thanks for the explaination, DekuTree64.
Is this the ideal way to do collision detection on the GBA, or is there a simpler and just-as-effective way? |
There is no one 'ideal way'
The best way to detect collisions between entities depends on the game design specs.
One thing for sure: mask based 'pixel perfect' detection is very unlikely to be the ideal way whatever the application.
Apart from being slow, and the difficulty to catching the 'missile through neck' issue that Gene described, mask based detection has other problems...
When your player character jumps, and one pixel of his big hair touches one pixel of a baddies loose clothing, to you really want a collision - I wouldn't.
The mask technique also makes it very tricky to (efficiently) determine the point and time of contact between two entities. This is often necessary when developing your collision response code - which is usually much more hassle than the detection code.
A better alternative is to use geometric primitives such as circles and/or rectangles.
If you want more detail than a rectangle or square can give, use an arrangement of multiple primitives.
(On any reasonable sized project you would really need some sort of visual editing tool so that you can easily build and edit these collision maps...)
HTH
Col |
I currently have it working with the sprite bounding box (the size of the sprite that was set when loaded into the OAM). You just gave me an idea on possibly just shrinking down the size of the bounding box I use to test collisions per sprite. A rectangle or a smaller square might work. :)
#28045 - Gene Ostrowski - Tue Oct 26, 2004 3:48 pm
I always use a smaller bounding box for my collisions, even if the sprite takes up the entire square (well, of course there are special situations...)
Think of the two possible scenarios:
1) Box is too big: Hair pixel touches clothing pixel. Player yells "No Way! That guy didn't even touch me!". He then goes to play a different game that seems more fair.
2) Box is smaller. Missile slides right along your ship, slightly overlapping, but you don't explode. "Holy batshite! That was soooo close!". Heart pounds. Excitement ensues.
_________________
------------------
Gene Ostrowski
#28073 - Abscissa - Tue Oct 26, 2004 6:38 pm
| Gene Ostrowski wrote: |
I always use a smaller bounding box for my collisions, even if the sprite takes up the entire square (well, of course there are special situations...)
Think of the two possible scenarios:
1) Box is too big: Hair pixel touches clothing pixel. Player yells "No Way! That guy didn't even touch me!". He then goes to play a different game that seems more fair.
2) Box is smaller. Missile slides right along your ship, slightly overlapping, but you don't explode. "Holy batshite! That was soooo close!". Heart pounds. Excitement ensues. |
Of course, you don't want to make the boxes TOO small, or the player will get annoyed that "Hey, I shot that dang enemy! Why didn't it die?? That's not fair!"