Efficient Spatial Collision Detection

Detecting collisions among many moving blobs in 2D gets expensive fast: checking every pair each frame is $O(n^2)$. A quad-tree brings that down by only comparing blobs that share a region of space.

On every tick, CollisionGUI rebuilds a PointQuadtree<Blob> over the whole 800×600 field. Each node holds one blob, the rectangle it governs, and up to four children c1–c4, one per quadrant; insert sends a new blob down the quadrant its coordinates fall in, subdividing as it descends. Blobs near each other in space therefore land in the same or adjacent cells.

Finding collisions then means asking each blob's neighborhood through findInCircle(x, y, radius). The search prunes any node whose rectangle fails an intersectsCircle test and collects the rest with isInCircle, so it walks a shallow path of cells rather than the whole population. More than one hit inside a blob's radius flags a collision, and the handler colors the culprits red, destroys them, or freezes them in place. Each query touches roughly $O(\log n)$ cells, so a frame costs about $O(n\log n)$ instead of $O(n^2)$, and rebuilding the tree each tick keeps it accurate as the blobs move.