Class QuadTree

packages/melonjs/src/physics/broadphase/quadtree.ts:104–607

 * @see World.broadphase
 */
export default class QuadTree implements Broadphase<QuadTreeItem> {
	world: World;
	bounds: QuadRect | Bounds;
	max_objects: number;
	max_levels: number;
	level: number;
	objects: QuadTreeItem[];
	nodes: QuadTree[];

	/**
	 * Total number of objects in this subtree (this node's own
	 * `objects` plus every descendant's). Maintained by `insert`
	 * and `remove` so `isPrunable` / `hasChildren` are O(1) reads
	 * instead of O(tree-size) walks. Reset to 0 in `clear`.
	 * @ignore
	 */
	_subtreeCount: number;

	/**
	 * Root-only scratch array reused across `retrieve` calls to
	 * avoid allocating a fresh array per pointer event / per
	 * narrow-phase query. Only the root allocates one; recursive
	 * subnode calls receive the array via the `result` arg.
	 * @ignore
	 */
	_retrieveScratch: QuadTreeItem[] | null;

	/**
	 * @param world - the physic world this QuadTree belongs to
	 * @param bounds - bounds of the node
	 * @param [max_objects=4] - max objects a node can hold before splitting into 4 subnodes
	 * @param [max_levels=4] - total max levels inside root QuadTree
	 * @param [level] - depth level, required for subnodes
	 */
	constructor(
		world: World,
		bounds: QuadRect | Bounds,
		max_objects = 4,
		max_levels = 4,
		level = 0,
	) {
		this.world = world;
		this.bounds = bounds;

		this.max_objects = max_objects;
		this.max_levels = max_levels;

		this.level = level;

		this.objects = [];
		this.nodes = [];

		this._subtreeCount = 0;
		this._retrieveScratch = level === 0 ? [] : null;
	}

	/*
	 * Split the node into 4 subnodes