SpatialTrees 3.0.0

Spatial Trees

This library lets you quickly build and search a quadtree (2D) or octree (3D) spatial index. Both are tuned for real-time game and physics use: fast incremental inserts and moves, a one-shot bulk Build for the load-everything-up-front case, and collision queries that allocate nothing on the heap. The octree mirrors the quadtree's design one dimension up — same API shape, same splitting behavior, just with a Z axis added.

Table of contents

• Spatial Trees
  • Table of contents
  • Requirements
  • Project layout
  • Building and testing
  • Thread safety
  • Creating a quadtree
  • Choosing MaxDepth
  • Items
  • Creating an octree
  • Volume items
  • License

The project references another library of mine, FastG, which provides basic geometric primitives (points, rectangles, circles, etc.) and is available on this same GitHub account. Clone the FastG repository as a sibling of this one — e.g. ../FastG relative to this repo's root — and the solution will build without any further changes.

Requirements

• .NET 10 SDK
• The FastG library, cloned next to this repository (see above)

Project layout

SpatialTrees/
├── SpatialTrees.sln
├── SpatialTrees/              # library project
│   ├── SpatialTrees.csproj
│   ├── Quadtree/
│   │   ├── IMapObject2d.cs
│   │   ├── Quadtree.cs
│   │   ├── MultiThreadQuadtree.cs
│   │   ├── QuadtreeNode.cs
│   │   └── eQuadrant.cs
│   └── Octree/
│       ├── IMapObject3d.cs
│       ├── Octree.cs
│       ├── MultiThreadOctree.cs
│       ├── OctreeNode.cs
│       └── eOctant.cs
├── SpatialTreeTests/          # NUnit test project
│   ├── SpatialTreeTests.csproj
│   ├── Quadtree/
│   │   ├── SpatialTreesTests.cs
│   │   ├── TestItem.cs
│   │   └── ...                # AddItem/MoveItem/RemoveItem/Build/Clear/Resize/etc. fixtures
│   └── Octree/
│       ├── OctreeCollisionTests.cs
│       ├── TestVolumeItem.cs
│       └── ...                # same fixture layout as Quadtree, one dimension up
└── BenchMarks/                # BenchmarkDotNet perf suite (see BenchMarks/README.md)
    └── BenchMarks.csproj

Building and testing

dotnet build SpatialTrees.sln
dotnet test SpatialTrees.sln

Unit tests are written with NUnit and live in the SpatialTreeTests project.

The BenchMarks project is a BenchmarkDotNet suite for measuring insert, build, and query performance. Run it in Release: dotnet run -c Release --project BenchMarks -- --filter *Quadtree* (see BenchMarks/README.md).

Thread safety

Quadtree and Octree are not thread safe. They are intended for single-threaded use; if you access one from more than one thread, you must serialize the calls yourself.

For concurrent use, wrap the structure in MultiThreadQuadtree or MultiThreadOctree. Each is a thread-safe facade over one plain tree that serialises every operation through a ReaderWriterLockSlim: collision queries take a shared read lock (so they run in parallel), and mutations (AddItem, MoveItem, RemoveItem, Clear, Resize, ...) take the write lock exclusively. The lock is entered inline on every method, so the hot paths carry no extra delegate or allocation — the only cost over the plain tree is the lock itself.

using var tree = new MultiThreadQuadtree(boundingBox, maxDepth, maxObjects);
tree.AddItem(item);
tree.GetCollidingItems(collisionBox, objectTypes, itemsFound);

• Construct from the same arguments as the plain tree, from an already-built instance (new MultiThreadQuadtree(quadtree) — the test injection seam), or with MultiThreadQuadtree.Build(...) for the bulk-load case.
• AddItems / MoveItems apply a whole batch under a single lock acquisition.
• The wrapped tree is never handed out for unsynchronised access. For an operation the facade does not expose directly, call Read(tree => ...) / Write(tree => ...), which run your delegate against the inner tree under the appropriate lock. The lock is non-recursive, so a delegate must not call back into the facade, and tree-owned references (nodes, the object index, the result list) must not escape the delegate.
• Dispose the facade to release the lock. The caller must not share a result list between threads.

MultiThreadOctree mirrors this exactly, one dimension up.

Creating a quadtree

To initialize a new quadtree, use the following code:

var boundingBox = new Rectangle(0, 0, 1000, 1000);
var maxDepth = 8;
var maxObjects = 16;
var tree = new Quadtree(boundingBox, maxDepth, maxObjects);

• boundingBox is the outer boundary of the search space.
• maxDepth is the number of levels of "resolution". The more levels you add, the more finely the space is subdivided, and the more memory is consumed. See Choosing MaxDepth for how to pick it.
• maxObjects is a per-node limit on how many objects a node holds before it splits. A query has to scan a node's items linearly before it can prune past that node, so keep this small (8–32); raise maxDepth instead if you need more capacity.

The parameterless / bounding-box-only constructors default to maxDepth = 8, maxObjects = 16.

A fourth optional argument, expectedItemCount, pre-sizes the internal item-to-node index so a large build doesn't repeatedly grow it:

var tree = new Quadtree(boundingBox, maxDepth, maxObjects, expectedItemCount: 50_000);

If you have every item up front, build the tree in one pass instead of adding them one at a time:

var tree = Quadtree.Build(boundingBox, maxDepth, maxObjects, items); // items: IReadOnlyCollection<IMapObject2d>

Build partitions the items one quadrant boundary at a time and assembles the nodes bottom-up, so it does none of the repeated leaf split-and-redistribute work the incremental path does and sizes the internal index and each leaf's item list exactly. It is materially faster and lighter for the build-once case; use AddItem for changes afterwards. Items must be distinct references and each must satisfy the same rules AddItem enforces. There is also a Quadtree.Build(boundingBox, items) overload that uses the default depth and object limits.

Searches use binary space partitioning, which is very fast, and collision queries allocate nothing on the heap — the caller supplies the result list and it is reused. Objects are indexed internally, so moving them within the tree is also quick.

The following methods are available on a Quadtree:

static Build(Rectangle boundingBox, int maxDepth, int maxObjects, IReadOnlyCollection<IMapObject2d> items)
static Build(Rectangle boundingBox, IReadOnlyCollection<IMapObject2d> items)
    Builds a tree from all of its items in one bottom-up pass. The short overload uses
    the default depth and object limits. Throws ArgumentException for an item outside
    the world or with no object type bits, same as AddItem.

Resize()
    Doubles the outer bounding box by adding a new top-level node, and increments MaxDepth.

AddItem(IMapObject2d item)
    Adds an item to the tree, or re-places it if it is already present. Throws
    ArgumentException if the item's bounding-box centre is outside the world or it has
    no object type bits set.

MoveItem(IMapObject2d item)
    Re-places an item after its position or size changed; adds it if it was never tracked.
    Same throwing contract as AddItem; a rejected move leaves the item where it was.

RemoveItem(IMapObject2d item)
    Removes the specified item. Returns true if it was found and removed, false otherwise.

Clear()
    Removes all items from the tree. The world rectangle and MaxDepth are left as they are.

GetCollidingItems(Rectangle collisionBox, int objectTypes, List<IMapObject2d> itemsFound)
GetCollidingItems(Circle collisionCircle, int objectTypes, List<IMapObject2d> itemsFound)
    Clears itemsFound, then fills it with every unique item whose bounding box overlaps the
    query region and whose ObjectType shares a bit with objectTypes. Allocates nothing; the
    caller owns the list and reuses it, so it must not be null (ArgumentNullException).
    Returns true if anything was found. The query box must have ordered coordinates
    (Left <= Right, Top <= Bottom); it is not validated.

List<IMapObject2d> GetCollidingItems(Rectangle collisionBox, int objectTypes)
List<IMapObject2d> GetCollidingItems(Circle collisionCircle, int objectTypes)
    Allocating convenience overloads for one-off queries: return a fresh list of the hits.
    On a hot path, keep a list and use the overload above instead.

ObjectIndex, TopNode, WorldRectangle, MaxDepth, and MaxNodeObjects are exposed as read-only properties for inspection.

Choosing MaxDepth

Every level of the tree bisects each axis, so a leaf at depth d (the root is depth 1) spans worldSize / 2^(d - 1) per axis. To pick maxDepth, decide the smallest cell you want the tree to be able to resolve — usually the size of your smallest game object, or the grid resolution collision queries need — and work back from the ratio of the map to that cell:

maxDepth = ceil( log2( worldSize / smallestCell ) ) + 1

worldSize is the longer axis of a non-square map (cells stay square; the short axis just holds more of them). The same formula applies to the octree.

Examples:

Notes:

• This is the depth cap for a fully packed region. A leaf also stops splitting once it holds no more than maxObjects items, so sparse areas never reach maxDepth — it is only the worst-case floor on cell size.
• Extra depth is cheap: interior nodes defer their item-list allocation and an empty quadrant costs nothing, so rounding maxDepth up a level or two for headroom is fine.
• Resize() adds a level on top and increments maxDepth, so the smallest resolvable cell stays the same size while the world doubles.

Items

The quadtree works with any object that implements the IMapObject2d interface:

public interface IMapObject2d
{
    int ObjectType { get; set; }
    Point2 Location { get; set; }
    Rectangle BoundingBox { get; }
}

As long as your objects implement these members, you can add anything you want to the structure with little effort. The ObjectType property lets you intermix different kinds of objects and selectively filter them in searches using bit flags.

BoundingBox is treated as an axis-aligned box with ordered coordinates (Left <= Right, Top <= Bottom). The tree does not validate this — an inverted or rotated rectangle is not detected and will route and range-check incorrectly. Normalise your boxes before handing them to the tree.

Creating an octree

The Octree is the three-dimensional counterpart to the Quadtree — same constructor shape, same methods, same splitting and filtering behavior, just with a Cube/Sphere/Point3 in place of Rectangle/Circle/Point2:

var boundingBox = new Cube(0, 0, 0, 1000, 1000, 1000);
var maxDepth = 8;
var maxObjects = 16;
var tree = new Octree(boundingBox, maxDepth, maxObjects);

It exposes the same set of methods as Quadtree — static Octree.Build(...), Resize(), AddItem(IMapObject3d item), MoveItem(IMapObject3d item), RemoveItem(IMapObject3d item), Clear(), and the GetCollidingItems overloads (a Cube and a Sphere search volume, each with a fill-a-list and an allocating form). A node splits into 8 octants instead of 4 quadrants when it already holds maxObjects items and another one arrives. Choosing MaxDepth works the same way — the cell-size formula is identical, only the per-node child count differs.

Volume items

The octree works with any object that implements the IMapObject3d interface:

public interface IMapObject3d
{
    int ObjectType { get; set; }
    Point3 Location { get; set; }
    Cube BoundingBox { get; }
}

As with the quadtree, BoundingBox must have ordered coordinates (X1 <= X2, Y1 <= Y2, Z1 <= Z2). The tree does not check this; an inverted cube routes incorrectly.

License

This library is covered by the MIT license — do pretty much anything you want with it, except claim it as your own work. Go build something cool with it, and sell it for a lot of money.