/** * Quadtree is a data-structure that contains a root node, and child nodes up to a defined depth. These nodes can be considered 'buckets' that can hold up to X objects. * When that number is exceeded (and the maximum depth is not yet reached), the node will split up into 4 separate nodes * (top left, top right, bottom left, bottom right), * dividing up the objects into the correct quadrant based on their location. * */ class QuadTree { constructor (width, height, maxDepth = 7, bucketSize = 30) { this.root = new Node(0, 0, width, height, 0, null, "", this); this.maxDepth = maxDepth; this.bucketSize = bucketSize; this.width = width; this.height = height; } /** * Adds object to the quadtree. if the amount of objects in the target node is higher than * the permitted size, it divides up into 4 new nodes. Contents of this node is then divided up. * @param {GameObject} object * @returns {void} */ add (object) { let dirOfOob = this.outOfBounds(object); while (dirOfOob) { this.embiggen(dirOfOob); dirOfOob = this.outOfBounds(object); } // Node.add may split and move the object into a descendant leaf. // Always re-resolve node afterwards — assigning the pre-split leaf // leaves object.node pointing at an empty branch and breaks remove(). this.findNodeFromRoot(object).add(object); object.node = this.findNodeFromRoot(object); } /** * Removes object from quadtree. If the total amount of objects held by siblings is lower than the maximum size, * a cleanup phase is triggered to remove the objects from siblings, moved up to parent node * @param {GameObject} object * @returns {void} */ remove (object) { const node = object.node || (!this.root.hasChildren ? this.root : null); if (node && node.remove(object)) { object.node = null; } } /** * Retrieves objects within range of a given position. Sorted by distance from position * * @param {vector} position * @param {number} range (radius) * @returns {GameObject[]} result */ getObjectsInRange (position, range) { return this.getObjectsOfTypesInRange(position, range, null); } /** * Retrieves objects within range of a given position matching a type. Sorted by distance from position * * @param {vector} position * @param {number} range (radius) * @param {class[]} types * @returns {GameObject[]} result */ getObjectsOfTypesInRange (position, range, types) { const typeFilter = Array.isArray(types) ? types.filter(t => t != null) : (types != null ? [types] : []); return this.collectInRange(position, range, (obj) => { if (typeFilter.length === 0) { return true; } return typeFilter.some(t => obj instanceof t); }); } getObjectsWithTagInRange (position, range, tags) { const tagFilter = Array.isArray(tags) ? tags.filter(t => t != null) : (tags != null ? [tags] : []); return this.collectInRange(position, range, (obj) => { if (tagFilter.length === 0) { return true; } const objTags = obj.tags; if (!objTags || objTags.length === 0) { return false; } return tagFilter.some(t => objTags.some(tag => tag == t)); }); } collectInRange (position, range, predicate) { const scored = []; const nodes = [this.root]; while (nodes.length > 0) { const node = nodes.pop(); if (!this.isInRange(position, range, node)) { continue; } if (node.hasChildren) { nodes.push(...node.getChildren()); continue; } const objects = node.getObjects(); for (let i = 0, len = objects.length; i < len; i++) { const obj = objects[i]; const dist = obj.transform.position.distanceTo(position); if (dist > 0 && dist < range && predicate(obj)) { scored.push({ obj, dist }); } } } scored.sort((a, b) => a.dist - b.dist); return scored.map(entry => entry.obj); } isInRange (vector, range, node) { var points = [ vector.x - range, vector.x + range, vector.y - range, vector.y + range ]; if (points[1] >= node.x1 && points[0] <= node.x2) { if (points[3] >= node.y1 && points[2] <= node.y2) { return true; } } return false; } embiggen (dirOfOob) { // Place the current root as a child of a 2x parent that grows into the // out-of-bounds direction (L←, R→, U↑, D↓). if (dirOfOob == "L") { this.root = this.root.createParent("topright"); } else if (dirOfOob == "R") { this.root = this.root.createParent("topleft"); } else if (dirOfOob == "U") { this.root = this.root.createParent("bottomleft"); } else if (dirOfOob == "D") { this.root = this.root.createParent("topleft"); } this.width = this.root.lengthX; this.height = this.root.lengthY; } traverseTo (path) { let node = this.root; for (let i = 0, len = path.length; i < len; i++) { if (!node.hasChildren) { return node; } node = node.getChildren()[path[i]]; } return node; } findNodeFromRoot (object) { return this.findNodeFromRootAtPosition(object.transform.position); } findNodeFromRootAtPosition (position) { let node = this.root; while (node && node.hasChildren) { node = node.findChildNode(position) || node.topleft; } return node || this.root; } show (ctx) { this.showAll(this.root, ctx); } showAll (node, ctx) { node.show(ctx); if (node.hasChildren) { node.getChildren().forEach((element) => this.showAll(element, ctx)); } } update (/* deltaTime */) { // Merge/split happen eagerly on add/remove; nothing to tick per frame. } outOfBounds (object) { const pos = object.transform.position; if (pos.x < this.root.x1) { return "L"; } if (pos.x > this.root.x2) { return "R"; } if (pos.y < this.root.y1) { return "U"; } if (pos.y > this.root.y2) { return "D"; } return false; } } class Node { get canBeMerged () { // Leaf siblings may collapse into their parent when the parent's // whole subtree fits in one bucket again. return !this.hasChildren && this.parent && this.parent.recursiveCount <= this.quadTree.bucketSize; } get shouldSplit () { return !this.hasChildren && this.recursiveCount > this.quadTree.bucketSize && this.depth < this.quadTree.maxDepth; } get hasChildren () { return this.bottomright != null; //assume the rest is there too } constructor (x1, y1, x2, y2, depth, parent, name, quadTree) { this.name = name; this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2; this.objects = []; this.topleft = null; this.topright = null; this.bottomleft = null; this.bottomright = null; this.parent = parent; this.depth = depth; this.recursiveCount = 0; this.lengthX = this.x2 - this.x1; this.lengthY = this.y2 - this.y1; this.halfLengthX = this.lengthX / 2; this.halfLengthY = this.lengthY / 2; this.quadTree = quadTree; } addCount () { this.recursiveCount++; this.parent && this.parent.addCount(); if (this.shouldSplit) { this.divide(); } } removeCount () { this.recursiveCount--; // Merge before notifying the parent. If the parent is checked first, // it still sees this node as a branch and skips the collapse; after // this node merges into a leaf the parent never re-checks. if (this.hasChildren) { let merge = true; const children = this.getChildren(); for (let i = 0, l = children.length; i < l; i++) { if (!children[i].canBeMerged) { merge = false; } } if (merge) { this.merge(); } } this.parent && this.parent.removeCount(); } remove (obj) { const index = this.objects ? this.objects.indexOf(obj) : -1; if (index >= 0) { this.objects.splice(index, 1); this.removeCount(); return true; } return false; } add (obj, ignoreCount) { if (this.objects.indexOf(obj) < 0) { this.objects.push(obj); if (!ignoreCount) { this.addCount(); } } } divide () { this.createNodes(); const center = new vector((this.x1 + this.x2) / 2, (this.y1 + this.y2) / 2); this.objects.forEach(object => { if (object.transform.position.y > center.y) { if (object.transform.position.x > center.x) { object.node = this.bottomright; this.bottomright.add(object, true); } else { object.node = this.bottomleft; this.bottomleft.add(object, true); } } else { if (object.transform.position.x > center.x) { object.node = this.topright; this.topright.add(object, true); } else { object.node = this.topleft; this.topleft.add(object, true); } } }); this.objects = []; // add(..., true) skips counting so the parent is not double-counted. // Children still need a correct local recursiveCount, and may themselves // need to split when this redistribute dumps more than bucketSize in one cell. this.getChildren().forEach(child => { child.recursiveCount = child.objects.length; if (child.shouldSplit) { child.divide(); } }); } merge () { this.getChildren().forEach(child => { child.getObjects().forEach(object => { this.add(object, true); object.node = this; }); }); this.removeNodes(); } size () { if (this.objects != null) { return this.objects.length; } return 0; } getObjects () { return this.objects; } getChildren () { if (!this.hasChildren) { return []; } return [this.topleft, this.topright, this.bottomleft, this.bottomright]; } findChildNode (position) { if (!this.hasChildren) { return this; } // Same midpoint rule as divide() so add/remove/query stay consistent, // and we never return undefined on shared edges. const midX = this.x1 + this.halfLengthX; const midY = this.y1 + this.halfLengthY; if (position.y > midY) { return position.x > midX ? this.bottomright : this.bottomleft; } return position.x > midX ? this.topright : this.topleft; } createNodes () { if (this.hasChildren) { return; } const depth = this.depth + 1; this.topleft = new Node(this.x1, this.y1, this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, depth, this, this.name + 0, this.quadTree); this.topright = new Node(this.x1 + this.halfLengthX, this.y1, this.x2, this.y1 + this.halfLengthY, depth, this, this.name + 1, this.quadTree); this.bottomleft = new Node(this.x1, this.y1 + this.halfLengthY, this.x1 + this.halfLengthX, this.y2, depth, this, this.name + 2, this.quadTree); this.bottomright = new Node(this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, this.x2, this.y2, depth, this, this.name + 3, this.quadTree); return this.getChildren(); } createParent (nodePosition) { let parentNode; if (nodePosition == "topleft") { parentNode = new Node(this.x1, this.y1, this.x1 + (this.lengthX * 2), this.y1 + (this.lengthY * 2), this.depth - 1, null, "", this.quadTree); parentNode.topleft = this; } if (nodePosition == "topright") { parentNode = new Node(this.x1 - this.lengthX, this.y1, this.x1 + this.lengthX, this.y1 + (this.lengthY * 2), this.depth - 1, null, "", this.quadTree); parentNode.topright = this; } if (nodePosition == "bottomleft") { parentNode = new Node(this.x1, this.y1 - this.lengthY, this.x1 + (this.lengthX * 2), this.y1 + this.lengthY, this.depth - 1, null, "", this.quadTree); parentNode.bottomleft = this; } if (nodePosition == "bottomright") { parentNode = new Node(this.x1 - this.lengthX, this.y1 - this.lengthY, this.x1 + this.lengthX, this.y1 + this.lengthY, this.depth - 1, null, "", this.quadTree); parentNode.bottomright = this; } this.parent = parentNode; parentNode.recursiveCount = this.recursiveCount; if (!parentNode.topleft) { parentNode.topleft = new Node(parentNode.x1, parentNode.y1, parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 0, this.quadTree); } if (!parentNode.topright) { parentNode.topright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1, parentNode.x2, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 1, this.quadTree); } if (!parentNode.bottomleft) { parentNode.bottomleft = new Node(parentNode.x1, parentNode.y1 + parentNode.halfLengthY, parentNode.x1 + parentNode.halfLengthX, parentNode.y2, this.depth, parentNode, parentNode.name + 2, this.quadTree); } if (!parentNode.bottomright) { parentNode.bottomright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, parentNode.x2, parentNode.y2, this.depth, parentNode, parentNode.name + 3, this.quadTree); } parentNode.reconfigureNames(""); return parentNode; } startReconfigureNames () { let parent = this; while (parent.parent) { parent = parent.parent; } parent.reconfigureNames(""); } reconfigureNames (name) { this.name = name; const children = this.getChildren(); for (let i = 0, l = children.length; i < l; i++) { children[i].reconfigureNames(name + i); } } removeNodes () { this.topleft = null; this.topright = null; this.bottomleft = null; this.bottomright = null; } show (ctx) { ctx.strokeStyle = "white"; ctx.strokeRect(this.x1, this.y1, this.lengthX, this.lengthY); } }