Struct ScyllaLooseQuadtreeCore

Burst-compilable loose quadtree kernel that stores items by integer ID and 2D axis-aligned bounding boxes. Designed for fast broad-phase spatial queries (overlap, radius, ray) over large numbers of potentially moving items.

Implements

IDisposable

Inherited Members

ValueType.Equals(object)

ValueType.GetHashCode()

ValueType.ToString()

object.Equals(object, object)

object.GetType()

object.ReferenceEquals(object, object)

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

[BurstCompile]
public struct ScyllaLooseQuadtreeCore : IDisposable

Remarks

Loose bounds concept: Every node maintains two sets of bounds. The tight bounds are the exact cell extents produced by subdivision. The loose bounds are the tight bounds scaled outward by the Looseness factor (e.g. 1.2 means 20 percent expansion on each side). Insertion and update containment checks use the loose bounds, while query traversal pruning also tests loose bounds. This strategy reduces reinsertion churn: as long as an item remains within its assigned node’s loose bounds, Update(int, ScyllaAABB2) only updates the stored bounds without walking the tree again.

Update vs Rebuild:

• Use Update(int, ScyllaAABB2) when only a subset of items move each tick. The amortized cost is sub-linear for typical entity movement patterns.
• Use Rebuild(NativeArray<int>, NativeArray<ScyllaAABB2>) when nearly all items move every tick; a single bulk clear-and-reinsert pass is typically cheaper than the accumulated reinsertion churn of many per-item updates.

Algorithmic complexity (typical):

• Insert: O(depth) tree descent plus an occasional redistribution pass when a node is split.
• Remove: O(k) where k is the number of items in the owning node (bounded by MaxItemsPerNode in most cases).
• Queries: proportional to the number of nodes visited plus the number of candidate items returned.

Determinism: Child nodes are always appended in a fixed order (−x−y, +x−y, −x+y, +x+y) and traversal uses an iterative stack over this fixed order, so query results are deterministic for an identical insertion sequence. Items within a single node are stored in a singly-linked list with O(1) head insertion, so per-node result order reflects insertion recency, not original insertion order.

Native container ownership: All internal storage uses NativeList and NativeHashMap. Call Dispose() to release unmanaged memory. The managed wrapper ScyllaLooseQuadtree handles disposal automatically in its own Dispose method.

Burst usage: This struct is marked [BurstCompile]. You may pass it by value to a Burst job; ensure the owning ScyllaLooseQuadtree is not disposed while the job is executing.

Constructors

ScyllaLooseQuadtreeCore(ScyllaAABB2, int, int, float, Allocator, int)

Creates a new loose quadtree core and allocates its native containers.

Declaration

public ScyllaLooseQuadtreeCore(ScyllaAABB2 rootBounds, int maxDepth, int maxItemsPerNode, float looseness, Allocator allocator, int initialItemCapacity = 64)

Parameters

Type	Name	Description
ScyllaAABB2	rootBounds	Tight root bounds of the quadtree. Items are inserted only when their bounds are fully contained by the root's loose bounds (tight bounds expanded by looseness). Both size components must be greater than zero.
int	maxDepth	Maximum number of subdivision levels permitted. A value of 0 means no subdivision - all items are stored in the root node. Higher values allow finer partitioning at the cost of additional node memory.
int	maxItemsPerNode	Maximum number of items a node may hold before being subdivided. Must be at least 1. Lower values produce deeper, more granular trees; higher values keep the tree shallow.
float	looseness	Expansion factor applied to each node's tight bounds to produce its loose bounds. Must be a finite value greater than or equal to 1.0. A value of exactly 1.0 disables looseness (tight equals loose). Values in the range 1.1-2.0 are typical for games with frequently moving items.
Allocator	allocator	Memory allocator used for the internal NativeList and NativeHashMap. Use Allocator.Persistent for a tree that lives beyond a single frame.
int	initialItemCapacity	Initial bucket capacity for the item hash map. Defaults to 64. Setting this close to the expected peak item count reduces early rehashing.

Exceptions

Type	Condition
ArgumentException	Thrown when rootBounds is invalid.
ArgumentOutOfRangeException	Thrown when rootBounds has a non-positive size component, maxDepth is negative, maxItemsPerNode is less than 1, or looseness is less than 1.0, NaN, or infinite.

Properties

Count

Total number of items currently registered across all nodes in the tree.

Declaration

public int Count { get; }

Property Value

Type	Description
int

IsCreated

Returns true when the underlying native containers have been allocated, i.e. the parameterized constructor has been called. A default-initialized struct returns false. All public API methods guard against a false value via Scylla.Core.Structures.ScyllaLooseQuadtreeCore.RequireCreated().

Declaration

public bool IsCreated { get; }

Property Value

Type	Description
bool

Looseness

Expansion factor applied to each node's tight bounds to produce its loose bounds. Must be at least 1.0 (no expansion). Higher values reduce reinsertion frequency for moving items at the cost of increased node overlap during query traversal.

Declaration

public float Looseness { get; }

Property Value

Type	Description
float

MaxDepth

Maximum number of subdivision levels allowed. Nodes at this depth are never split further, regardless of how many items they accumulate. A value of 0 means no subdivision.

Declaration

public int MaxDepth { get; }

Property Value

Type	Description
int

MaxItemsPerNode

Number of items a node may hold before being considered for subdivision. When a node's item count exceeds this value and the node is below MaxDepth, it will be split by TrySplitIfNeeded(int).

Declaration

public int MaxItemsPerNode { get; }

Property Value

Type	Description
int

RootLooseBounds

The loose bounds of the root node: the tight bounds expanded by the Looseness factor. Items are only accepted by TryAdd(int, ScyllaAABB2) and Update(int, ScyllaAABB2) when their bounds are fully contained by this region.

Declaration

public ScyllaAABB2 RootLooseBounds { get; }

Property Value

Type	Description
ScyllaAABB2

RootTightBounds

The tight (exact cell) bounds of the root node, i.e. the spatial extent passed to the constructor. All items must fit within RootLooseBounds, which is derived from this value.

Declaration

public ScyllaAABB2 RootTightBounds { get; }

Property Value

Type	Description
ScyllaAABB2

Methods

Clear()

Removes all items from every node and collapses the tree back to a single root node, discarding all subdivision structure. The Count is reset to zero.

Declaration

public void Clear()

Remarks

This is an O(n) operation in the number of existing nodes. After this call, any item IDs that were previously registered are no longer valid and must be re-added.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Contains(int)

Returns true if an item with the specified ID is currently registered in the tree.

Declaration

public bool Contains(int itemID)

Parameters

Type	Name	Description
int	itemID	The integer ID to test for membership.

Returns

Type	Description
bool	true if the ID was previously added and has not been removed; false otherwise.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Dispose()

Releases the native containers (NativeList and NativeHashMap) owned by this core and returns their memory to the Unity allocator.

Declaration

public void Dispose()

Remarks

It is safe to call Dispose on a core that has not been fully constructed; each container is checked with IsCreated before disposal. After this call, any further use of the core is undefined behavior.

QueryOverlap(ScyllaAABB2, NativeList<int>, NativeList<int>)

Overlap query: appends the IDs of all items whose bounding boxes intersect the query bounds.

Declaration

public void QueryOverlap(ScyllaAABB2 query, NativeList<int> results, NativeList<int> traversalStackScratch)

Parameters

Type	Name	Description
ScyllaAABB2	query	2D axis-aligned query region. Items whose bounds overlap this region are included in results. If query is invalid (IsValid is false), the query is skipped and no items are appended.
NativeList<int>	results	Output list to which matching item IDs are appended. This list is not cleared before appending; callers must clear it themselves if a fresh result set is needed.
NativeList<int>	traversalStackScratch	A caller-supplied scratch NativeList<int> used as the iterative traversal stack. Its contents are cleared at the start of each query. Reuse the same instance across queries to avoid allocation. The managed wrapper ScyllaLooseQuadtree provides its own internal scratch stack so callers of that type do not need to manage this parameter.

Remarks

Query results are candidates - all returned IDs have passing node-level loose-bounds intersection tests plus an exact item-level bounds test. No false positives are returned, but note that the returned set reflects the state of the tree at the time of the call.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

QueryRadius(float2, float, NativeList<int>, NativeList<int>)

Radius query: appends the IDs of all items whose bounding boxes are within the specified radius of the given center point.

Declaration

public void QueryRadius(float2 center, float radius, NativeList<int> results, NativeList<int> traversalStackScratch)

Parameters

Type	Name	Description
float2	center	2D center of the query circle in the tree's coordinate space.
float	radius	Search radius. An item is included if its closest point to center is within this distance (i.e. squared distance from AABB to point is less than or equal to radius * radius). Negative values cause the query to be skipped silently.
NativeList<int>	results	Output list to which matching item IDs are appended. Not cleared before appending.
NativeList<int>	traversalStackScratch	Caller-supplied scratch NativeList<int> used as the iterative traversal stack. Cleared at the start of each query. Reuse across calls to avoid allocation.

Remarks

The containment test is AABB-to-point squared distance, so axis-aligned items that partially protrude into the circle are included even if their center lies outside the radius.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

QueryRay(float2, float2, float, float, NativeList<int>, NativeList<int>)

Ray query: appends the IDs of all items whose bounding boxes intersect the ray segment defined by the parametric interval [tMin, tMax].

Declaration

public void QueryRay(float2 origin, float2 invDir, float tMin, float tMax, NativeList<int> results, NativeList<int> traversalStackScratch)

Parameters

Type	Name	Description
float2	origin	2D origin of the ray in the tree's coordinate space.
float2	invDir	Component-wise reciprocal of the ray direction (1 / direction). Passing the reciprocal avoids repeated division inside the AABB slab test. Use RcpSafe(float2) when the direction may have zero components to avoid division-by-zero producing NaN.
float	tMin	Minimum ray parameter. Intersection must occur at t >= tMin. Pass 0f to start the segment at the ray origin.
float	tMax	Maximum ray parameter. Intersection must occur at t <= tMax. Pass float.PositiveInfinity for an infinite ray.
NativeList<int>	results	Output list to which matching item IDs are appended. Not cleared before appending.
NativeList<int>	traversalStackScratch	Caller-supplied scratch NativeList<int> used as the iterative traversal stack. Cleared at the start of each query. Reuse across calls to avoid allocation.

Remarks

The intersection test uses the standard AABB slab method. Both node-level and item-level tests check the loose bounds and the item's stored bounds respectively.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Rebuild(NativeArray<int>, NativeArray<ScyllaAABB2>)

Performs a bulk rebuild by clearing the tree and reinserting every item from the supplied arrays.

Declaration

public void Rebuild(NativeArray<int> itemIDs, NativeArray<ScyllaAABB2> bounds)

Parameters

Type	Name	Description
NativeArray<int>	itemIDs	Parallel array of item IDs to reinsert. Must have the same length as bounds.
NativeArray<ScyllaAABB2>	bounds	Parallel array of 2D bounding boxes corresponding to each ID in itemIDs. Each entry must be fully contained by the root loose bounds; entries outside the root are silently skipped by TryAdd(int, ScyllaAABB2).

Remarks

Use this method instead of repeated Update(int, ScyllaAABB2) calls when most or all items move every tick. The single clear-and-reinsert pass avoids per-item traversal overhead and is typically faster under high-churn conditions.

If itemIDs and bounds have different lengths, the operation is silently skipped.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Remove(int)

Removes the item with the specified ID from the tree.

Declaration

public bool Remove(int itemID)

Parameters

Type	Name	Description
int	itemID	ID of the item to remove.

Returns

Type	Description
bool	true if the item was found and removed; false if the ID was not registered.

Remarks

Removal is O(k) where k is the number of items currently in the owning node. In typical use, k is bounded by MaxItemsPerNode.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

TryAdd(int, ScyllaAABB2)

Attempts to register a new item in the tree.

Declaration

public bool TryAdd(int itemID, ScyllaAABB2 bounds)

Parameters

Type	Name	Description
int	itemID	Integer ID uniquely identifying the item. Must not already exist in the tree. Use any non-negative integer that is meaningful to the caller (e.g. an entity index or instance ID). No implicit ID management is performed; the caller owns ID assignment.
ScyllaAABB2	bounds	2D axis-aligned bounding box of the item in the tree's coordinate space. Must be fully contained by RootLooseBounds.

Returns

Type	Description
bool	true if the item was successfully added. Returns false if itemID is already registered, or if bounds extends outside the root loose bounds.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Update(int, ScyllaAABB2)

Updates the 2D bounds of an existing item, potentially reinserting it into a different node.

Declaration

public bool Update(int itemID, ScyllaAABB2 newBounds)

Parameters

Type	Name	Description
int	itemID	ID of the item to update. Must be currently registered.
ScyllaAABB2	newBounds	The item’s new 2D bounding box. Must be fully contained by RootLooseBounds. If newBounds extends outside the root loose bounds, the update is rejected and the method returns false without modifying the tree.

Returns

Type	Description
bool	true if the item existed and its bounds were updated; false if the ID was not registered or if newBounds exceeds the root loose bounds.

Remarks

If the new bounds are still fully contained by the assigned node’s loose bounds, only the stored bounding box is updated - no tree traversal or reinsertion occurs (O(1)).

If the item has moved outside its current node’s loose bounds, it is unlinked from that node and reinserted from the root via FindBestNodeForBounds(ScyllaAABB2). A subsequent split check is performed on the new node.

Exceptions

Type	Condition
InvalidOperationException	Thrown when the core has not been constructed.

Implements

IDisposable

See Also

ScyllaLooseQuadtree

ScyllaAABB2