Game Development Reference
In-Depth Information
Figure 7.14
A quadtree, where letters represent objects in the world.
When it's time to do the collision check, the code would first check which of the
original quarters intersect against the player, potentially eliminating three fourths
of the objects instantly. Then a recursive algorithm could continue testing until it
finds all of the nodes that potentially intersect with the player. Once there's only a
handful of objects left, they could each be tested against the player using the nor-
mal collision checks.
A quadtree isn't the only partitioning method available; there are others, including
binary spatial portioning (BSP) and octrees (which are the 3D version of
quadtrees).Mostofthealgorithmspartitiontheworldspatially,butotherspartition
it with some other grouping heuristic. Partitioning algorithms could easily be an
entire chapter in a topic, and it turns out there are multiple chapters on this topic
in the aforementioned
Real-time Collision Detection
.
