Games 101 w/ Verax

QUADTREES FOR COLLISION DETECTION:
If you have a game where your collision detection is taking way too much CPU power and is making the game slow, you can use a quadtree to reduce the number of collision detection operations.

A quadtree is basically a variant of a binary tree; it has four child nodes instead of two. The idea of a quadtree is to avoid calculating collisions for objects that cannot possibly collide. This is done by splitting our tree when it reaches x objects. Have a look at this:



Here we have a quadtree that has been split into four, then yet again it has been split into four. The objects in the top left cannot collide with the objects in the bottom left, and therefore we reduce the number of collision detection calls/calculations. Neat, eh?