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