So, I just finished up the last touches, and am ready to to release the beta.

Screenshots of the examples:

{"name":"collegro_types.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/9\/d9b3e52b41c561211886359d1256b224.png","w":643,"h":501,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/9\/d9b3e52b41c561211886359d1256b224"}
{"name":"collegro_ani.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/2\/d2e511b60d5fda3d55abbebf35987744.png","w":644,"h":502,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/2\/d2e511b60d5fda3d55abbebf35987744"}

So far, collegro supports testing between bounding boxes, bounding circles, and bit masks. You can grab a lot of the data from allegro BITMAPs, saving programmers a little bit of time. You can also draw the various collision objects to an allegro BITMAP, including bit masks. It supports custom bit masks as well.

I added some quickie functions for testing if two allegro BITMAPs collide, for example...

I'm sure this function will be well liked:

int clgo_collide_bitmaps (BITMAP *bitmap_a, int blit_x_a, int blit_y_a, BITMAP *bitmap_b, int blit_x_b, int blit_y_b)

The library is C compatable, fully documented, and written inside a single file so you can add it to your projects really easily.

You can read the documentation at:
http://www.playingwithyarn.net/collegro/

And you can download collegro at:
http://www.playingwithyarn.net/?Downloads:Collegro

Pre-compiled Windows binaries are available.

Before releasing 1.0, I want to have collegro tested a bit more, so please download it and use it. I also will want to write more example code and how-tos for the documentation based on questions I recieve. I also will want to include a pre-compiled MSVC library and a linux makefile. But for right now, it should be in a usable state, so have fun. =)

On a side note: I should probably add this to the depot. Should I submit it under the utilities section, or will Matthew add it to the libraries section?

EDIT: Post suggestions / bugs / comments below or on my website's message board.

The question that most people will ask: How fast is it?

In a scale of 1 - 10, 10 being totally optimised, I'd say, 8ish.

So it's pretty fast, but not so fast as to make the code unreadable.

EDIT: To clarify...
For example, it only tests the bits inside an overlapping rectangle of a bit mask and the other collision object.. So it won't test any bits in a bit mask that can't possibly collide.

I also read allegro BITMAPs directly to grab the data for the bit masks.

And obviously, bounding boxes and bounding circles are very fast.

However, on the slower side of things, I added some safety code to help make sure user errors won't cause the program to crash, and I store one bit of a bit mask inside each unsigned char, as opposed to packing a bunch of them into an 8 bit variable. This way, the bit masks are much easier to work with, and the bit masks can store more than 2 values if the user needs them to.

Well, that seems fast enough to me. When I need something more than bounding boxes, I'll be sure to use your library, congratulations.

You still might want to use collegro if you just want to use bounding boxes at first because it'll probably be faster to set up, comes with debugging tools (you can draw the bounding box to the screen), and can test between bounding circles and bit maps later on, if you need it to. =P

Besides, I need people to beta test it.

EDIT: Found one bug involving unsigned ints trying to be ints. Already fixes and will be included in the next release.

Whenever there's...

int overlapping_box_width;
int overlapping_box_height;

It should be...

unsigned int overlapping_box_width;
unsigned int overlapping_box_height;

That's why it's beta.

Congratulations! When I start being productive again I'll most definetally check it out (source included).

The only collision detection library I've used so far is PPCol. It seemed pretty good, but I never did anything serious with it. Perhaps I'll uses Collegro instead now (assuming it's better/faster).

Nice work!

One suggestion:

for checking between two rectangles you use:

but wouldn't this be a little more fast and compact, not sure, just asking...
(untested code)

Also you could declare all local variables that are calculated only once and never changed as constants. It might help compiler to better optimize the code.

Thanks! =)

I am in the middle of finals, but I am totally going to go through the code and make a bunch of minor optimizations. I just wanted to get the beta out then optimize for the next release. =P

Actually, another minor optimization I'm going to pull off is changing the array code so that I increment a pointer instead of using array subscripts all the time.

Example:
peanut[5] VS. *(peanut + size_peanut * 5). Of course for traversing the array, I'd just be incrementing "peanut," so the code would look more like, "peanut = peanut + size_peanut," then de-reference that pointer a bunch of times.

It's a beta, there's a bunch of minor optimizations left to do, and I appreciate your suggestions.

Still, the big O of the algorithms shouldn't change.

EDIT: FMC, your code is faster, thank you. =)

EDIT 2: Also, do you think I should disable NULL testing for pointers? The biggest desire I think people are asking for is speed. It would shave off a comparison in each function, but could possibly cause crashes if the user passes a NULL pointer (which they shouldn't do in the first place?)

EDIT 3: Another optimization idea: I use unsigned chars to store 1s and 0s in a bit mask. If I use ints, it'll use 4 - 8 times as much space, but could be quicker. Think it's worth it?

Depending on how you do it, the compiler may do that automatically for you. But be careful:

Foo *bar;
++bar; // <- increases the pointer by sizeof(*bar), not 1!

Bit field is faster and uses eight times smaller space than storing it in unsigned char. I accept your opinion about multiple values, but I would also implement bit field.

And another note: what about polygon collisions?

Whoah, that must be the hugest function I've seen to perform a bounding box collision... You can do it in 2 lines (4 tests and 4 sums) as I did in the other collision thread

Flad: That's the second thing.

I couldn't sleep very well last night, but that gave me some time to think about how to optimize collegro.

Currently, the only collision tests that do not run in constant time are, of course, the bit map tests.

To answer your question of why not bit pack all the bits into an unsigned char, at least for right now...

1 - Really complicated code. I may be able to test 8 bits at once, but I may need to add several more operations and tests to align the bits, making the increase in speed on certain tests, marginal. However, the code would come close to unreadable.

2 - There are a lot of functions that need to grab one bit at a time. For those functions, storing each bit seperately is actually faster.

3 - The horizontal / vertical flipping flags would be difficult and slower to implement using bit fields. I would have to rebuild and store horizontal, vertially, and horizontally/vertically flipped bit masks in memory all at the same time, at the very least.

4 - Optimizations like that come last, after you get the code working. =P

But here are some ideas that could make some signifigant speed increases...

1) Using MMX, SSE, SSE2, etc.. to test multiple sets of data at once.

My only question would be how portable can the code be? I don't want to force the user to set flags and stuff for different systems.

2) Instead of packing into unsigned chars, pack into unsigned ints. Why test 8 bits at once, when we can test 32 / 64 at once, using the data size the processor likes?

The only draw-back... very complicated code.

It's long, but it's not slow, just a lot of if/else statements. =P I was mainly concerned with writing very understandable code at the time that I wrote it, I already planned on compressing it into a shorter amount of code for the next release anyways. =)

That's what PPCol and other libraries like that do. Personally I like collision polygons best, you can even generate those from images so no extra work for the developer (see my thread about OL's new features).

You can access bits like this:

char *bit_field;
int n;  // how many bits you want

b = (char *)malloc((n/8)*sizeof(char) + 1);  // you have to divide it by 8 to get the number of chars and add there one to avoid memory leaks

// then a single bit can be accessed like this
b[i>>3] /* and some bit operation - reading what's there, setting a bit to 0/1 */

Funny you should mention that. I was going to add that later on, after I finish up with the current tests. =P

EDIT:
Thanks, OICW. That was certainly random, but informative, I think.

EDIT 2: What I decided to do for the release after next (the next release will be just code cleanup and a few bug fixes), I'll keep the unsigned char bit map for quick single pixel access, but add four integer bit masks for collision testing.

EDIT 3: I just want to remind everyone that I know what can be fixed up to go faster. Remember, collegro is UNFINISHED. The whole idea of releasing this beta was to get user feedback on features / suggestions. So, I appreciate suggestions and feedback regarding the api / features / etc, but critisizing unfinished code for not being optimized is just telling me something I already know.

EDIT 4: Since people have been complaining about it, I just wanted to post the final collision box code for now. It should be pretty close to what FMC posted earlier.

EDIT 5: Phew! Just got through optimizing the code. I also fixed some bugs regarding 15 bit image masks. There are a couple functions I want to make inline now, but I have no idea how to do that in standard C. (And no, (static / extern / nothing) inline void func(void) { ... } doesn't seem to work.) Anyone have any ideas other than using a macro?

I'm going to add some distancing functions to collegro, write an example of how to find the distance between a bounding box and/or a bounding circle, and upload version 0.81 by Friday.

XP uses Collegro.

[edit] Found a bug while using collegro too. Not a major one, but your code doesn't play nice with C++. Adding extern "C" around the #include of collegro.h helped. This is necessary, as collegro.c doesn't compile as C++. You may want to add the #ifdef __cplusplus extern "C" {, etc code to collegro.h.

You could still do that all with 4 comparasions and 4 sums...

PS. You need a collision library for pong?!

I didnt need a collision detection library.. but I decided due to the weird shape of the paddles (candy canes) it could benifit from pixel perfect collision detection, then I remembered Collegro, so I decided to try that out, and it worked good, so I kept it.

Excellent. Already added and ready for the next release (which will be shortly after I finish my essay.)

if(((bb_a_x >= bb_b_x && bb_a_x < bb_b_final_x) || (bb_b_x >= bb_a_x && 
      bb_b_x < bb_a_final_x)) && ((bb_a_y >= bb_b_y && bb_a_y < 
      bb_b_final_y) || (bb_b_y >= bb_a_y && bb_b_y < bb_a_final_y)))
      return 1;

  return 0;

You know, if just assume that the function returns true (non-zero) on collision, you can remove an entire branch by doing this instead:

return ((bb_a_x >= bb_b_x && bb_a_x < bb_b_final_x) || (bb_b_x >= bb_a_x && 
      bb_b_x < bb_a_final_x)) && ((bb_a_y >= bb_b_y && bb_a_y < 
      bb_b_final_y) || (bb_b_y >= bb_a_y && bb_b_y < bb_a_final_y));

I have to say though, it looks pretty good (haven't downloaded it yet myself though...)

True true true!

Thanks cammus.

• Committed.

1. Speed isn't really important in pair-based collision detection. Higher-level factors tend to dominate in the real world, like culling possible collision pairs.

2.
Here's the bounding-box collision detection from PPCol

#define check_bb_collision_general(x1,y1,w1,h1,x2,y2,w2,h2) (!( ((x1)>=(x2)+(w2)) || ((x2)>=(x1)+(w1)) || \
                                                                ((y1)>=(y2)+(h2)) || ((y2)>=(y1)+(h1)) )) 

Here's the same from PMASK:

#define check_bb_collision_general(x1,y1,w1,h1,x2,y2,w2,h2) (!( ((x1)>=(x2)+(w2)) || ((x2)>=(x1)+(w1)) || ((y1)>=(y2)+(h2)) || ((y2)>=(y1)+(h1)) ))

edit: the forum code seems to be truncating that line, but it's basically identical to PPCols, except single-line instead of a multiline macro, probably because multiline macros sometimes get bugged when moving code between platforms with different carriage returns (ie dos2unix etc).
(possibly I stole that one from PPCol?)

Anyway, both have 4 comparisons, 4 adds, and 3 logical-booleans-operators.

3.
For pixel-perfect, I expect bitwise is significantly faster than per-pixel-logic, and I suspect that benchmarks under-estimate the real world performance difference, since bitwise based methods use less memory and thus should play nicer when they have to share resources with AI and game logic etc.

4.
I have some code lieing around that tests a bunch of pixel-perfect collision libraries against each other for correctness and speed. If you want I could clean the code slightly and post it here.
I've added Collegro to it. It now tests PMASK, PPCol, Ebox, Ebox2, Molly, Bitmask, and Collegro. PMASK, PPCol, and Bitmask are based upon packed bits and bitwise operations. Molly is based upon Minkowski sums, and Ebox/Ebox2 are based upon a hierarchical data structure.
Collegro passes the correctness test, along with PMASK, PPCol, and Bitmask. The others fail.
PMASK, PPCol, and Bitmask tend to have very similar performance, since they are all based upon bitwise operations. Collegro outperforms the bitwise-operator by up to a factor of 2 or so when the bitmaps are very small (2x2). At 60x60, the bitmask-based libs tend to outperform Collegro by a factor of 3 or 4. At 100x100 the difference rises to a factor of 15 or so. The sprite-size at which the bitwise-based libs and Collegro are equal in performance varies greatly based upon the exact settings used (in terms of sprite shapes, what percentage of the collision checks are overlapping and by how much, etc), but is generally between 15x15 and 40x40.
Even the slowest of the libraries is still plenty fast enough for most any sane purpose - as I said earlier, performance is not as important as people think it is for pair-based collision functions.

Code readability?
I mean you could even just use bb_a->x instead of bb_a_x, and put the whole thing only in the return, no need to declare variables

That's really interesting. At first I was going to rewrite all the code to use bitwise operations, but now I guess it's best to keep the current code for overlaps of 25 x 25 or smaller.

Thank you so much, that's really helpful.

EDIT:

That's how I had it before, but aparently it's faster if you read a value twice or more times from a struct to copy the data to a local variable first. If anyone knows that this is not the case, let me know.

I may want to come up with some quick tests for all objects to determine if there's even a remote possibility of their colliding at all since I assume in real world calculations, 99% of the time, objects won't collide, and when they do, they'll be moved to not collide.

It's not. The fastest way is the same as orz said. The compiler optimizes your code anyways, but it might not be able to compile out unnecessary conditions.

Well, then it makes more sense...

Glad to be helpful.

I expect the version without locals to be faster - there's no function calls between the variable reads, no writes to unknown pointers, and nothing declared volatile, so the compiler shouldn't have trouble optimizing away the redunandant reads. In general, my recommendation is that you just assume the compiler will figure out the little things unless speed is really really REALLY important. And if speed is really really REALLY important, then neither assume nor take someones word for it, but benchmark it personally (though be warned, benchmarking tiny things like that on modern computers is something of a black art... the results may vary with changes made to completely unrelated bits of code, the phase of the moon, and the prime factorization of the world population at the moment... also, optimizing something that small for one processor/compiler combination will tend to make it run slower on other processor/compiler combinations... Hail Eris!).

That sort of thing is best done at a higher level than pair-wise tests, by using "better than O(n^2)" algorithms that use the kind of sorting/indexing to rule out lots of collisions without having to check each pair. The simple-but-effective algorithm most commonly quoted around here looks like this:

void check_n_axi_aligned_bounding_boxes ( int n, BoundBox **bbs ) {
//bbs is sorted, so that bbs<i>->y <= bbs[i+1]->y for all i < n-1
//if it's not, the caller should use a qsort call to make it sorted
//before calling this function
  int i, j;
  for (i = 0; i < n-1; i++) {
    int maxy = bbs<i>.y + bbs<i>.h;
    for (j = i+1; j < n && bbs[j]->y < maxy; j++) {
      if ((bbs<i>->x < bbs[j]->x+bbs[j]->w) && (bbs[j]->x < bbs<i>->x+bbs<i>->w)
        check_pair(bbs<i>, bbs[j]);
    }
  }
}

More complicated versions use tables or trees or other such data structures. If you look at one of the recent versions of PMASK, you'll see the ColList is packaged with it at the moment, and the ColList example program has something like ten thousand asteroids bouncing off of each other in real-time (the exact number of asteroids varies from version to version, and is 8k ATM IIRC), using ColList to check all asteroids to find pairs of asteroids that should be checked with the PMASK pixel-perfect stuff as a second pass. Unfortunately, that sort of higher-level functionality tends to require invasive interfaces, so that games can't use it unless they tie themselves to the library. Speaking of which, I would suggest that you not have world positions stored inside your collision-shape objects. With current scheme, for instance, colliding two objects of the same shape with each other requires two copies of that shape, so that it can have two different positions.

OK, I just uploaded and released 0.82.

Once again, you can grab it here: http://www.playingwithyarn.net/?Downloads:Collegro

Changes include random bug fixes and code alterations suggested earlier in this thread.

Also, I made a lot of optimization on the O(1) functions based on the suggestions made earlier in this thread as well. I included inline versions of many functions (define statements), but kept a function version as well for documentation purposes.

I removed NULL testing on parameters. If the user passes a NULL variable, I'm sure they'll be able to debug the problem. That should speed things up a bit.

I know I say this often, but I can't say it enough, thank you for your feedback, everyone. It's really invaluable. Not only is collegro beginning to take shape, I can honestly say that a large part of that is due to your comments and suggestions.

Consider it done.

EDIT: 0.82 comes with a PPCOL-ish bounding box function that takes raw values (x1, x2...). I'll add another function for bounding circles, and maybe some other functions to help out in this regard for the next release.

EDIT 2: I forgot to mention what I'll be working on for the next release. Besides what I just listed above, I want to add bitwise operations for comparing bit masks. Secondly, I'm going to add some functions to determine the distances between objects.

Once again, feel free to give any suggestions and comments.

Just remembered what I'm currently working on, are there functions for rotating bitmasks/pixelmasks?

Currently, collegro supports the horizontal and vertical flipping of bit masks.

The bit mask structure cointains 4 sets of pre-computed bit-packed arrays to quickly test with horizontal and vertical flippings turned on and off (note that the bitwise operations are not implemented in 0.82). I assumed users would horizontally flip player sprites and what not that requires pixel-perfect accuracy quite often.

It also contains a list of separate unsigned chars for when it's slower to use a bit mask (reading a single bit, for example.) So it's definately possible to add more rotation functions, but it's probably better to leave it up to the user to create a bitmask for each rotation they do ahead of time, if for no other reason, it would be hard to sync up the values between a rotated allegro sprite and the bit mask if you calculate each one independantly.

But there's no reason other than the functions perhaps becoming too complicated for the user to be useful that we can't implement some kind of theta rotation functions into collegro's bit mask functions.

EDIT: Now that I think about it, it might be possible to make a function that rotates and displays an allegro sprite, but at the same time generates a bit mask for it. I'll keep that in mind for the release after next.

I was also thinking about making pixel mask for each frame of the image, but in my project I rotate them on the fly, and creating pixel masks on the fly isn't really fast process.

I'd like to try this out. Before I do, let me ask this: I have a mask that is green and pink. Will collegro be able to handle this? Will it have to make a copy of this mask? I don't think my code will work with it if so. Attached is a sample mask. Pink is solid, IIRC.

My second example shows how to create custom masks. The pink is the solid color, while blue is the non-solid color. You create custom bit masks through a callback function. It's pretty simple.

I'll try it out I'm seeing how much overhead it'll add if I just put the whole thing in my project... The download link for the source is broken, btw.

Wow. It's 2 source files big. That's a huge download Okay, next hour I'll try to add it to my code

[edit]
Will we always be assured that the bcircle_create function will only set the x y and radius? Can I just not use a pointer?

You can use a pointer. =) I justed wanted to make collegro a no-brainer.

Well, a pointer is fine, but I had to write a copy constructor

Okay, collegro really needs the ability to update a small portion of a bitmask in the same manner as the blit function... It makes my game pretty much unusable constantly recreating the collision mask. Oh, I'm recreating it because it's a destroyable earth game.

Right now, the bit mask is only held in an unsigned char array.

To edit a single bit... it would be:

CLGO_BIT_MASK *bit_mask;

bit_mask->entries[y * bit_mask->bb.width + x] = 1 for solid, 0 for transparent.

Good thinking of a feature for a future function though.

EDIT: You can also be more creative and use a series of 1x1 bounding boxes to represent the earth.

And yes, I'm aware that there's a typo in one of the bounding box creation functions, but it'll be fixed in the next version.

I'm not going to go using 1x1 boxes, that's just insane. Now I might steal the alogrithm from EBox if I decide to solve the problem. Right now I just don't worry about the level bitmask and simply check the pixels at the edges of the circle (top, bottom, left, right). Later, if I find this method doesn't work well enough, I'll fix it properly.

If I wasn't in the middle of finals, I'd work with you on improving collegro to find a suitable solution. I'm sure if you have this problem, someone else will in the future as well.

Hello,
Just a minor suggestion, for your bounding box creation from a bitmap, why not add an optional parameter 'margin' so that the size can be reduced easily for each bitmap you give it. This is useful in games where you want the bounding box inside the sprite to allow a small degree of overlap before a collision occurs.