A data structure for organizing objects based on their locations in a three-dimensional space.
- iOS 10.0+
- macOS 10.12+
- Mac Catalyst 13.0+Beta
- tvOS 10.0+
An octree manages its structure to optimize for spatial searches—unlike a basic data structure such as an array or dictionary, an octree can find all elements occupying a specific position or volume very quickly. The octree partitioning strategy divides space into eight octants at each level, as illustrated in Figure 1. When an octant contains more than one object, the tree subdivides that region into eight smaller octants, adding a level to the tree.
Octrees 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
GKOctree class is one of three spatial partitioning data structures that GameplayKit provides, and the only one suited to three-dimensional data. See the GKQuadTree class for the two-dimensional analogue of an octree, and the
GKRTree class for different ways to organize two-dimensional data.