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

- 11-14-2006g4j31a5Checking intersection of 2 rectangles.
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.

- 11-14-2006ChaosEngine
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?

Code:`point p;`

rect r;

bool bPointInRect = p.x > r.left && p.x < r.right && p.y > r.top && p.bottom;

- 11-14-2006g4j31a5Quote:

Originally Posted by**ChaosEngine**

- 11-14-2006Mario F.
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. - 11-14-2006g4j31a5Quote:

Originally Posted by**Mario F.**

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;

- 11-14-2006Desolation
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

}

}

- 11-14-2006Tonto
- 11-15-2006g4j31a5
Thanks guys. I think I know what I should do now. Thanks alot.

- 11-15-2006CatQuote:

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. - 11-15-2006jafet
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.

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.

- 11-15-2006g4j31a5
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.