QuadTree constructor

QuadTree({ required Rect boundary, int capacity = 24, int depth = 12, })

Creates a new Quadtree with boundary and a capacity.

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.

Implementation

factory QuadTree({
  // Boundary of the QuadTree.
  required ui.Rect boundary,
  // Capacity of the each QuadTree node.
  int capacity = 24,
  // Maximum depth of the QuadTree.
  int depth = 12,
}) {
  // Make copy of the boundary
  final rect = ui.Rect.fromLTRB(
    boundary.left,
    boundary.top,
    boundary.right,
    boundary.bottom,
  );
  // Validate the parameters
  assert(rect.isFinite, 'The boundary must be finite.');
  assert(!rect.isEmpty, 'The boundary must not be empty.');
  assert(capacity >= 6, 'The capacity must be greater or equal than 6.');
  assert(depth >= 1, 'The maximum depth must be greater or equal than 1.');
  assert(depth <= 7000, 'The maximum depth must be less or equal than 7000.');
  // Initialize the QuadTree
  final nodes = List<QuadTree$Node?>.filled(_reserved, null, growable: false);
  final recycledNodes = Uint32List(_reserved);
  final objects = Float32List(_reserved * _objectSize);
  final recycledIds = Uint32List(_reserved);
  final id2node = Uint32List(_reserved);
  // Create the QuadTree
  return QuadTree._internal(
    boundary: rect,
    capacity: capacity.clamp(6, 10000),
    depth: depth.clamp(1, 7000),
    nodes: nodes,
    recycledNodes: recycledNodes,
    objects: objects,
    recycledIds: recycledIds,
    id2node: id2node,
  );
}