What's a good, simple, 2D rectangles-only collision detection algorithm?
I'm designing a collision detection game tutorial for young adults, so I want this to be as simple as possible to make it easier to explain.
The requirements are very simple. The world is 2D and contains only rectangles (of arbitrary sizes). BSP and even quadtrees seems like it would be overkill (again, the emphasis is on simplicity) but I would like something more efficient than brute forcing through all n(n-1)/2 possible collisions.
2D, rectangles only, and simple.
Can anyone point to an algorithm I can look up? Is a quadtree algorithm what I'm looking for?
EDIT: Also, the rectangles will never be rotated (I'm keeping it simple). And to give you an idea of what scale I'm working at, there will be on the order of a few hundred rectangles running on your typical user's laptop/desktop (less than 5 years old) implemented in Python with Pygame.
Answer
In my experience, all broadphase collision-detection algorithms are relatively subtle and hard to understand. Given how cheap rectangle-collision testing is, I'd structure the lesson using the n^2 algorithm, then as bonus material, maybe introduce the idea of spatial indexing. With fewer than hundreds of rectangles, I'll bet the dumb way is fast enough.
A quadtree would be fine for your purposes, but remember that when you're dealing with non-points, you have to put the rectangle in a node that contains all of the quadrants it intersects. Then, when testing something that's in a low node, you have to test against all the rects in that node and in all of its ancestors!
You might also consider a sort and sweep algorithm, since what you've already got are axis-aligned bounding boxes.