QuadTree class final

A Quadtree data structure that subdivides a 2D space into four quadrants to speed up collision detection and spatial queries.

All objects are stored in the leaf nodes of the QuadTree and represented as rectangles with an identifier. The QuadTree can store objects with a width, height, and position. Positions are represented as a point (x, y) in the 2D space at the top-left corner of the object.

The QuadTree is a tree data structure in which each internal node has exactly four children: North-West, North-East, South-West, and South-East. Each node represents a rectangular region of the space.

The QuadTree is a spatial partitioning algorithm that is used to subdivide a two-dimensional space into smaller regions for efficient collision detection and spatial queries.

boundary is the boundary of the QuadTree, usually the size of the game world coordinates or the screen size.

capacity is the maximum number of objects that can be stored in a node before it subdivides. Suitable values for the capacity are usually between 18 and 24. Should be always greater or equal than 6.

depth is the maximum depth of the QuadTree. If the depth is reached, the QuadTree will not subdivide further and capacity will be ignored. Suitable values for the depth are usually between 8 and 16. Should be always greater or equal than 1.

This formula computes the maximum depth of a quad tree based on the overall boundary size (Boundary) and the desired minimal boundary size (Size) for each node:

maxDepth = ceil(log2(Boundary / Size))

Where:

  • Boundary is the length of the entire boundary (e.g., the width or height of the area, assuming a square).
  • Size is the desired minimal boundary size for a node.
  • log2(...) is the logarithm base 2.
  • ceil(...) means rounding up to the next integer.

For example, if the boundary is 1024x1024 and the desired minimal size is 64x64, the maximum depth of the quad tree will be: maxDepth = ceil(log2(1024 / 64)) = ceil(log2(16)) = ceil(4) = 4

The quad tree subdivides its space by splitting each node into four quadrants, effectively halving the boundary at every level. Once the boundary size reaches the desired minimal size, the maximum depth is reached.

Constructors

QuadTree.new({required Rect boundary, int capacity = 24, int depth = 12})
Creates a new Quadtree with boundary and a capacity.
factory

Properties

boundary → Rect
Boundary of the QuadTree.
final
capacity → int
The maximum number of objects that can be stored in a node before it subdivides.
final
depth → int
The maximum depth of the QuadTree.
final
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Whether this tree is empty and has no objects.
no setter
isNotEmpty → bool
Whether this tree is not empty and has objects.
no setter
length → int
Number of active objects in the QuadTree.
no setter
nodes → int
Number of active nodes in the QuadTree.
no setter
root → QuadTree$Node?
The root node of the QuadTree.
no setter
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

changeSize(int objectId, {double? width, double? height}) → void
Change the size of the object with the given objectId to the new width and height.
clear() → void
Clears the QuadTree and resets all properties.
forEach(bool cb(int id, double left, double top, double width, double height)) → void
Visit all objects in this QuadTree. The walk stops when it iterates over all objects or when the callback returns false.
get(int objectId) → Rect
Get rectangle bounds of the object with the given objectId.
healthCheck() → List<String>
Health check for the QuadTree node. Returns a list of problems found in the QuadTree.
insert(Rect rect) → int
Insert an rectangle into the QuadTree. Returns the identifier of the object in the QuadTree.
move(int objectId, double left, double top, {double? width, double? height}) → void
Move the object with the given objectId to the new position left (x), top (y).
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
optimize() → void
Call this on the root to try merging all possible child nodes. Recursively merges subtrees that have fewer than capacity objects in total.
query(Rect rect) → QuadTree$QueryResult
Query the QuadTree for objects that intersect with the given rect. Returns a buffer of object data.
queryIds(Rect rect) → List<int>
Query the QuadTree for objects that intersect with the given rect. Returns a list of object identifiers.
queryMap(Rect rect) → Map<int, Rect>
Query the QuadTree for objects that intersect with the given rect. Returns a map of object identifiers and their bounds.
remove(int objectId) → bool
Removes objectId from the Quadtree if it exists. After removal, tries merging nodes upward if possible.
toString() → String
A string representation of this object.
override
visit(bool visitor(QuadTree$Node node)) → void
Visit all nodes in the QuadTree. The walk stops when it iterates over all nodes or when the callback returns false.

Operators

operator ==(Object other) → bool
The equality operator.
inherited