Spatial Structures

Burst-compatible spatial data structures (loose quadtree, loose octree, BVH (Bounding Volume Hierarchy), KD-tree) that keep overlap, radius, ray, and nearest-neighbor queries fast even when the world holds thousands of moving entities.

Summary

Spatial structures answer the questions every game with many entities asks every frame. Which enemies are within attack range? Which projectiles overlap this trigger volume? Which props does this ray hit? Which decoration is closest to the player? The naive answer is to iterate over every candidate, but iteration cost scales linearly with the world’s entity count and quickly dominates the frame budget. A spatial index reorganizes the candidates so the answer can be found in time proportional to the result set rather than the world.

Scylla Core provides four spatial structures, each tuned for a different access pattern:

• ScyllaLooseQuadtree indexes 2D bounding boxes for many moving items.
• ScyllaLooseOctree does the same in 3D.
• ScyllaBVH indexes 3D bounding boxes with a Surface Area Heuristic (SAH) builder and is the right pick for static or rarely-moving collision proxies.
• ScyllaKDTree3 indexes points (no extent) and is the only structure that supports k-nearest-neighbor queries.

Every structure is exposed in three layers. The *Core struct is the Burst-compatible kernel that owns native storage and exposes the algorithmic surface (insert, remove, query). The non-generic managed wrapper (ScyllaLooseQuadtree, ScyllaBVH, etc.) owns a Core plus a built-in query scratch stack, performs argument validation, and supports a fluent builder. The generic wrapper (ScyllaLooseQuadtree<T>, ScyllaLooseOctree<T>) attaches a payload dictionary so callers can associate a managed object with every spatial ID. The Core layer is what runs inside a Burst job; the managed wrappers are what game code uses day-to-day.

Use the spatial structures for:

• Broad-phase collision detection and trigger overlap tests.
• Range queries (sensor cones, ability radii, fog-of-war reveal).
• Ray queries (line-of-sight, projectile sweeps, picking).
• Nearest-neighbor lookups (target acquisition, flocking, point-cloud sampling).
• Culling lists of candidates before more expensive narrow-phase checks.
• Indexing static world geometry built once and queried for the rest of the level.

Features

The structures share a common allocation discipline, query model, and Burst compatibility. Capabilities differ by structure; the feature list below covers everything available across the four.

• Four complementary structures. Loose quadtree for 2D, loose octree for 3D, BVH for static or rarely-moving 3D bounds, KD-tree for 3D points. Each is tuned for a distinct access pattern so a project rarely needs to write its own.
• Loose-bounds optimization. Quadtree and octree nodes carry a tight bound and a loose bound expanded by a Looseness factor. Items that move inside their current loose bound do not have to be reinserted, dropping per-frame update cost to an in-place bounds rewrite. Typical Looseness is 1.1 to 2.0.
• Burst-compatible Cores. Every structure has a [BurstCompile] Core struct that uses only NativeList, NativeHashMap, and primitives. Pass the Core into a Burst job to run inserts and queries with no managed overhead.
• Three-layer architecture. A Core kernel for performance, a managed wrapper for ergonomics, and a generic <T> wrapper for payload binding. Pick the layer that matches the use case without losing access to the others.
• Fluent builders. Every managed wrapper exposes a CreateBuilder() API with With* setters and sensible defaults. Missing required configuration (root bounds, allocator) throws at Build() time, not later.
• Three query shapes. Overlap (AABB (Axis-Aligned Bounding Box) intersection), radius (sphere or 2D circle), and ray (slab method with precomputed inverse direction). BVH adds ray queries explicitly; the loose trees expose all three. KD-tree adds nearest-neighbor and k-nearest-neighbor.
• Generic payload variants. ScyllaLooseQuadtree<T> and ScyllaLooseOctree<T> wrap a payload dictionary so each item ID maps to a managed object. The spatial query returns IDs; TryGetPayload translates them.
• SAH-based BVH bulk build. ScyllaBVH.Build(itemIDs, bounds) builds a balanced binary tree top-down using the Surface Area Heuristic. Significantly faster than inserting items one by one when the full set is known up front.
• Fattened BVH leaves. Leaf AABBs are expanded by a FatteningMargin (default 0.1, typical 0.05 to 0.2). Items that move inside their fattened leaf are refit; only items that escape are reinserted, halving update cost for slowly-moving objects.
• 3D-aware quadtree. ScyllaLooseQuadtree exposes Add/Update/Query* overloads that take 3D inputs and project them onto either the XZ plane (top-down games) or the XY plane (side-scrollers) via the ScyllaQuadtreePlane enum.
• Iterative traversal with scratch stacks. All queries use an iterative depth-first traversal over an explicit stack. The managed wrapper allocates a NativeList<int> once and reuses it across queries; jobs supply their own.
• IScyllaCollection conformance. Every wrapper exposes Count, IsEmpty, Capabilities, ThreadSafety (always Unsynchronized), and SyncRoot. Disposal is mandatory and double-dispose is safe.

Structures

The choice of structure is dictated by dimensionality, movement frequency, and whether items have extent. Pick the row that matches the dominant pattern.

Structure	Dim	Item shape	Movement profile	Notes
ScyllaLooseQuadtree	2D	ScyllaAABB2	Many moving items	Default for 2D games and for top-down 3D worlds where Y is largely irrelevant (use the 3D overloads with ScyllaQuadtreePlane.XZ). The looseness factor keeps small per-frame motion from triggering reinsertion.
ScyllaLooseOctree	3D	ScyllaAABB3	Many moving items	Default for true 3D worlds with moving entities. Same loose-bounds optimization as the quadtree, extended to eight children per subdivision. Memory cost is roughly double the quadtree for the same item count.
ScyllaBVH	3D	ScyllaAABB3	Static or slow-moving	Surface Area Heuristic bulk build produces a tight, query-efficient tree. Best when the bound set is known up front, queried often, and rarely modified. Incremental Add/Update/Remove are supported with fattening; for high update churn the loose octree is usually better.
ScyllaKDTree3	3D	float3 (points)	Built once	The only structure offering true nearest-neighbor and k-nearest-neighbor. Items are points without extent. Build is bulk-only; once built, the tree is read-only until cleared and rebuilt.

The structures use 32-bit integer item IDs supplied by the caller. The same ID can be reused across structures if a project wants the same entity indexed in more than one tree (for example a LooseOctree of present-frame positions and a BVH of authored room volumes).

Recipes

These recipes cover every public surface in the spatial structures subsystem. Each one is a self-contained answer to a specific gameplay problem, so jump straight to the scenario that matches what you are building. The first recipe walks you through picking a structure and building a quadtree; the rest assume you have a tree in hand, so start there if you are new to the API.

Pick the right structure for your game

Problem. You are about to index spatial data and four structures are on offer. Picking the wrong one means either a painful refactor or a slower query loop than you need. The decision is short, so make it before writing any code.

Solution. Work through this decision tree:

• Items have no extent (just a position) and queries are nearest-neighbor: use ScyllaKDTree3.
• Items have extent and the world is 2D or treats Y as ignorable (top-down, strategy, side-scroller): use ScyllaLooseQuadtree.
• Items have extent in 3D and move often (enemies, projectiles, vehicles): use ScyllaLooseOctree.
• Items have extent in 3D and are mostly static with many queries per frame (trigger volumes, authored collision proxies, baked occluders): use ScyllaBVH.

A project can hold multiple structures simultaneously and route different query types to each. A level might keep static collision in a ScyllaBVH and moving enemies in a ScyllaLooseOctree, sharing the same integer IDs across both so a hit can look up the entity in either tree.

The next recipe shows you how to build a loose quadtree, which is a good starting point for the most common case: a 2D game or a top-down 3D world with many moving entities. Once you have that pattern, the octree and BVH builders follow the same shape.

Build a loose quadtree for a 2D game

Problem. You have a 2D game with dozens or hundreds of moving enemies and bullets, and you want to stop paying the cost of checking every enemy against every bullet every frame. A loose quadtree partitions the 2D world into a hierarchy of cells; querying only visits cells that overlap the query region rather than scanning the whole list.

Solution. The fluent builder requires WithRootBounds and WithAllocator; the remaining settings have sensible defaults (maxDepth = 8, maxItemsPerNode = 8, looseness = 1.2, itemCapacity = 64).

/* Define the world extent. Every enemy and bullet must fit inside these bounds. */
var worldBounds = new ScyllaAABB2(
    min: new float2(0f, 0f),
    max: new float2(1000f, 1000f));

/* Build the quadtree. Persistent allocator keeps it alive across frames. */
var enemies = ScyllaLooseQuadtree.CreateBuilder()
    .WithRootBounds(worldBounds)                /* Required. Defines the tight root extent.           */
    .WithAllocator(Allocator.Persistent)        /* Required. Persistent for trees that outlive a frame.*/
    .WithMaxDepth(8)                            /* Up to 8 subdivisions; defaults to 8.               */
    .WithMaxItemsPerNode(8)                     /* Subdivide when a node holds more than 8 items.     */
    .WithLooseness(1.25f)                       /* Loose bounds are 25% larger than tight bounds.     */
    .WithItemCapacity(256)                      /* Hint for the item hash map; grows on demand.       */
    .Build();

/* Dispose when done -- the tree owns native memory. */
/* enemies.Dispose() goes in OnDestroy or framework teardown. */

Build a loose octree for a 3D game

Problem. Your game is a true 3D world where enemies, projectiles, and props move in all three dimensions. You want the same loose-bounds efficiency as the quadtree but extended to the full 3D volume.

Solution. The octree builder follows the same shape as the quadtree builder, with WithRootBounds taking a ScyllaAABB3 instead. Root bounds should wrap the entire playable region; items outside the root loose bounds will be rejected at insertion.

/* 3D world: 256 wide, 64 tall, 256 deep, centered at origin. */
var worldBounds = ScyllaAABB3.FromCenterHalfSize(
    center: float3.zero,
    halfSize: new float3(128f, 32f, 128f));

/* Build the octree. Default looseness and node limits are fine for most games. */
var props = ScyllaLooseOctree.CreateBuilder()
    .WithRootBounds(worldBounds)
    .WithAllocator(Allocator.Persistent)
    .WithMaxDepth(7)              /* Coarser tree than the quadtree; 7 levels handles ~5k items well.  */
    .WithMaxItemsPerNode(16)      /* Octree leaves can hold more before splitting pays off.             */
    .WithLooseness(1.3f)          /* Slightly looser bounds for fewer reinsertions on fast movers.     */
    .Build();

Add, move, and remove enemies from the index

Problem. You have a tree and a fleet of enemies. You need to register each one when it spawns, keep the index current as enemies move each frame, and remove them when they die. Anyone who has built a broad-phase index from scratch has eventually wanted the index to key on the same entity ID the rest of the codebase uses, and these structures take that shape directly.

Solution. Items are identified by integer IDs supplied by the caller (typically an entity or instance ID). The same calls work on both the quadtree and the octree; only the AABB type differs.

/* Add three enemies at spawn time. Item IDs come from your entity system. */
enemies.Add(itemID: 1, bounds: new ScyllaAABB2(new float2(10f, 10f), new float2(20f, 20f)));
enemies.Add(itemID: 2, bounds: new ScyllaAABB2(new float2(50f, 50f), new float2(60f, 60f)));
enemies.Add(itemID: 3, bounds: new ScyllaAABB2(new float2(900f, 900f), new float2(910f, 910f)));

/* Per-frame: move enemy 1 to a new position. */
enemies.Update(itemID: 1, newBounds: new ScyllaAABB2(new float2(12f, 11f), new float2(22f, 21f)));

/* On death: remove enemy 3. Returns false when the ID is not registered. */
var removed = enemies.Remove(itemID: 3);

/* Membership probe -- useful before an Update call in defensive code. */
var isAlive = enemies.Contains(itemID: 1);

Query nearby enemies for an AOE attack

Problem. You are implementing an AOE (Area of Effect) ability: a grenade explodes, a shockwave ripples out, a mage’s frost nova hits everything within range. Every frame you need “which enemies are within X units of this point?” and you want only the candidates, not the whole world.

Solution. You allocate a results buffer once and reuse it across every query. Three query shapes cover the common gameplay cases: an AABB overlap for rectangular trigger volumes, a radius for circular or spherical effects, and a ray for projectile sweeps and line-of-sight checks.

/* Allocate a results buffer once. Clear between queries when you want a fresh set. */
var hits = new NativeList<int>(Allocator.Temp);

/* Radius query: all enemies within 30 units of the blast center.
 * The canonical AOE query -- grenade, frost nova, shockwave. */
hits.Clear();
enemies.QueryRadius(
    center: new float2(15f, 15f),
    radius: 30f,
    results: hits);

/* AABB (Axis-Aligned Bounding Box) overlap: all enemies inside a rectangular trigger volume.
 * Use for room-entry events, zone-based logic, proximity mines with a box shape. */
hits.Clear();
enemies.QueryOverlap(
    query: new ScyllaAABB2(new float2(0f, 0f), new float2(100f, 100f)),
    results: hits);

/* Ray query: all enemies a laser beam or bullet sweep intersects.
 * Pass the safe-reciprocal of the direction, not the direction itself. */
var origin    = new float2(0f, 0f);
var direction = new float2(1f, 0f);
var invDir    = ScyllaLooseQuadtreeUtil.RcpSafe(direction);   /* handles zero components safely */
hits.Clear();
enemies.QueryRay(
    origin: origin,
    invDir: invDir,
    tMin: 0f,
    tMax: float.PositiveInfinity,
    results: hits);

/* Act on the candidates. Results are broad-phase only -- run a precise
 * narrow-phase check before applying damage or effects. */
for (var i = 0; i < hits.Length; i++)
{
    var enemyID = hits[i];
    if (PreciseOverlapCheck(enemyID, blastCenter, blastRadius))
    {
        ApplyAOEDamage(enemyID);
    }
}

hits.Dispose();

Keep a large enemy fleet updated efficiently

Problem. You have hundreds of enemies moving every frame and you are paying for a full reinsertion on every move. The index is slow and per-frame update cost is eating into your frame budget. You need a smarter update path.

Solution. The loose-bounds optimization means most per-frame movements are free: an item that stays inside its loose envelope only needs a bounds rewrite, not a full remove-and-reinsert. When almost all items have moved (a swarm AI ticking every agent), a single-pass Rebuild is cheaper than iterating Update calls.

/* Per-tick update path: rewrite bounds for each enemy that moved.
 * If the updated bounds fit inside the existing loose envelope, this is a
 * single hash map write with no tree traversal. The fast path for sparse motion. */
foreach (var enemy in movedThisFrame)
{
    enemies.Update(enemy.ID, enemy.WorldBounds.ToAABB2());
}

/* Bulk rebuild: when most or all enemies moved this frame (a swarm, a flocking
 * system, a physics-driven crowd), a single Rebuild pass is cheaper than many
 * Update calls because it avoids per-item migration bookkeeping. */
var ids    = new NativeArray<int>(enemiesArray.Length, Allocator.Temp);
var bounds = new NativeArray<ScyllaAABB2>(enemiesArray.Length, Allocator.Temp);

for (var i = 0; i < enemiesArray.Length; i++)
{
    ids[i]    = enemiesArray[i].ID;
    bounds[i] = enemiesArray[i].WorldBounds;
}

enemies.Rebuild(ids, bounds);
ids.Dispose();
bounds.Dispose();

Get enemy objects back from a spatial query

Problem. Your spatial query returns integer IDs, but you want the enemy MonoBehaviour or data struct back directly without maintaining a separate dictionary in your own code. A lot of game code wants to ask the spatial index a question and get the entity object out of the other end.

Solution. ScyllaLooseQuadtree<T> and ScyllaLooseOctree<T> wrap the non-generic tree with a managed Dictionary<int, T> payload map. Spatial queries still return IDs; TryGetPayload then maps each hit to the associated object.

/* The payload is whatever object you want back from a query. */
public sealed class Enemy { public Transform Transform; public int Health; }

/* Build the generic wrapper using the same positional arguments as the non-generic tree. */
var spatial = new ScyllaLooseQuadtree<Enemy>(
    rootBounds: worldBounds,
    maxDepth: 8,
    maxItemsPerNode: 8,
    looseness: 1.2f,
    allocator: Allocator.Persistent);

/* Add enemies. The payload is stored alongside the spatial entry. */
spatial.Add(itemID: enemy.ID, payload: enemy, bounds: enemy.Bounds);

/* Query and resolve payloads in one pass. */
var hits = new NativeList<int>(Allocator.Temp);
spatial.QueryRadius(center: new float2(0f, 0f), radius: 50f, results: hits);

for (var i = 0; i < hits.Length; i++)
{
    if (spatial.TryGetPayload(hits[i], out var found))
    {
        /* found is your Enemy instance -- apply damage, add to a target list, etc. */
        found.Health -= 10;
    }
}

hits.Dispose();

Use a 2D quadtree for a top-down 3D world

Problem. Your game is technically 3D but plays from a top-down perspective: an RTS, a twin-stick shooter, a management sim. The Y axis is mostly irrelevant for enemy proximity and ability range queries, so you do not want to pay for full octree traversal on a dimension that barely varies.

Solution. The quadtree’s 3D overloads project a float3 AABB onto either the XZ plane (top-down, default) or the XY plane (side-scroller) via the ScyllaQuadtreePlane enum. You keep the lighter 2D tree while still feeding it 3D world positions directly.

/* A unit positioned on the XZ ground plane. Y is ignored for spatial indexing. */
var unitMin = new float3(120f, 0f, 340f);
var unitMax = new float3(124f, 2f, 344f);

/* Project to the XZ plane at insertion time. */
enemies.Add(itemID: 42, min: unitMin, max: unitMax, plane: ScyllaQuadtreePlane.XZ);

/* 3D radius query: a sensor cone projected onto the same plane.
 * All units within 20 units on the ground plane, regardless of height. */
var sensorCenter = new float3(122f, 0f, 342f);
var hits = new NativeList<int>(Allocator.Temp);
enemies.QueryRadius(center: sensorCenter, radius: 20f, results: hits, plane: ScyllaQuadtreePlane.XZ);

hits.Dispose();

Cull off-screen objects with a BVH

Problem. You have a level full of authored trigger volumes, static collision proxies, or baked occluders. There could be 500 of them, they almost never move, and you are querying against them hundreds of times per frame. A loose octree is overkill for this shape: the SAH (Surface Area Heuristic) BVH builds a tighter tree that queries much faster when the set is known up front.

Solution. Use ScyllaBVH.Build with the full set at level load. You get dramatically better query performance than incremental insertion because SAH partitioning places the split planes where they minimize traversal cost. Incremental Add/Update/Remove are still supported for the handful of objects that genuinely arrive at runtime.

/* Build the BVH at level load. Plan for roughly 2*itemCount nodes. */
var bvh = ScyllaBVH.CreateBuilder()
    .WithAllocator(Allocator.Persistent)
    .WithItemCapacity(512)              /* expect ~500 trigger volumes              */
    .WithNodeCapacity(1024)             /* 2 * itemCapacity - 1 for a complete tree */
    .WithQueryStackCapacity(256)        /* traversal stack; grows on demand         */
    .WithFatteningMargin(0.1f)          /* 10% expansion allows small runtime edits */
    .Build();

/* Bulk-build from authored trigger volume data. One pass, dramatically faster
 * than calling Add 500 times. The SAH builder produces a tight, balanced tree. */
var ids    = new NativeArray<int>(triggerVolumes.Length, Allocator.Temp);
var bounds = new NativeArray<ScyllaAABB3>(triggerVolumes.Length, Allocator.Temp);

for (var i = 0; i < triggerVolumes.Length; i++)
{
    ids[i]    = triggerVolumes[i].ID;
    bounds[i] = triggerVolumes[i].WorldBounds;
}

bvh.Build(ids, bounds);
ids.Dispose();
bounds.Dispose();

/* Incremental edits are supported for the rare runtime additions. */
bvh.Add(itemID: 9001, bounds: new ScyllaAABB3(
    min: new float3(0f, 0f, 0f),
    max: new float3(1f, 1f, 1f)));

bvh.Update(itemID: 9001, newBounds: new ScyllaAABB3(
    min: new float3(2f, 0f, 0f),
    max: new float3(3f, 1f, 1f)));

bvh.Remove(itemID: 9001);

Check line-of-sight against level geometry

Problem. You are building an AI stealth system and need to know whether a guard can see the player. Or you are doing a bullet sweep to find the first wall a projectile hits. Both come down to a ray query against your level’s static collision geometry.

Solution. BVH ray queries take a ScyllaRay3 that carries its precomputed inverse direction. Build the ray once per query, then pass it to QueryRay. AABB overlap and sphere intersection are also available on the same tree.

var hits = new NativeList<int>(Allocator.Temp);

/* Line-of-sight check: cast a ray from the guard to the player position.
 * All BVH leaves the ray intersects are returned in traversal order. */
var guardPos  = new float3(10f, 1f, 20f);
var playerPos = new float3(50f, 1f, 80f);
var dir       = math.normalize(playerPos - guardPos);
var ray       = new ScyllaRay3(origin: guardPos, dir: dir);  /* caches safe inverse direction */

hits.Clear();
bvh.QueryRay(ray: ray, maxDistance: 200f, results: hits);

var lineOfSightClear = hits.Length == 0;  /* no geometry between guard and player */

/* AABB overlap: check which trigger volumes a camera frustum intersects for culling. */
hits.Clear();
bvh.QueryOverlap(
    query: new ScyllaAABB3(new float3(0f, 0f, 0f), new float3(100f, 100f, 100f)),
    results: hits);

/* Sphere: all trigger volumes within 25 units of a character
 * (used for audio zone detection, weather region membership, etc.). */
hits.Clear();
bvh.QuerySphere(
    center: new float3(50f, 0f, 50f),
    radius: 25f,
    results: hits);

hits.Dispose();

Find the nearest pickup to the player

Problem. You want to highlight the nearest health pack when the player drops below 30% HP, or snap a held object to the nearest anchor point on a shelf, or have an AI auto-target the closest enemy. Any “what is closest to this point” question where items are positions rather than volumes belongs to the KD-tree (k-Dimensional tree).

Solution. ScyllaKDTree3 is the only structure that offers true nearest-neighbor and k-nearest-neighbor (k-NN) queries. You build it once from a bulk set; once built it is read-only until Clear is called. The payoff is the fastest possible single-nearest and multi-nearest lookup available.

/* Build the KD-tree from all pickup positions at level load. */
var kd = ScyllaKDTree3.CreateBuilder()
    .WithAllocator(Allocator.Persistent)
    .WithPointCapacity(2048)
    .WithNodeCapacity(4096)
    .Build();

var ids    = new NativeArray<int>(pickups.Length, Allocator.Temp);
var points = new NativeArray<float3>(pickups.Length, Allocator.Temp);

for (var i = 0; i < pickups.Length; i++)
{
    ids[i]    = pickups[i].ID;
    points[i] = pickups[i].Position;
}

kd.Build(ids, points);
ids.Dispose();
points.Dispose();

/* Single nearest pickup to the player. */
if (kd.TryFindNearest(queryPoint: player.Position, out var nearestID, out var nearestDist))
{
    /* nearestID is the ID of the closest pickup, nearestDist is squared distance */
    HighlightPickup(nearestID);
}

/* k-nearest pickups: useful for showing the three closest health packs on a minimap
 * or for flocking where each agent needs its k nearest flock-mates. */
var kIDs   = new NativeList<int>(Allocator.Temp);
var kDists = new NativeList<float>(Allocator.Temp);
var found  = kd.FindKNearest(
    queryPoint: player.Position,
    k: 3,
    results: kIDs,
    distances: kDists);  /* FindKNearest clears the lists before writing */

/* Radius query: all pickups within interaction range of the player. */
kIDs.Clear();
kDists.Clear();
kd.QueryRadius(
    queryPoint: player.Position,
    radius: 5f,
    results: kIDs,
    distances: kDists);  /* QueryRadius also clears the lists before writing */

kIDs.Dispose();
kDists.Dispose();

Run spatial queries inside a Burst job

Problem. Your enemy AI ticks hundreds of agents per frame and a radius query per agent is eating too much of your frame budget. You want to move the spatial queries into a Burst-compiled job to get the throughput back.

Solution. Every managed wrapper exposes a Core property that returns the underlying *Core struct. Passing the Core into a Burst job runs inserts and queries with no managed overhead. The job must supply its own scratch stack because the wrapper’s stack is not accessible from inside a job.

[BurstCompile]
public struct EnemyRadiusJob : IJob
{
    public ScyllaLooseQuadtreeCore Tree;
    public float2 Center;
    public float Radius;
    public NativeList<int> Results;
    public NativeList<int> TraversalStack;  /* caller-supplied scratch; one per job instance */

    public void Execute()
    {
        /* Provide an explicit traversal stack -- the managed wrapper's stack
         * is not accessible from a Burst job, so each job allocates its own. */
        Results.Clear();
        TraversalStack.Clear();
        Tree.QueryRadius(Center, Radius, Results, TraversalStack);
    }
}

/* Schedule the job using the wrapper's Core. Do not dispose the wrapper
 * while the job is in flight -- the Core holds a reference into its native storage. */
var job = new EnemyRadiusJob
{
    Tree           = enemies.Core,
    Center         = new float2(15f, 15f),
    Radius         = 30f,
    Results        = new NativeList<int>(Allocator.TempJob),
    TraversalStack = new NativeList<int>(Allocator.TempJob)
};

var handle = job.Schedule();
handle.Complete();

/* Process results on the main thread after the job finishes. */

API Sketch

The public surface across the four structures and supporting types. See the API reference for full signatures, remarks, and exception contracts on every member.

namespace Scylla.Core.Structures
{
    /* ------------------------------------------------------------------ */
    /* SUPPORTING TYPES                                                   */
    /* ------------------------------------------------------------------ */

    public struct ScyllaAABB2 : IEquatable<ScyllaAABB2>
    {
        public float2 Min;
        public float2 Max;
        public ScyllaAABB2(float2 min, float2 max);
        public static ScyllaAABB2 FromCenterHalfSize(float2 center, float2 halfSize);
        public bool IsValid { get; }
        public bool Contains(ScyllaAABB2 other);
        public bool Overlaps(ScyllaAABB2 other);
        public float DistanceSqToPoint(float2 point);
        public bool RayIntersects(float2 origin, float2 invDir, float tMin, float tMax);
    }

    public struct ScyllaAABB3 : IEquatable<ScyllaAABB3>
    {
        public float3 Min;
        public float3 Max;
        public ScyllaAABB3(float3 min, float3 max);
        public static ScyllaAABB3 FromCenterHalfSize(float3 center, float3 halfSize);
        public static ScyllaAABB3 Union(ScyllaAABB3 a, ScyllaAABB3 b);
        public bool IsValid { get; }
        public float SurfaceArea { get; }
        public bool Contains(ScyllaAABB3 other);
        public bool Overlaps(ScyllaAABB3 other);
        public float DistanceSqToPoint(float3 point);
        public bool RayIntersects(float3 origin, float3 invDir, float tMin, float tMax);
        public ScyllaAABB3 Expanded(float margin);
    }

    public struct ScyllaRay3
    {
        public float3 Origin;
        public float3 Dir;
        public float3 InvDir;
        public ScyllaRay3(float3 origin, float3 dir);
    }

    public enum ScyllaQuadtreePlane { XZ = 0, XY = 1 }

    /* ------------------------------------------------------------------ */
    /* LOOSE QUADTREE                                                     */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaLooseQuadtree : IScyllaCollection, IDisposable
    {
        public ScyllaLooseQuadtree(ScyllaAABB2 rootBounds, int maxDepth, int maxItemsPerNode,
                                   float looseness, Allocator allocator, int initialItemCapacity = 64);
        public int Count { get; }
        public bool IsEmpty { get; }
        public ScyllaLooseQuadtreeCore Core { get; }
        public void Clear();
        public bool Contains(int itemID);
        public void Add(int itemID, ScyllaAABB2 bounds);
        public void Add(int itemID, float3 min, float3 max, ScyllaQuadtreePlane plane = ScyllaQuadtreePlane.XZ);
        public bool Remove(int itemID);
        public bool Update(int itemID, ScyllaAABB2 newBounds);
        public bool Update(int itemID, float3 min, float3 max, ScyllaQuadtreePlane plane = ScyllaQuadtreePlane.XZ);
        public void Rebuild(NativeArray<int> itemIDs, NativeArray<ScyllaAABB2> bounds);
        public void QueryOverlap(ScyllaAABB2 query, NativeList<int> results);
        public void QueryOverlap(float3 min, float3 max, NativeList<int> results, ScyllaQuadtreePlane plane = ScyllaQuadtreePlane.XZ);
        public void QueryRadius(float2 center, float radius, NativeList<int> results);
        public void QueryRadius(float3 center, float radius, NativeList<int> results, ScyllaQuadtreePlane plane = ScyllaQuadtreePlane.XZ);
        public void QueryRay(float2 origin, float2 invDir, float tMin, float tMax, NativeList<int> results);
        public void QueryRay(float3 origin, float3 direction, float tMin, float tMax, NativeList<int> results, ScyllaQuadtreePlane plane = ScyllaQuadtreePlane.XZ);
        public void Dispose();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaLooseQuadtree<T> : IScyllaCollection, IDisposable
    {
        public ScyllaLooseQuadtree(ScyllaAABB2 rootBounds, int maxDepth, int maxItemsPerNode,
                                   float looseness, Allocator allocator, int initialItemCapacity = 64);
        public ScyllaLooseQuadtree Tree { get; }
        public void Add(int itemID, T payload, ScyllaAABB2 bounds);
        public bool Remove(int itemID, out T payload);
        public bool TryGetPayload(int itemID, out T payload);
        public bool Update(int itemID, ScyllaAABB2 newBounds);
        public void QueryOverlap(ScyllaAABB2 query, NativeList<int> results);
        public void QueryRadius(float2 center, float radius, NativeList<int> results);
        public void Dispose();
    }

    public static class ScyllaLooseQuadtreeUtil
    {
        public static float2 Project(float3 v, ScyllaQuadtreePlane plane);
        public static ScyllaAABB2 ProjectAabb(float3 min, float3 max, ScyllaQuadtreePlane plane);
        public static ScyllaAABB2 ProjectAabbFromCenterHalfSize(float3 center, float3 halfSize, ScyllaQuadtreePlane plane);
        public static float2 RcpSafe(float2 dir);
    }

    /* ------------------------------------------------------------------ */
    /* LOOSE OCTREE                                                       */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaLooseOctree : IScyllaCollection, IDisposable
    {
        public ScyllaLooseOctree(ScyllaAABB3 rootBounds, int maxDepth, int maxItemsPerNode,
                                 float looseness, Allocator allocator, int initialItemCapacity = 64);
        public int Count { get; }
        public ScyllaLooseOctreeCore Core { get; }
        public void Clear();
        public bool Contains(int itemID);
        public void Add(int itemID, ScyllaAABB3 bounds);
        public bool Remove(int itemID);
        public bool Update(int itemID, ScyllaAABB3 newBounds);
        public void Rebuild(NativeArray<int> itemIDs, NativeArray<ScyllaAABB3> bounds);
        public void QueryOverlap(ScyllaAABB3 query, NativeList<int> results);
        public void QueryRadius(float3 center, float radius, NativeList<int> results);
        public void QueryRay(float3 origin, float3 invDir, float tMin, float tMax, NativeList<int> results);
        public void Dispose();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaLooseOctree<T> : IScyllaCollection, IDisposable { /* mirrors the quadtree<T> shape in 3D */ }

    public static class ScyllaLooseOctreeUtil
    {
        public static float3 RcpSafe(float3 dir);
    }

    /* ------------------------------------------------------------------ */
    /* BVH                                                                */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaBVH : IScyllaCollection, IDisposable
    {
        public ScyllaBVH(Allocator allocator, int initialItemCapacity = 64, int initialNodeCapacity = 128,
                        float fatteningMargin = 0.1f, int initialQueryStackCapacity = 256);
        public int Count { get; }
        public ScyllaBVHCore Core { get; }
        public void Reserve(int itemCapacity, int nodeCapacity, int scratchCapacity);
        public void Clear();
        public bool Contains(int itemID);
        public void Build(NativeArray<int> itemIDs, NativeArray<ScyllaAABB3> bounds);
        public void Add(int itemID, ScyllaAABB3 bounds);
        public bool Remove(int itemID);
        public bool Update(int itemID, ScyllaAABB3 newBounds);
        public void QueryOverlap(ScyllaAABB3 query, NativeList<int> results);
        public void QueryRay(ScyllaRay3 ray, float maxDistance, NativeList<int> results);
        public void QuerySphere(float3 center, float radius, NativeList<int> results);
        public void Dispose();
        public static Builder CreateBuilder();
    }

    /* ------------------------------------------------------------------ */
    /* KD-TREE                                                            */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaKDTree3 : IScyllaCollection, IDisposable
    {
        public ScyllaKDTree3(Allocator allocator, int initialPointCapacity = 64, int initialNodeCapacity = 128);
        public int Count { get; }
        public ScyllaKDTree3Core Core { get; }
        public void Build(NativeArray<int> itemIDs, NativeArray<float3> points);
        public void Clear();
        public bool TryFindNearest(float3 queryPoint, out int itemID, out float distance);
        public int FindKNearest(float3 queryPoint, int k, NativeList<int> results, NativeList<float> distances);
        public int QueryRadius(float3 queryPoint, float radius, NativeList<int> results, NativeList<float> distances);
        public void Dispose();
        public static Builder CreateBuilder();
    }
}

See the API reference for full signatures, remarks, and exception contracts on every member.

Settings reference

Every builder exposes a small set of settings. Sensible defaults are listed; required setters are marked.

Loose quadtree builder

Setter	Default	Required	Effect
WithRootBounds	(none)	Yes	Tight root bounds. Items must fit inside the root loose bounds (root tight scaled by looseness).
WithAllocator	(none)	Yes	Native memory allocator. Persistent for long-lived trees, TempJob for single-frame jobs.
WithMaxDepth	8	No	Maximum subdivision depth. 0 keeps everything in the root.
WithMaxItemsPerNode	8	No	Subdivide a node when it exceeds this item count. Smaller values produce deeper trees with tighter queries; larger values reduce memory at the cost of overlap checks.
WithLooseness	1.2	No	Loose-bounds expansion factor. Must be finite and >= 1.0. Typical range 1.1–2.0. Larger values reduce reinsertion churn but increase node overlap (and query false positives).
WithItemCapacity	64	No	Initial item map capacity hint. Grows on demand.

Loose octree builder

Same parameters as the quadtree builder, with WithRootBounds taking a ScyllaAABB3.

BVH builder

Setter	Default	Required	Effect
WithAllocator	(none)	Yes	Native memory allocator.
WithItemCapacity	64	No	Initial item storage capacity. Grows on demand.
WithNodeCapacity	128	No	Initial node storage capacity. Aim for 2 * itemCapacity - 1 for a complete binary tree.
WithQueryStackCapacity	256	No	Initial size of the built-in traversal scratch stack. Grows on demand.
WithFatteningMargin	0.1	No	Leaf AABB expansion. Must be finite and >= 0. Larger margins reduce update churn at the cost of more query false positives. Typical range 0.05–0.2.

KD-tree builder

Setter	Default	Required	Effect
WithAllocator	(none)	Yes	Native memory allocator.
WithPointCapacity	64	No	Initial point storage capacity hint. Grows on Build.
WithNodeCapacity	128	No	Initial node storage capacity hint. Grows on Build.

Best Practices

• Pick the structure that matches the access pattern, not the dimensionality alone. A top-down 3D world is almost always better served by a loose quadtree with XZ projection than a loose octree, because the octree pays for vertical subdivision that produces no query benefit. See the Collections Overview for the broader context on when each structure family fits.
• Use the bulk path when the data is known up front. ScyllaBVH.Build and ScyllaKDTree3.Build produce dramatically better trees than incremental insertion. Reserve incremental Add for items that genuinely arrive over time (spawned at runtime, streamed in from disk).
• Reuse the results NativeList<int> across queries. Allocate it once with Allocator.Temp (per-frame) or Allocator.Persistent (longer scopes), Clear it between calls when fresh results are wanted, and Dispose when done. Allocating per query defeats most of the benefit of the spatial index.
• Tune Looseness and FatteningMargin against actual movement. Both knobs trade reinsertion cost for query false positives. Profile representative gameplay; defaults are starting points, not endpoints.
• Prefer Update for sparse motion and Rebuild for dense motion. The crossover depends on item count and looseness; the rule of thumb is Update below around 30% of items moving, Rebuild above around 70%, and profile in between.
• Dispose every native-backed tree. The wrappers hold a NativeList, NativeHashMap, and (for BVH) an internal scratch stack. Leaks are silent in the Editor and fatal in player builds. Wrap each tree in an owning manager that disposes on OnDestroy or framework teardown.
• Stay within the root bounds. Quadtree and octree Add and Update validate the bounds against the root loose envelope and throw or return false when an item escapes. Pre-clip movement against world bounds at the gameplay layer rather than relying on the tree to silently accept out-of-world geometry.
• Use the Core for jobs, the wrapper for game code. The wrapper provides validation, exception handling, and a shared query stack. Inside a Burst job, all of that is overhead; pass tree.Core and supply a scratch stack from the job’s own allocations.
• Filter spatial-query candidates rather than treating them as authoritative. The loose-bounds and fattened-leaf strategies guarantee no false negatives but tolerate false positives. Run narrow-phase tests (precise sphere-AABB, ray-mesh, custom collision shape) on every returned ID before acting on it.
• Mind the asymmetric clear behavior. FindKNearest and QueryRadius on the KD-tree clear destination lists before writing; the broad-phase queries on the loose trees and BVH append to the destination list. Always check which behavior you need at each call site; clear explicitly where the desired semantics differ.
• Do not assume thread safety. All four wrappers report ThreadSafety.Unsynchronized. Concurrent queries on the same wrapper instance share the internal scratch stack and will corrupt each other. Either serialize with a lock or use the Core in a properly scheduled job with private scratch buffers.
• Combine structures rather than picking one. Static collision in a ScyllaBVH, moving entities in a ScyllaLooseOctree, and a point sampler in ScyllaKDTree3 is a common production layout. The structures share IDs, so an entity can be indexed in multiple trees at the cost of one bit map per tree. See the Grid page if your game also needs grid-aligned spatial reasoning alongside these free-form structures.

Pitfalls

Related

• Collections Overview
• Grid
• Object Pools
• API reference: Scylla.Core.Structures.ScyllaLooseQuadtree
• API reference: Scylla.Core.Structures.ScyllaLooseQuadtreeCore
• API reference: Scylla.Core.Structures.ScyllaLooseOctree
• API reference: Scylla.Core.Structures.ScyllaLooseOctreeCore
• API reference: Scylla.Core.Structures.ScyllaBVH
• API reference: Scylla.Core.Structures.ScyllaBVHCore
• API reference: Scylla.Core.Structures.ScyllaKDTree3
• API reference: Scylla.Core.Structures.ScyllaKDTree3Core
• API reference: Scylla.Core.Structures.ScyllaAABB2
• API reference: Scylla.Core.Structures.ScyllaAABB3
• API reference: Scylla.Core.Structures.ScyllaRay3
• API reference: Scylla.Core.Structures.ScyllaQuadtreePlane