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

Quote:

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.

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:

Quote:

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

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.

Fladimir da Gorf
Member #1,565
October 2001
avatar

Quote:

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.

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.

Quote:

I decided due to the weird shape of the paddles (candy canes)

Well, then it makes more sense... ;)

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)

orz
Member #565
August 2000

Quote:

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.

Glad to be helpful.

Quote:

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

Quote:

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.

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.

NyanKoneko
Member #5,617
March 2005
avatar

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.

Quote:

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.

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.

OICW
Member #4,069
November 2003
avatar

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

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

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.

OICW
Member #4,069
November 2003
avatar

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.

[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"

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

NyanKoneko
Member #5,617
March 2005
avatar

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.

CGamesPlay
Member #2,559
July 2002
avatar

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

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

NyanKoneko
Member #5,617
March 2005
avatar

Quote:

Can I just not use a pointer?

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

CGamesPlay
Member #2,559
July 2002
avatar

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

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

NyanKoneko
Member #5,617
March 2005
avatar

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.

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

NyanKoneko
Member #5,617
March 2005
avatar

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.

Neil Walker
Member #210
April 2000
avatar

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.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

 1   2 


Go to: