2D Spatial Trees: Concepts and Usage¶

This practical guide complements performance and semantics pages with diagrams and actionable selection advice.

TL;DR: What Problem This Solves¶

• You often need to answer: "What's near X?" or "What's inside this area?"
• ⭐ Naive loops are O(n): check every object. Spatial trees are O(log n): only check nearby objects.
• Result: 10-100x faster queries, scaling from dozens to millions of objects.

The Scaling Advantage¶

Quick picks

• Many moving points, frequent rebuilds, broad searches: QuadTree2D
• Static points, nearest‑neighbor/k‑NN: KdTree2D (Balanced)
• Fast builds with good‑enough queries on points: KdTree2D (Unbalanced)
• Objects with size (bounds), intersect/contain queries: RTree2D

Quick Start (Code)¶

Points (QuadTree2D / KdTree2D)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

using WallstopStudios.UnityHelpers.Core.DataStructure;
using UnityEngine;
using System.Collections.Generic;

// Example element with a position
struct Enemy { public Vector2 pos; public int id; }

var enemies = new List<Enemy>(/* fill with positions */);

// Build a tree from points
var quad = new QuadTree2D<Enemy>(enemies, e => e.pos);
var kd   = new KdTree2D<Enemy>(enemies, e => e.pos); // balanced by default

// Range query (circle)
var inRange = new List<Enemy>();
quad.GetElementsInRange(playerPos, 10f, inRange);

// Bounds (box) query
var inBox = new List<Enemy>();
kd.GetElementsInBounds(new Bounds(center, size), inBox);

// Approximate nearest neighbors
var neighbors = new List<Enemy>();
kd.GetApproximateNearestNeighbors(playerPos, count: 10, neighbors);

Sized objects (RTree2D)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

using WallstopStudios.UnityHelpers.Core.DataStructure;
using UnityEngine;
using System.Collections.Generic;

struct Tile { public Bounds bounds; public int kind; }

var tiles = new List<Tile>(/* fill with bounds */);

// Build from bounds (AABBs)
var rtree = new RTree2D<Tile>(tiles, t => t.bounds);

// Bounds query (fast for large areas)
var hits = new List<Tile>();
rtree.GetElementsInBounds(worldBounds, hits);

// Range query (treats items by their bounds)
var near = new List<Tile>();
rtree.GetElementsInRange(center, radius, near);

Notes

• These trees are immutable: rebuild when positions/bounds change significantly.
• For lots of moving points, consider SpatialHash2D for broad‑phase.
• See Spatial Tree Semantics for boundary behavior and edge cases.

⭐ Zero-Allocation Queries: The Performance Killer Feature¶

The Problem - GC Spikes Every Frame:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void Update()
{
    // 🔴 BAD: Allocates new List every frame
    List<Enemy> nearby = tree.GetElementsInRange(playerPos, 10f);

    foreach (Enemy e in nearby)
    {
        e.ReactToPlayer();
    }
    // Result: GC runs frequently = frame drops
}

The Solution - Buffering Pattern:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Reusable buffer (declare once)
private List<Enemy> nearbyBuffer = new(64);

void Update()
{
    nearbyBuffer.Clear();

    // 🟢 GOOD: Reuses same List = zero allocations
    tree.GetElementsInRange(playerPos, 10f, nearbyBuffer);

    foreach (Enemy e in nearbyBuffer)
    {
        e.ReactToPlayer();
    }
    // Result: No GC, stable 60fps
}

Impact:

• Before: GC spikes every 2-3 seconds, frame drops to 40fps
• After: Zero GC from queries, stable 60fps even with 1000s of queries/second

All spatial trees support this pattern:

• QuadTree2D.GetElementsInRange(pos, radius, buffer)
• KdTree2D.GetElementsInBounds(bounds, buffer)
• RTree2D.GetElementsInRange(pos, radius, buffer)

💡 Pro Tip: Pre-size your buffers based on expected max results. new List<Enemy>(64) avoids internal resizing for results up to 64 items.

Maximum Ergonomics:

These APIs return the buffer you pass in, so you can use them directly in foreach loops:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

private List<Enemy> nearbyBuffer = new(64);

void Update()
{
    // Returns the same buffer - use it directly in foreach!
    foreach (Enemy e in tree.GetElementsInRange(playerPos, 10f, nearbyBuffer))
    {
        e.ReactToPlayer();
    }
}

Using Pooled Buffers:

Don't want to manage buffers yourself? Use the built-in pooling utilities:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

using WallstopStudios.UnityHelpers.Utils;

void Update()
{
    // Get pooled buffer - automatically returned when scope exits
    using var lease = Buffers<Enemy>.List.Get(out List<Enemy> buffer);

    // Use it directly in foreach - combines zero-alloc query + pooled buffer!
    foreach (Enemy e in tree.GetElementsInRange(playerPos, 10f, buffer))
    {
        e.ReactToPlayer();
    }
    // buffer automatically returned to pool here
}

See Buffering Pattern for the complete guide and Pooling Utilities for more pooling options.

Structures¶

QuadTree2D¶

• Partition: Recursively splits space into four quadrants.
• Use for: Broad-phase proximity, view culling, general spatial bucketing.
• Pros: Simple structure; predictable performance; incremental updates straightforward.
• Cons: Data hotspots deepen local trees; nearest neighbors slower than KDTree.

Diagram:

KDTree2D¶

• Partition: Alternating axis-aligned splits (x/y), often median-balanced.
• Use for: Nearest neighbor, k-NN, range queries on points.
• Pros: Strong NN performance; balanced variant gives consistent query time.
• Cons: Costly to maintain under heavy churn; unbalanced variant can degrade.

Diagram:

RTree2D¶

• Partition: Groups items by minimum bounding rectangles (MBRs) with hierarchical MBRs.
• Use for: Items with size (AABBs): sprites, tiles, colliders; bounds intersection.
• Pros: Great for large bounds queries; matches bounds semantics.
• Cons: Overlapping MBRs can increase node visits; not optimal for point NN.

Diagram:

Choosing a Structure¶

Use this decision flowchart to pick the right spatial tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

START: Do your objects move frequently?
  │
  ├─ YES → Consider SpatialHash2D instead (see README)
  │         (Spatial trees require rebuild on movement)
  │
  └─ NO → Continue to next question
      │
      └─ What type of queries do you need?
          │
          ├─ Primarily nearest neighbor (k-NN)
          │   │
          │   ├─ Static data, want consistent performance
          │   │   → KDTree2D (Balanced) ✓
          │   │
          │   └─ Data changes occasionally, need fast rebuilds
          │       → KDTree2D (Unbalanced) ✓
          │
          ├─ Do objects have size/bounds (not just points)?
          │   │
          │   ├─ YES → Need bounds intersection queries
          │   │   → RTree2D ✓
          │   │
          │   └─ NO → Continue
          │
          └─ General range/circular queries, broad-phase
              → QuadTree2D ✓ (best all-around choice)

Quick Reference¶

• Many moving points, rebuild or frequent updates: QuadTree2D
• Nearest neighbors on static points: KDTree2D (Balanced)
• Fast builds with good-enough queries: KDTree2D (Unbalanced)
• Objects with area; bounds queries primary: RTree2D
• Very frequent movement (every frame): SpatialHash2D (see README)

Query Semantics¶

• Points vs. Bounds: QuadTree2D and KDTree2D are point-based; RTree2D is bounds-based.
• Boundary inclusion: normalize half-open vs. closed intervals. Add epsilons for edge cases.
• Numeric stability: prefer consistent ordering for collinear and boundary points.
• Results are a multiset, and the destination list is cleared exactly once. A negative or NaN radius, or a nonfinite query center, returns that cleared empty list; a +Infinity radius is supported. Nearest-neighbor excludes NaN distances and returns min(count, eligibleElementCount) entries ordered by distance and then insertion index; which equidistant elements are in that set differs by family. Constructors exclude non-finite stored positions or bounds edges from the index while retaining the original elements snapshot and source identities. See Query Contract for the full table.

For deeper details, performance data, and diagrams, see:

• 2D Performance Benchmarks
• Spatial Tree Semantics