Allegro.cc - Online Community

Allegro.cc Forums » The Depot » Collegro (Allegro Collision Detection Library) Released

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Collegro (Allegro Collision Detection Library) Released
NyanKoneko
Member #5,617
March 2005
avatar

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"}collegro_types.png
{"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"}collegro_ani.png

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.

Felipe Maia
Member #6,190
September 2005
avatar

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

NyanKoneko
Member #5,617
March 2005
avatar

Quote:

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.

Felipe Maia
Member #6,190
September 2005
avatar

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

NyanKoneko
Member #5,617
March 2005
avatar

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. ;D

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.

Jonny Cook
Member #4,055
November 2003

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).

The face of a child can say it all, especially the mouth part of the face.

FMC
Member #4,431
March 2004
avatar

Nice work!

One suggestion:

for checking between two rectangles you use:

1int clgo_collide_bbox_bbox(CLGO_BOUNDING_BOX *bb_a, CLGO_BOUNDING_BOX *bb_b)
2{
3 int left_most_x;
4 int right_most_x;
5 int highest_y;
6 int lowest_y;
7 int combined_height;
8 int combined_width;
9
10 /* Make sure that the bounding boxes are valid. */
11 if(bb_a == NULL || bb_b == NULL)
12 {
13 clgo_error = CLGO_INVALID_PARAMS;
14 return 0;
15 }
16
17 /* First, let's check to see if there is overlap on the y axis. */
18 combined_height = bb_a->height + bb_b->height - 2;
19
20 /* Find the highest y coordinate (lowest number). */
21 if(bb_a->y <= bb_b->y)
22 {
23 highest_y = bb_a->y;
24 }
25 else
26 {
27 highest_y = bb_b->y;
28 }
29
30 /* Find the lowest y coordinate (biggest number). */
31 if(bb_a->y + bb_a->height >= bb_b->y + bb_b->height)
32 {
33 lowest_y = bb_a->y + bb_a->height - 1;
34 }
35 else
36 {
37 lowest_y = bb_b->y + bb_b->height - 1;
38 }
39
40 /* If the combined height is less than the overlapped height, then we have a
41 match. Otherwise, we should quit now. */
42 if(lowest_y - highest_y > combined_height)
43 {
44 return 0; /* No overlap. */
45 }
46
47 /* Now let's check if there's overlap on the x axis. */
48 combined_width = bb_a->width + bb_b->width - 2;
49
50 /* Find the left-most x coordinate. */
51 if(bb_a->x <= bb_b->x)
52 {
53 left_most_x = bb_a->x;
54 }
55 else
56 {
57 left_most_x = bb_b->x;
58 }
59
60 /* Find the right-most x coordinate. */
61 if(bb_a->x + bb_a->width >= bb_b->x + bb_b->width)
62 {
63 right_most_x = bb_a->x + bb_a->width - 1;
64 }
65 else
66 {
67 right_most_x = bb_b->x + bb_b->width - 1;
68 }
69
70 /* Check to see if there's overlap on the x axis as well. */
71 if(right_most_x - left_most_x > combined_width)
72 {
73 return 0; /* No overlap. */
74 }
75
76 /* Tests passes for both the x and y axis. */
77 return 1;
78}

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

1int clgo_collide_bbox_bbox(CLGO_BOUNDING_BOX *bb_a, CLGO_BOUNDING_BOX *bb_b){
2 int x,y, xw, yh; //for bb_a
3 int z,r,zw,zh; //for bb_b
4 
5 x = bb_a->x;
6 y = bb_a->y;
7 xw = x + bb_a->w;
8 yh = y + bb_a->h;
9 
10 z = bb_b->x;
11 r = bb_b->y;
12 zw = x + bb_b->w;
13 rh = y + bb_b->h;
14 
15 if( ((x >= z) && (x <= zw)) || ((z >= x) && (z <= xw)) ){
16 if( ((y >= r) && (y <= rw)) || ((r >= y) && (r <= yw)) ){
17 return COLLISION;
18 }
19 }
20 return NO_COLLISION;
21}

[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites]
Written laws are like spiders' webs, and will, like them, only entangle and hold the poor and weak, while the rich and powerful will easily break through them. -Anacharsis
Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. -Mark Twain

HoHo
Member #4,534
April 2004
avatar

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.

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

NyanKoneko
Member #5,617
March 2005
avatar

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. ;D

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?

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

peanut[5] VS. *(peantut + 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.

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!

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

OICW
Member #4,069
November 2003
avatar

Quote:

I store one bit of a bit mask inside each unsigned char

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?

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

Fladimir da Gorf
Member #1,565
October 2001
avatar

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 :P

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

OICW
Member #4,069
November 2003
avatar

Flad: That's the second thing.

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

NyanKoneko
Member #5,617
March 2005
avatar

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.

Quote:

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 :P

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. =)

Fladimir da Gorf
Member #1,565
October 2001
avatar

Quote:

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?

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).

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

OICW
Member #4,069
November 2003
avatar

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 */

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

NyanKoneko
Member #5,617
March 2005
avatar

Quote:

collision polygons

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. ;D

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. :P

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.

1int clgo_collide_bbox_bbox(CLGO_BOUNDING_BOX *bb_a, CLGO_BOUNDING_BOX *bb_b)
2{
3 int bb_a_x; /* Bounding box a X position. */
4 int bb_a_final_x; /* Bounding box a right-most x postion. */
5 int bb_b_x; /* Bounding box b X position. */
6 int bb_b_final_x; /* Bounding box b right-most x postion. */
7 int bb_a_y; /* Bounding box a Y position. */
8 int bb_a_final_y; /* Bounding box a bottom Y position. */
9 int bb_b_y; /* Bounding box b Y position. */
10 int bb_b_final_y; /* Bounding box b bottom Y position. */
11
12 /* Grab our values. */
13 bb_a_x = bb_a->x;
14 bb_a_final_x = bb_a_x + bb_a->width;
15 bb_b_x = bb_b->x;
16 bb_b_final_x = bb_b_x + bb_b->width;
17 bb_a_y = bb_a->y;
18 bb_a_final_y = bb_a_y + bb_a->height;
19 bb_b_y = bb_b->y;
20 bb_b_final_y = bb_b_y + bb_b->height;
21
22 /* See if the Xes and Ys are both between the other collision box's points. */
23 if(((bb_a_x >= bb_b_x && bb_a_x < bb_b_final_x) || (bb_b_x >= bb_a_x &&
24 bb_b_x < bb_a_final_x)) && ((bb_a_y >= bb_b_y && bb_a_y <
25 bb_b_final_y) || (bb_b_y >= bb_a_y && bb_b_y < bb_a_final_y)))
26 return 1;
27 
28 return 0;
29}

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.

BAF
Member #2,981
December 2002
avatar

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.

Fladimir da Gorf
Member #1,565
October 2001
avatar

Quote:

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.

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

PS. You need a collision library for pong?!

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

BAF
Member #2,981
December 2002
avatar

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. :P

NyanKoneko
Member #5,617
March 2005
avatar

Quote:

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.

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

Carrus85
Member #2,633
August 2002
avatar

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...)

NyanKoneko
Member #5,617
March 2005
avatar

True true true!

Thanks cammus. ;D

  • Committed.

orz
Member #565
August 2000

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.

FMC
Member #4,431
March 2004
avatar

Quote:

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

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 :P

[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites]
Written laws are like spiders' webs, and will, like them, only entangle and hold the poor and weak, while the rich and powerful will easily break through them. -Anacharsis
Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. -Mark Twain

 1   2 


Go to: