I'm creating a scrolling shooter and I need a pixel-perfect collision detection algorithm for bullet-to-obstacle collisions. I started creating one and tested it and it didn't work at all. (ouchies) I think I went about it the entirely wrong way. Here's what I came up with.

I figured that first, I'd obtain the bounding boxes for the sprites. The bounding boxes are at a 20% decreased size. Next I'd check to see if there is a bounding box collision. If there is, then I'd start testing the non-transparent pixels in the bullet against the non-transparent pixels in the obstacle. If they were in the same spot, then there was a collision. But I'm starting to think I thought wrong haha.

Here's the code I came up with. Please scrutinize at will if need be.

Your method, although a nice idea, is way too slow. Instead, have a look at the bitmask collision detection library. It works, it's fast, it's free, you just add it to your projects and it will let you get on with coding the rest of your game.

Thanks. I had a feeling it was going to be way to slow. (all those for loops... ick!!!)

Onto experimenting with BitMask. After reading and pondering over the very vague usage instructions, I've come to terms with this:

Basically, with BitMask, I create BitMasks for the sprites. Then for collisions, I use the BitMasks (BitMask functions) rather than the sprites themselves. Is that about right?

Any pointers on how to get started using BitMask would be really helpful because I've got this weird feeling that I'm going to have to rewrite a lot of stuff in my code. (actually the more correct term would be re-adapt the code but that's still a pain)

From memory, there is better much documentation in the download file than there is on the web page.

Yes, you create a bitmask from the sprite image you have, and you pass the two bitmasks you want to test for a collision, plus the offsets between the two sprites.

I'll provide some sample code when I get home later today, along with a small function I wrote for the library which takes an Allegro bitmap and returns the bitmask.

[edit]
I've attached my updated version of the bitmask library, which includes the function to create a bitmask from an Allegro bitmap.

Sample code:

// Just some 'position' variables for the example
int x1 = 100, , y1 = 100, x2 = 120, y2 = 101;

// to create the bitmasks from a bitmaps
BITMAP* bmp1 = load_bitmap("image1.bmp", NULL);
BITMAP* bmp2 = load_bitmap("image2.bmp", NULL);
bitmaks_t* mask1 = bitmask_new(bmp1);
bitmaks_t* mask2 = bitmask_new(bmp2);

// and for collision detection
bitmask_overlap(mask1, mask2, x1-x2, y1-y2)

Oh, and my memory failed me. The documentation within the orignal code wasn't much better than the web site.
[/edit]

Here's a hint. As well as getting the collision-detection to work as fast as possible, try working on ways to reduce the number of collisons that need to take place. One way of doing it is to divide the world into sectors and only test for collisions of objects in the same sector (in two dimensions, if the minimum sector-size is no smaller than the largest object you want to test for collisions, an object can be in a maximum of four sectors).

AE.

Hes already doing a bounding box test first, which will be more effective then using sector divisions.

Andrei Ellman is referring to higher level collision detection, i.e. the algorithm for figuring out which objects get checked at all. It can be (if the number of objects is large enough) far faster than a simple bounding box implementation that checks all bounding boxes against all other bounding boxes.

Bounding box is so fast anyway...

If you wanted to get faster I would just convert to circles. Its probably faster anyway (pointer lookups and list management can be sloooow). And keeping everything sorted would be a bigger drain.

Sectoring is good for stuff like MMORPGs and crap. Or if you just have an unbelievable amount of units or infinite terrain.

You know something, that sounds interesting and I've never thought of using those at all. And considering the fact that I'm still in expiremental stages with the game, I don't see the harm in going back and using a bounding circle rather than a bounding rectangle.

Plus I'm having some trouble getting used to using BitMask. I'm not sure if I'm supposed to compile the BitMask files and link an object file or what because just including the header file, it doesn't solve the linker errors.

xmltorrent, I don't understand the problem you have with the bitmask functions. I've added the two files (the ones I attached in an earlier post) to my projects, and included the header file in every class that uses a bitmask type or function. No problems.

What errors are you getting, and are you including the bitmask files in your project (attach your file(s) if it need be)?

Optimisation isn't just about creating the fastest collision-detection algorithm possible, but also about deciding on whether or not the collision-detections need to take place in the first place.

AE.

How very profound

The linker says there's an undefined reference to bitmask_new, the function you posted in your sample block above.

EDIT:
Which I know what that means but I can't seem to come up with where that function came from or it's equivalent. It's not listed anywhere in the header or source file for BitMask.

Hence the reason I'm trying to get as fast as I can with the collision-detections because they kinda HAVE to happen. ^_^

Are you sure you know what it means?

It means you're using the bitmask header and source files from the web-site, and not those attached to my second post .

Haha Whoops. I just noticed that attachment icon at the top of the post haha. My bad.

ummmm I can't download the attachment. I click on the icon and it's not doing anything at all.

EDIT:
Nevermind, I got it to work. I think I just need to go back to bed today.

n00b:P;D

Haha

EDIT:

I had to make a slight modification to your function. The for loops in bitmask_new function were picked up as being declared outside C99. I just declared the counter variables as local variables in the function and went from there. Just thought you might want to know that. ^_^

EDIT 2:

Haha Another problem has arisen. I think it might just be my brain not working right today or what but I'll explain.

The sprites that I'm using BitMask for are all animated. Now my first plan of attack was to create a BitMask for each frame of animation then when I perform my collision detection, I loop through all the BitMasks for each frame and perform checking on the other sprites BitMasks. However, while the program runs perfectly fine, it always says that there is a collision with an enemy plane when I know that the player plane isn't anywhere near the enemy plane when the program starts. So I'm guessing that another method is needed. Pondering.....

Ta. I probably won't change my code, as I'm developing in C++, which doesn't kick up about it.

Heh, I just spotted some redundent code in the function ("temp->w = w;" and "temp->h = h").

argh!!!

What values should I use for the xoffset and yoffset for bitmask? I have a xoffset and yoffset value for my sprite struct but they don't seem to work.

What he meant by that was that when you have thousands of objects for the level then having a fast collision function is not much use. Much more useful would be to find out those few things you have to collide with and only check those.

E.g using a quadtree could tell you what other objects are near the object you need to collide with. Using the same way you can also find out the objects you have on screen. Without any kind of space partitioning you will have to ton N^2 tests whereas with finding only objects on screen you will most likely cut that down to a fraction of it.

When you also use quadtree to find objects near the one you are colliding with instead of colliding all the objects on screen it can very easily be that you only have to make only a few collision tests per frame. Finding those few collision detections will save a lot more time than making your collision code 10x faster. I bet even your own ugly version would be good enough with decent partitionig scheme.

The xOffset and yOffset are just the x and y differences between the two sprites of the bitmasks you are passing (as per my sample code).

If you still have trouble, post the code.

bllawrgle....

Okay. Here's what I have for the player initialization function: (displays the xoffset and yoffset values)

This is where I'm totally lost at. Like I used those values for bounding box collisions but now I'm not sure how to accomidate those values to BitMask.