SpatialHash_for_Pygame — wiki
This class is very fast compared to the Quadtree I was using in Gummworld2. I solved some of the problems and limitations the original author encountered, and I found it suitable for a high quantity of mobile objects. In stress tests I had around 600 objects / 2000 collision checks going at 30 fps, a scenario which would require nearly 400K brute force collision checks.
It's got a builtin optional collision check (see _extended_collided()) to support fast custom shape1-vs-shape2 and pixel-perfect collisions.
The intersect_*() methods are ideal for tile culling.
The Gummworld2 "tiled2" branch has some better demos than the one in __main__ here.
Errrrk. Sorry, I guess there is a size limit to wiki pages or something. The editor is truncating my input. The full source is available here, or you can SVN the repo at the address above.