Hi, I'm planning to use a dirty rectangle method to blit screen with SDL. Everything seems fine except if there were intersecting sprites. So, can anybody tell me how to detect intersection between 2 rectangles (SDL_Rect)? Thanks in advance.
Printable View
Hi, I'm planning to use a dirty rectangle method to blit screen with SDL. Everything seems fine except if there were intersecting sprites. So, can anybody tell me how to detect intersection between 2 rectangles (SDL_Rect)? Thanks in advance.
do you want the intersected rectangle or just to test if they actually intersect?
if it's the latter, it's pretty easy. how would you test if a point is in a rectangle with corners top, left, bottom and right?
figure the rest out from there.Code:point p;
rect r;
bool bPointInRect = p.x > r.left && p.x < r.right && p.y > r.top && p.bottom;
Yeah, I just want to check whether they're intersected or not. And for the code, that's what I had in mind too. But it seemed too costly because it means I have to check every for corners of the rectangle. Say for example, I have 100 sprites = 100 rectangles. Every loop I'll have to check 4 points' intersections to each other sprites (4 * 99). And this will be done for each rectangles (4*99*100). Is there any other optimized solution or is it the only way to do it? Thanks a lot for the reply.Quote:
Originally Posted by ChaosEngine
The advantage of the method ChaosEngine gave you is that you will not really be doing calculations of 4 points on many of them.
Short-circuit evaluation will guarantee that you will be doing less calculations.
But I still have to call it for every corners of the rectangle, right? So it probably will be like this:Quote:
Originally Posted by Mario F.
BTW, I've noticed something. For every rectangles, I don't have to make a loop to check all 100 of 'em. E.g. if I've checked rectangle A for every other rectangle's intersection, I don't have to check whether B is intersected with A in rectangle B's turn.Code:rect r,p;
bool bRectInRectTopLeft = p.left > r.left && p.left < r.right && p.top > r.top && p.top < r.bottom;
bool bRectInRectTopRight = p.right > r.left && p.right < r.right && p.top > r.top && p.top < r.bottom;
bool bRectInRectBottomLeft = p.left > r.left && p.left < r.right && p.bottom > r.top && p.botom < r.bottom;
bool bRectInRectBotomRight = p.right > r.left && p.right < r.right && p.bottom > r.top && p.bottom < r.bottom;
bool bRectInRect = bRectInRectTopLeft || bRectInRectTopRight || bRectInRectBottomLeft || bRectInRectBotomRight;
This is pretty much what you want:
Code:for(int i = 0; i < 100; i++) {
for(int j = i + 1; j < 100; j++) {
// collision detection
}
}
Thanks guys. I think I know what I should do now. Thanks alot.
There are a vast number of optimizations, but a lot depends on how specific you want to be. In general the more assumptions you are allowed to make about sprite size, sprite motion, etc. the easier it is to make a highly optimized, very specific algorithm.Quote:
Originally Posted by g4j31a5
Space Invaders would be one game in which you can make a very efficient collision algorithm because:
1. You have a maximum sprite size,
2. The player ship has no y-axis mobility,
3. The bullets move in one direction with one speed,
4. The monsters likewise move all in the same pattern with the same speed.
You could optimize the algorithm in this case by sorting the list of bullets and the list of monsters by y-value (or, more likely, you create the lists presorted). You only do collision testing on sprites that are within the narrow range of y-values that could conceivably overlap the player sprite. The motion of the bullets and monsters also can never cause the list to need resorting.
Try sorting rectangles by orthogonal coordinates. If rect[X] does not intersect rect[X + 1] on the Y-axis, you can safely assume rect[X + 2] will not intersect rect[X] as well. This can speed up your algorithm by an order of magnitude if you don't expect many collisions at a time (eg. you're checking for collisions in a game every frame).
The downside is that you need to sort the rectangles four times for each direction (decreasing X, increasing X, decreasing Y, increasing Y). The upside is that you can just use a std::map for this, which means you now get best-case O(n) amortized collision detection per frame.
Yeah, I like to ramble. Here's (possibly slightly different from the above) pseudocode.
Hope this helps.Code:sort(rectangles by left edge, right to left) //or iterate a pre-filled ordered tree, like std::map
for i = 0, i in sorted_rects.size, ++i
for j = i + 1, j in sorted_rects.size, ++j
if sorted_rects[i].right_edge < sorted_rects[j].left_edge
//no collision detected in this dimension,
//and sorted_rects[i] is not going to cross subsequent sorted_rects from j onwards
break; //this part is what makes the algorithm fast
else //intersect in this dimension, further checking
if collision_check(sorted_rects[i], sorted_rects[j])
//collision found, deal with it
//don't break, check the next rectangle
//repeat for three other edges
//remember to reverse sorting criteria, comparisons, etc etc.
Thanks. But I'm not using the rectangle intersection checking for collision detection because I didn't need it just yet. I needed it for blitting the sprites on the back buffer surface with a dirty rectangles algorithm (only blitting the sprites that changed). So rather than blitting the background and all the current sprites, I'll blit only the rectangles that changed. But if the dirty sprites intersect other clean sprites, I have to mark them dirty too so they will be updated also. But thanks anyway. I'll use a collision detection later if I develop games that need it such as Tetris or Raiden clones.