/** * 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; this.merge = []; } /** * 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); } if (!this.root.hasChildren) { this.root.add(object); object.node = this.root; return; } const node = this.findNodeFromRoot(object); node.add(object); object.node = node; } /** * 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) { if (!this.root.hasChildren) { this.root.remove(object); object.node = null; return; } const node = object.node; object.node = null; node && node.remove(object); } /** * 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 result = []; const nodes = []; types = Array.isArray(types) ? types : [types]; nodes.push(this.root); while (nodes.length > 0) { const node = nodes.pop(); if (this.isInRange(position, range, node)) { if (!node.hasChildren) { let filtered = node.getObjects() .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0); if (types != null) { filtered = filtered.filter(obj => types.some(t => obj instanceof t)); } result.push(...filtered); } else { nodes.push(...node.getChildren()); } } } return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position)); } getObjectsWithTagInRange = function (position, range, tags) { const result = []; const nodes = []; tags = Array.isArray(tags) ? tags : [tags]; nodes.push(this.root); while (nodes.length > 0) { const node = nodes.pop(); if (this.isInRange(position, range, node)) { if (!node.hasChildren) { let filtered = node.getObjects() .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0); if (tags != null) { filtered = filtered.filter(obj => tags.some(t => obj.tags.some(tag => tag == t))); } result.push(...filtered); } else { nodes.push(...node.getChildren()); } } } return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position)); }; 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) { if (dirOfOob == "L") { this.root = this.root.createParent("bottomright"); } 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"); } } 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) { if (!this.root.hasChildren) { return this.root; } let node = this.root.findChildNode(position); while (node.hasChildren) { node = node.findChildNode(position); } return node; } countObjectsInChild (parentNode) { if (!parentNode.hasChildren) { return 0; } return parentNode.topleft.size() + parentNode.topright.size() + parentNode.bottomleft.size() + parentNode.bottomright.size(); } 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) { this.root.update(deltaTime); } 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 () { return !this.hasChildren && this.parent && this.parent.recursiveCount <= this.quadTree.bucketSize; } get shouldSplit () { return !this.hasChildren && this.recursiveCount > this.quadTree.bucketSize; } 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.markedForCleanup = false; this.timer = 0; this.quadTree = quadTree; } addCount () { this.recursiveCount++; this.parent && this.parent.addCount(); if (this.shouldSplit) { this.divide(); } } removeCount () { this.recursiveCount--; this.parent && this.parent.removeCount(); 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(); } } } remove (obj) { if (this.objects && this.objects.indexOf(obj) >= 0) { this.objects = this.objects.filter(ind => ind != obj); this.removeCount(); } } 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 = []; } 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; } if (position.x >= this.topleft.x1 && position.x <= this.topleft.x2 && position.y >= this.topleft.y1 && position.y <= this.topleft.y2) { return this.topleft; } else if (position.x >= this.bottomleft.x1 && position.x <= this.bottomleft.x2 && position.y >= this.bottomleft.y1 && position.y <= this.bottomleft.y2) { return this.bottomleft; } else if (position.x >= this.topright.x1 && position.x <= this.topright.x2 && position.y >= this.topright.y1 && position.y <= this.topright.y2) { return this.topright; } else if (position.x >= this.bottomright.x1 && position.x <= this.bottomright.x2 && position.y >= this.bottomright.y1 && position.y <= this.bottomright.y2) { return this.bottomright; } } 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; } update (deltaTime) { if (this.hasChildren) { this.topleft.update(deltaTime); this.topright.update(deltaTime); this.bottomleft.update(deltaTime); this.bottomright.update(deltaTime); } } /** * Retrieves the same-level neighbour if possible, or the lowest level if not. * * @param {string} direction L, R, U or D */ getNeighbour (direction) { const name = this.name.split(""); const hmap = { 0: 1, 1: 0, 2: 3, 3: 2 }; const vmap = { 0: 2, 2: 0, 1: 3, 3: 1 }; switch (direction) { case "L": if (name[name.length - 1] == "0" || name[name.length - 1] == "2") { if (name.length > 1) { name[name.length - 2] = hmap[name[name.length - 2]]; } else { return null; } } name[name.length - 1] = hmap[name[name.length - 1]]; break; case "R": if (name[name.length - 1] == "1" || name[name.length - 1] == "3") { if (name.length > 1) { name[name.length - 2] = hmap[name[name.length - 2]]; } else { return null; } } name[name.length - 1] = hmap[name[name.length - 1]]; break; case "U": if (name[name.length - 1] == "0" || name[name.length - 1] == "1") { if (name.length > 1) { name[name.length - 2] = vmap[name[name.length - 2]]; } else { return null; } } name[name.length - 1] = vmap[name[name.length - 1]]; break; case "D": if (name[name.length - 1] == "2" || name[name.length - 1] == "3") { if (name.length > 1) { name[name.length - 2] = vmap[name[name.length - 2]]; } else { return null; } } name[name.length - 1] = vmap[name[name.length - 1]]; break; } return this.quadTree.traverseTo(name.join("")); } show (ctx) { ctx.strokeStyle = "white"; ctx.strokeRect(this.x1, this.y1, this.lengthX, this.lengthY); } }