How can I tell what a rectangle intersects with?

Question

I understand XNA's Rectangle class is rather limited, but surely there is a way to tell what a Rectangle is intersecting with?

If I had Rectangle boundingBox = new Rectangle(stuff here); how would I retrieve what is currently (if there is anything) intersecting boundingBox? Is there any easy method to detect if anything is intersecting it instead of testing with two individual rectangles with boundingBox.intersects()? Similarly, if this is possible, how would I retrieve what rectangle it is colliding with?

If there isn't any easy way of doing it, how would you go about implementing this if you had loads of possible rectangles you want to hit-test?

Answer 1

No, there's no way to do this. What you're looking for is a container, that holds references to rectangles that are insides its bounds. This isn't an easy thing to do when you really think about it.

There is no way for the rectangle object to know any other rectangle object exists, let alone know if one is inside of it or not. However, there is a few data structures that do what you want.

For 2D, which I'm assuming you're working in, there's a structure called a Quadtree. A Quadtree can start as a single container spanning the entire map. Now, as you add collidable objects to your game, you must ( manually ) add those objects to the quadtree. The quadtree can then split up into smaller areas recursively depending on the number of objects in the game. The result is that you can pass the quadtree a rectangle, and it can quite quickly return to you all the rectangles that lie in that area.

However, moving objects around the quadtree is a whole other story. Here's a better explanation: http://en.wikipedia.org/wiki/Quadtree

Of course, I wouldn't recommend over complicating things. Unless you're building a fairly complex game, there's nothing wrong with checking every rectangle with each other.

Answer 2

As far as I know, most programs will separate geometry for rendering from geometry for physics. (This is because rendered models can be incredibly detailed, and hit testing against each polygon will take way longer than say, a couple quadtree intersection tests.)

If you're using a small number of simple rectangles, you could simply test each rectangle against every other rectangle that exists. This is O(n^2), though, so it will scale dramatically as the number of rectangles increases; when performance starts to suffer, you should look into more "organized" collision detection/physics processing schemes.