What's a good, simple, 2D rectangles-only collision detection algorithm?

Question

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 1

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.

Answer 2

One simple strategy that sped up detection in an early attempt at a simple 2D game was to maintain a list sorted by the longer dimension.The collision phase consisted of something like this:

for i in 0..n
   j = i+1
   while rect[j].left < rect[i].right
       check for collision in y
       j=j+1
   endwhile 
endfor

Answer 3

Here's a simple algorithm that'll speed things up a little bit and works on axis-aligned rectangles.

Pick one of the axes as the "sorted axis." For this description I'll say the X axis is sorted. Specify each rectangle as two nodes, an "enter" node, and an "exit" node on the sorted axis. The enter nodes must always have a lower value on the axis than the exit nodes.

Create a sorted list of all of the enter and exit points.

Walk the sorted list. As you hit each "enter" node, add it to a list of "entered" rectangles, and then do a brute-force collision detection against all other nodes in the "entered" list. As you hit each "exit" node, remove it from the "entered" list.

You can then walk the reader through an exercise in which the "entered" list is itself sorted on the Y-axis with "enter" and "exit" points on the Y-axis.