Sign in to follow this  
EmilDenVige

Bitmask detection or 2D collision detection

Recommended Posts

Hiyas! I'm Emil. And i have a problem. :P In my game i use directdraw, and it's working very well for me. So far in my collision detection i am just using VERY SIMPLE algorithms (if player.x >= enemy.x and player.x <= enemy.x + enemy.width (And so on, you get the picture)) This probably isn't the best way by far, but it solves my problem nicely. Now if only everything was square.. You see, it so happens i have this picture: And i obviously want collision on it to be only on the visible area, and not in a big square around it all... I'm pretty sure what i want is to learn about bitmask detection, tough i'm not sure. There might be better ways. I can't seem to find any good tutorials or threads on this, so any help would be lovely. Thanks!!

Share this post


Link to post
Share on other sites
It's easy.

1. Calulate the offset of the coordinate (where on that picture do you want to check for hits)
2. Lock the surface
3. Read the pixel at that coordinate
4. If pixel != colorkey then hit else not-hit
5. Unlock surface

/MindWipe

Share this post


Link to post
Share on other sites
Arrr... Okay, i get the basic idea, but
I don't now how to do this really:
3. Read the pixel at that coordinate
4. If pixel != colorkey then hit else not-hit

And what if i have several pixels to hittest, won't this slow my fps down? Thanks matey.

Share this post


Link to post
Share on other sites
If you do this on the surface and do more than a few reads it will slow down. A solution: Keep a second surface (or better, only a simple memory block) with the bitmap data in system memory.

To read a pixel data you need to know the pixel format. There's several out there for ddraw, usually 16bit has X1R5G5B5 and R5G6B5, 24 bit is R8G8B8 and 32bit is X8R8G8B8.
Simply choose one format for the memory block and then calculate the offset in pixels first. Then you need to find the pixels offset in the memory block.

Example for 16bit:

WORD* pBitmapData = xxx (fill in here, pointer to bitmap data);

pBitmapData += xoffset + yoffset * bytesperline / 2;

WORD wPixelValue = *pBitmapData;

Note the WORD buffer as in 16 bit one pixel is two bytes (one WORD). Also, bytesperline is the offset from one line to another. If you take your own memory block it will usually be the same as width, if you use a ddraw surface use the Pitch value you get from Lock. Dividing by 2 since the pointer is already of type WORD and adding bytesperline would jump two lines.

The colorkey is usually a DWORD value, specifying 32bit format. To compare you may need to recalc the read pixel to the colorkey format (or vice versa).

Example for 16bit, X1R5G5B5:

DWORD dwResultingColor =
( ( ( ( wPixelValue & 0x7c00 ) >> 10 ) * 255 / 31 ) << 16 )
+ ( ( ( ( wPixelValue & 0x03e0 ) >> 5 ) * 255 / 31 ) << 8 )
+ ( wPixelValue & 0x001f ) * 255 / 31;


Now you can compare dwResultingColor with the colorkey (looks like 0x00ff00ff in your case).

Share this post


Link to post
Share on other sites
With modern hardware, you usually want to separate gameplay logic (such as collision detection) from rendering as much as possible - the same goes for the data used for gameplay and rendering.

SO, what would I do? -:

A) If I didn't need pixel perfect collision (most games on older platforms never did!), I'd experiment with a bounding box which was *smaller* than the rendered sprite; additionally you could experiment with multiple bounding boxes in a hierarchy to the resolution you require. So you test for collision with the top level bounding box, then work your way down the hierarchy.


*OR*


B) If I did need pixel perfect collision, I'd make a "collision mask".

1) when you create or load your sprite image, create a 2d array of bytes where each one represents a pixel in the sprite. For any transparent pixel, the value should be 0, and for a solid/opaque pixel the value should be 1 (or some other value).

e.g. if your sprite is is 32x32 you'd have:
unsigned char mask[32][32];


you could also use a bitmask for the above if your memory budget is tight (though having a full byte allows you to store other info per pixel such as surface type, and addressing bits complicates the code a tint bit).


2) when you need to test for collision, the first thing to do is test the whole bounding box as you are currently.


3) if there is a collision, with some very simple maths (a few subtracts), you can work out the area of overlap between the two sprites (A, B). I've marked this as O below:
+---------+
| A |
| |
| +---+---------+
| | O | |
+-----+---+ |
| |
| B |
+-------------+



4) Then just compare just the bytes in the mask[][] array which are in the overlap area O.


5) There are variations on this idea, such as:
- attaching masks to a hierarchy of bounding boxes (as those mentioned in method A) and testing masks individually as above.

- storing multiple versions of the mask at increasingly lower resolutions, e.g. 32x32, 16x16, 8x8, 4x4, 2x2. So for the 16x16 mask, each 2x2 block of the original mask is represented by 1 entry of the 16x16 map (if any pixel in the 2x2 block of the mask is solid, then the pixel in the 16x16 mask is set). This is pretty similar to an unrelated algorithm called "Hierarchical Occlusion Map" (HOM).



Although there is D3D support for D3DQUERYTYPE_OCCLUSION asynchronous queries, I still wouldn't use them for gameplay related collision detection.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this