A data structure for organizing objects based on their locations in a two-dimensional space.
- iOS 10.0+
- macOS 10.12+
- tvOS 10.0+
A quadtree manages its structure to optimize for spatial searches—unlike a basic data structure such as an array or dictionary, a quadtree can find all elements occupying a specific position or region very quickly. The quadtree partitioning strategy divides space into four quadrants at each level, as illustrated in Figure 1. When a quadrant contains more than one object, the tree subdivides that region into four smaller quadrants, adding a level to the tree.
Quadtrees can be useful for many tasks in game design. For example:
Deciding which game characters are close enough to each other for interaction
Deciding which portions of a large game world need to be processed at a given time
GKQuadtree class is one of three spatial partitioning data structures that GameplayKit provides. See these other classes for other tasks:
GKOctreeclass provides the three-dimensional equivalent of a quadtree. Use an octree when you need to organize objects in 3D space.
GKRTreeclass provides a different algorithm for two-dimensional spatial indexing. Quadtrees and R-trees have different performance tradeoffs for different tasks: quadtrees can be faster when objects are more uniformly distributed in space or when their positions change frequently, and R-trees can be faster when searching for all objects in a given region.