---
title: GKQuadtree
framework: gameplaykit
role: symbol
role_heading: Class
path: gameplaykit/gkquadtree
---

# GKQuadtree

A data structure for organizing objects based on their locations in a two-dimensional space.

## Declaration

```swift
class GKQuadtree<ElementType> where ElementType : NSObject
```

## Overview

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. 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 class is one of three spatial partitioning data structures that GameplayKit provides. See these other classes for other tasks: The GKOctree class provides the three-dimensional equivalent of a quadtree. Use an octree when you need to organize objects in 3D space. The 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:)](gameplaykit/gkquadtree/init(boundingquad:minimumcellsize:).md)

### Adding and Removing Elements

- [add(_:at:)](gameplaykit/gkquadtree/add(_:at:).md)
- [add(_:in:)](gameplaykit/gkquadtree/add(_:in:).md)
- [remove(_:using:)](gameplaykit/gkquadtree/remove(_:using:).md)
- [remove(_:)](gameplaykit/gkquadtree/remove(_:).md)

### Searching for Elements

- [elements(at:)](gameplaykit/gkquadtree/elements(at:).md)
- [elements(in:)](gameplaykit/gkquadtree/elements(in:).md)

### Constants

- [GKQuad](gameplaykit/gkquad.md)

## Relationships

### Inherits From

- [NSObject](objectivec/nsobject-swift.class.md)

### Conforms To

- [CVarArg](swift/cvararg.md)
- [CustomDebugStringConvertible](swift/customdebugstringconvertible.md)
- [CustomStringConvertible](swift/customstringconvertible.md)
- [Equatable](swift/equatable.md)
- [Hashable](swift/hashable.md)
- [NSObjectProtocol](objectivec/nsobjectprotocol.md)

## See Also

### Spatial Partitioning

- [GKQuadtreeNode](gameplaykit/gkquadtreenode.md)
- [GKOctree](gameplaykit/gkoctree.md)
- [GKOctreeNode](gameplaykit/gkoctreenode.md)
- [GKRTree](gameplaykit/gkrtree.md)