A data structure that adaptively organizes objects based on their locations in a two-dimensional space.
- iOS 10.0+
- macOS 10.12+
- tvOS 10.0+
An R-tree manages its structure to optimize for spatial searches—unlike a basic data structure such as an array or dictionary, an R-tree can find all elements occupying a specific position or region very quickly. Additionally, R-trees adapt their internal structure as you add and remove elements, increasing the amount of time required to perform those operations, but decreasing the time required to search for elements later.
An R-tree partitions the space it describes by calculating the minimum bounding regions that enclose each of the added objects. For example, in Figure 1, the numbered shapes are objects added to the tree, and the rectangles marked with letters are the data structure the tree creates to organize them.
In this example, the rectangle C is the smallest rectangle that entirely contains objects 1 and 2; the rectangle D is the smallest that contains objects 3, 4, and 5; the rectangle A is the smallest containing all the objects in rectangles C and D; and so on. The R-tree automatically creates these divisions in a way that keeps the tree balanced—that is, so that no branch of the tree contains significantly more objects or sub-branches than any other branch—so that searches for objects in the tree require a uniformly minimal amount of processing.
R-trees 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
Finding out which other objects are entirely contained within the region occupied by a certain object
GKRTree 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.
The GKQuadTree class 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.