1 /* 2 * @class jaws.QuadTree 3 * @property {jaws.Rect} bounds Rect(x,y,width,height) defining bounds of tree 4 * @property {number} depth The depth of the root node 5 * @property {array} nodes The nodes of the root node 6 * @property {array} objects The objects of the root node 7 * @example 8 * setup: 9 * var quadtree = new jaws.QuadTree(); 10 * update: 11 * quadtree.collide(sprite or list, sprite or list, callback function); 12 */ 13 var jaws = (function(jaws) { 14 15 /** 16 * Creates an empty quadtree with optional bounds and starting depth 17 * @constructor 18 * @param {jaws.Rect} [bounds] The defining bounds of the tree 19 * @param {number} [depth] The current depth of the tree 20 */ 21 jaws.QuadTree = function(bounds) { 22 this.depth = arguments[1] || 0; 23 this.bounds = bounds || new jaws.Rect(0, 0, jaws.width, jaws.height); 24 this.nodes = []; 25 this.objects = []; 26 }; 27 28 /** 29 * Moves through the nodes and deletes them. 30 * @this {jaws.QuadTree} 31 */ 32 jaws.QuadTree.prototype.clear = function() { 33 this.objects = []; 34 35 for (var i = 0; i < this.nodes.length; i++) { 36 if (typeof this.nodes[i] !== 'undefined') { 37 this.nodes[i].clear(); 38 delete this.nodes[i]; 39 } 40 } 41 }; 42 43 /** 44 * Creates four new branches sub-dividing the current node's width and height 45 * @private 46 * @this {jaws.QuadTree} 47 */ 48 jaws.QuadTree.prototype.split = function() { 49 var subWidth = Math.round((this.bounds.width / 2)); 50 var subHeight = Math.round((this.bounds.height / 2)); 51 var x = this.bounds.x; 52 var y = this.bounds.y; 53 54 this.nodes[0] = new jaws.QuadTree(new jaws.Rect(x + subWidth, y, subWidth, subHeight), this.depth + 1); 55 this.nodes[1] = new jaws.QuadTree(new jaws.Rect(x, y, subWidth, subHeight), this.depth + 1); 56 this.nodes[2] = new jaws.QuadTree(new jaws.Rect(x, y + subHeight, subWidth, subHeight), this.depth + 1); 57 this.nodes[3] = new jaws.QuadTree(new jaws.Rect(x + subWidth, y + subHeight, subWidth, subHeight), this.depth + 1); 58 }; 59 60 /** 61 * Returns the index of a node's branches if passed-in object fits within it 62 * @private 63 * @param {object} pRect An object with the properties x, y, width, and height 64 * @returns {index} The index of nodes[] that matches the dimensions of passed-in object 65 */ 66 jaws.QuadTree.prototype.getIndex = function(pRect) { 67 var index = -1; 68 var verticalMidpoint = this.bounds.x + (this.bounds.width / 2); 69 var horizontalMidpoint = this.bounds.y + (this.bounds.height / 2); 70 71 var topQuadrant = (pRect.y < horizontalMidpoint && pRect.y + pRect.height < horizontalMidpoint); 72 var bottomQuadrant = (pRect.y > horizontalMidpoint); 73 74 if (pRect.x < verticalMidpoint && pRect.x + pRect.width < verticalMidpoint) { 75 if (topQuadrant) { 76 index = 1; 77 } 78 else if (bottomQuadrant) { 79 index = 2; 80 } 81 } 82 else if (pRect.x > verticalMidpoint) { 83 if (topQuadrant) { 84 index = 0; 85 } 86 else if (bottomQuadrant) { 87 index = 3; 88 } 89 } 90 91 return index; 92 }; 93 94 /** 95 * Inserts an object into the quadtree, spliting it into new branches if needed 96 * @param {object} pRect An object with the properties x, y, width, and height 97 */ 98 jaws.QuadTree.prototype.insert = function(pRect) { 99 100 if (!pRect.hasOwnProperty("x") && !pRect.hasOwnProperty("y") && 101 !pRect.hasOwnProperty("width") && !pRect.hasOwnProperty("height")) { 102 return; 103 } 104 105 if (typeof this.nodes[0] !== 'undefined') { 106 var index = this.getIndex(pRect); 107 108 if (index !== -1) { 109 this.nodes[index].insert(pRect); 110 return; 111 } 112 } 113 114 this.objects.push(pRect); 115 116 if (typeof this.nodes[0] === 'undefined') { 117 this.split(); 118 } 119 120 var i = 0; 121 while (i < this.objects.length) { 122 var index = this.getIndex(this.objects[i]); 123 if (index !== -1) { 124 this.nodes[index].insert(this.objects.splice(i, 1)[0]); 125 } 126 else { 127 i++; 128 } 129 } 130 131 }; 132 133 /** 134 * Returns those objects on the branch matching the position of the passed-in object 135 * @param {object} pRect An object with properties x, y, width, and height 136 * @returns {array} The objects on the same branch as the passed-in object 137 */ 138 jaws.QuadTree.prototype.retrieve = function(pRect) { 139 140 if (!pRect.hasOwnProperty("x") && !pRect.hasOwnProperty("y") && 141 !pRect.hasOwnProperty("width") && !pRect.hasOwnProperty("height")) { 142 return; 143 } 144 145 var index = this.getIndex(pRect); 146 var returnObjects = this.objects; 147 if (typeof this.nodes[0] !== 'undefined') { 148 if (index !== -1) { 149 returnObjects = returnObjects.concat(this.nodes[index].retrieve(pRect)); 150 } else { 151 for (var i = 0; i < this.nodes.length; i++) { 152 returnObjects = returnObjects.concat(this.nodes[i].retrieve(pRect)); 153 } 154 } 155 } 156 return returnObjects; 157 }; 158 159 /** 160 * Checks for collisions between objects by creating a quadtree, inserting one or more objects, 161 * and then comparing the results of a retrieval against another single or set of objects. 162 * 163 * With the callback argument, it will call a function and pass the items found colliding 164 * as the first and second argument. 165 * 166 * Without the callback argument, it will return a boolean value if any collisions were found. 167 * 168 * @param {object|array} list1 A single or set of objects with properties x, y, width, and height 169 * @param {object|array} list2 A single or set of objects with properties x, y, width, and height 170 * @param {function} [callback] The function to call per collision 171 * @returns {boolean} If the items (or any within their sets) collide with one another 172 */ 173 jaws.QuadTree.prototype.collide = function(list1, list2, callback) { 174 175 var overlap = false; 176 var tree = new jaws.QuadTree(); 177 var temp = []; 178 179 if (!(list1.forEach)) { 180 temp.push(list1); 181 list1 = temp; 182 } 183 184 if (!(list2.forEach)) { 185 temp = []; 186 temp.push(list2); 187 list2 = temp; 188 } 189 190 list2.forEach(function(el) { 191 tree.insert(el); 192 }); 193 194 list1.forEach(function(el) { 195 if(jaws.collide(el, tree.retrieve(el), callback)) { 196 overlap = true; 197 } 198 }); 199 200 tree.clear(); 201 return overlap; 202 }; 203 204 return jaws; 205 206 })(jaws || {}); 207 208 // Support CommonJS require() 209 if (typeof module !== "undefined" && ('exports' in module)) { 210 module.exports = jaws.QuadTree; 211 } 212