# GKQuadtree A data structure for organizing objects based on their locations in a two-dimensional space. ``` class GKQuadtree where ElementType : NSObject ``` ## Overview 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](/documentation/gameplaykit/gkquadtree#1965707). 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 The [`GKQuadtree`](/documentation/GameplayKit/GKQuadtree) class is one of three spatial partitioning data structures that GameplayKit provides. See these other classes for other tasks: - The [`GKOctree`](/documentation/GameplayKit/GKOctree) class provides the three-dimensional equivalent of a quadtree. Use an octree when you need to organize objects in 3D space. - The [`GKRTree`](/documentation/GameplayKit/GKRTree) 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. ## Topics ### Creating a Quadtree [`init(boundingQuad:minimumCellSize:)`](/documentation/GameplayKit/GKQuadtree/init(boundingQuad:minimumCellSize:)) Initializes a quadtree with the specified dimensions. [`quadtreeWithBoundingQuad:minimumCellSize:`](/documentation/GameplayKit/GKQuadtree/quadtreeWithBoundingQuad:minimumCellSize:) Creates a quadtree with the specified dimensions. ### Adding and Removing Elements [`add(_:at:)`](/documentation/GameplayKit/GKQuadtree/add(_:at:)) Adds an object to the tree corresponding to the specified point in 2D space. [`add(_:in:)`](/documentation/GameplayKit/GKQuadtree/add(_:in:)) Adds an object to the tree corresponding to the specified region of 2D space. [`remove(_:using:)`](/documentation/GameplayKit/GKQuadtree/remove(_:using:)) Removes the specified object from the tree, using a reference to its containing node. [`remove(_:)`](/documentation/GameplayKit/GKQuadtree/remove(_:)) Searches for the specified object and removes it from the tree. ### Searching for Elements [`elements(at:)`](/documentation/GameplayKit/GKQuadtree/elements(at:)) Returns all objects whose corresponding locations overlap the specified point. [`elements(in:)`](/documentation/GameplayKit/GKQuadtree/elements(in:)) Returns all objects whose corresponding locations overlap the specified region. ### Constants [`GKQuad`](/documentation/GameplayKit/GKQuad) The definition of an axis-aligned rectangle addressed by the tree. For more information, see [GameplayKit Programming Guide](https://developer.apple.com/library/archive/documentation/General/Conceptual/GameplayKit_Guide/index.html#//apple_ref/doc/uid/TP40015172). --- Copyright © 2026 Apple Inc. All rights reserved. | [Terms of Use](https://www.apple.com/legal/internet-services/terms/site.html) | [Privacy Policy](https://www.apple.com/privacy/privacy-policy)