|
This thread is locked; no one can reply to it. |
1
2
|
Collegro (Allegro Collision Detection Library) Released |
NyanKoneko
Member #5,617
March 2005
|
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"} 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: 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: And you can download collegro at: 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
|
The question that most people will ask: How fast is it? |
NyanKoneko
Member #5,617
March 2005
|
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... 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
|
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
|
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; It should be... unsigned int overlapping_box_width; 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
|
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...
[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites] |
HoHo
Member #4,534
April 2004
|
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. __________ |
NyanKoneko
Member #5,617
March 2005
|
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: 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? ----------------- |
Kitty Cat
Member #2,815
October 2002
|
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!
-- |
OICW
Member #4,069
November 2003
|
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] |
Fladimir da Gorf
Member #1,565
October 2001
|
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 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
|
Flad: That's the second thing. [My website][CppReference][Pixelate][Allegators worldwide][Who's online] |
NyanKoneko
Member #5,617
March 2005
|
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 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
|
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
|
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] |
NyanKoneko
Member #5,617
March 2005
|
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: 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. ----------------- |
BAF
Member #2,981
December 2002
|
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
|
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... 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
|
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. |
NyanKoneko
Member #5,617
March 2005
|
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
|
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
|
True true true! Thanks cammus.
----------------- |
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. #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). Anyway, both have 4 comparisons, 4 adds, and 3 logical-booleans-operators. 3. 4. |
FMC
Member #4,431
March 2004
|
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? [FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites] |
|
1
2
|