Quadtree Demonstration
Collision detection is a regular task in games programming and can be very demanding of the processor. For instance, if we have N balls there are N(N-1)/2 possible collisions so for 500 balls that's 124750 possible collisions which have to be tested for. This number grows very rapidly as we increase the number of balls. The quadtree is a data structure that helps reduce the number of tests.
When a partition has too many balls it creates four child partitions (quadrants). Any ball that fits fully into a child partition is moved into it; any remaining balls stay in the in the original partition.
In this demo the quadtree is updated every frame using the following algorithm -
- change the balls position based on its velocity and elapsed time since last update
- updates the balls position in the tree
- any balls that don't fit the partition are moved up the tree to a partition they fit
- any ball that can fit a child partition is moved to it
- if the partition has too many balls create a subtree , tree depth permitting
- performs collision detection. This does not change the balls position simply its velocity vector.
In all three steps we start with the root partition and recursively visit all child partitions in turn.
Ultimately we have to balance the benefit or reduced collision detection with the need to update the quadtree.