1 /**
  2  * The Render Engine
  3  * SpatialGrid
  4  *
  5  * @fileoverview A simple collision model which divides a finite space up into
  6  *               a coarse grid to assist in quickly finding objects within that
  7  *               space.
  8  *
  9  * @author: Brett Fattori (brettf@renderengine.com)
 10  *
 11  * @author: $Author: bfattori $
 12  * @version: $Revision: 1555 $
 13  *
 14  * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com)
 15  *
 16  * Permission is hereby granted, free of charge, to any person obtaining a copy
 17  * of this software and associated documentation files (the "Software"), to deal
 18  * in the Software without restriction, including without limitation the rights
 19  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 20  * copies of the Software, and to permit persons to whom the Software is
 21  * furnished to do so, subject to the following conditions:
 22  *
 23  * The above copyright notice and this permission notice shall be included in
 24  * all copies or substantial portions of the Software.
 25  *
 26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 27  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 28  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 29  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 30  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 31  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 32  * THE SOFTWARE.
 33  *
 34  */
 35 
 36 // The class this file defines and its required classes
 37 R.Engine.define({
 38     "class":"R.collision.broadphase.SpatialGrid",
 39     "requires":[
 40         "R.collision.broadphase.AbstractCollisionModel",
 41         "R.collision.broadphase.SpatialGridNode",
 42         "R.math.Math2D",
 43         "R.math.Rectangle2D",
 44         "R.math.Point2D"
 45     ]
 46 });
 47 
 48 /**
 49  * @class A structure which divides a finite space up into a coarse grid to
 50  *        perform "broad phase" collision determinations within the space.
 51  *        After the PCL (potential collision list) is built, a "narrow phase"
 52  *        collision model would need to be employed to determine accurate collision
 53  *        response.  Using AABB overlapping for simple true/false determinations is
 54  *        one method.  Another method would be to use something like GJK to determine
 55  *        by how much two objects' convex hulls are overlapped.
 56  *        <p/>
 57  *        A spatial grid is defined by the size of the space and the number of
 58  *        divisions within that space.  A smaller PCL will result from a larger
 59  *        number of divisions, but the amount of data required to store the cells
 60  *        also increases.  Also, larger numbers of divisions means that as objects
 61  *        move, the determination of which cell the object is within increases as
 62  *        well.
 63  *
 64  * @constructor
 65  * @description Create an instance of a spatial grid model
 66  * @param width {Number} The width of the area
 67  * @param height {Number} The height of the area
 68  * @param divisions {Number} The number of divisions along both axis
 69  * @extends R.spatial.AbstractSpatialContainer
 70  */
 71 R.collision.broadphase.SpatialGrid = function () {
 72     "use strict";
 73     return R.collision.broadphase.AbstractCollisionModel.extend(/** @scope R.collision.broadphase.SpatialGrid.prototype */{
 74 
 75         divisions:1,
 76 
 77         xLocator:1,
 78         yLocator:1,
 79 
 80         accuracy:0,
 81         pclCache:null,
 82 
 83         /** @private */
 84         constructor:function (width, height, divisions) {
 85             this.base("SpatialGrid", width, height);
 86 
 87             // Divide the space up into a grid
 88             var gX = Math.floor(width / divisions);
 89             var gY = Math.floor(height / divisions);
 90             this.divisions = divisions;
 91             this.xLocator = 1 / gX;
 92             this.yLocator = 1 / gY;
 93             this.accuracy = R.collision.broadphase.SpatialGrid.HIGH_ACCURACY;
 94 
 95             var grid = [];
 96             this.setRoot(grid);
 97 
 98             for (var y = 0; y < this.divisions; y++) {
 99                 for (var x = 0; x < this.divisions; x++) {
100                     var rect = R.math.Rectangle2D.create(x * gX, y * gY, gX, gY);
101                     grid[x + (y * this.divisions)] = new R.collision.broadphase.SpatialGridNode(rect);
102                 }
103             }
104 
105             this.pclCache = {};
106         },
107 
108         /**
109          * Reset the collision model, removing any references to objects
110          * from all collision nodes.
111          */
112         reset:function () {
113             for (var pcl in this.pclCache) {
114                 this.pclCache[pcl].clear();
115             }
116         },
117 
118         /**
119          * Releases the spatial grid back into the object pool.  See {@link PooledObject#release}
120          * for more information.
121          */
122         release:function () {
123             this.base();
124             this.divisions = 1;
125             this.xLocator = 1;
126             this.yLocator = 1;
127             this.accuracy = 0;
128         },
129 
130         /*
131          addObject: function(obj, point) {
132          var oldNodes = this.getObjectSpatialData(obj, "nodes"), wb = obj.getWorldBox();
133          if (oldNodes != null) {
134          // See if the object's world box is still in all of the nodes
135          var full = R.math.Rectangle2D.create(oldNodes[0].getRect()), n;
136          for (n = 1; n < oldNodes.length; n++) {
137          full.join(oldNodes[n].getRect());
138          }
139          if (!full.containsRect(wb)) {
140          // The object is not within the same nodes
141          for (n = 0; n < oldNodes.length; n++) {
142          oldNodes.removeObject(obj);
143          }
144          } else {
145          // The object is in the same nodes
146          full.destroy();
147          return;
148          }
149          }
150 
151          // Find the nodes which contain the world box
152          var pt = R.math.Point2D.create(0,0), tlNode = this.findNodePoint(pt.set(wb.x, wb.y)),
153          trNode = this.findNodePoint(pt.set(wb.x, wb.r)),
154          blNode = this.findNodePoint(pt.set(wb.x, wb.b)),
155          brNode = this.findNodePoint(pt.set(wb.r, wb.b)), addTo = [];
156 
157          if (tlNode != null) {
158          tlNode.addObject(obj);
159          addTo.push(tlNode);
160          }
161          if (trNode != null) {
162          trNode.addObject(obj);
163          addTo.push(trNode);
164          }
165          if (blNode != null) {
166          blNode.addObject(obj);
167          addTo.push(blNode);
168          }
169          if (brNode != null) {
170          brNode.addObject(obj);
171          addTo.push(brNode);
172          }
173 
174          if (addTo.length != 0) {
175          this.setObjectSpatialData(obj, "nodes", addTo);
176          }
177 
178          pt.destroy();
179          full.destroy();
180          },
181          */
182 
183         /**
184          * Set the accuracy of the collision checks to either {@link #GOOD_ACCURACY},
185          * {@link #BETTER_ACCURACY}, or {@link #HIGH_ACCURACY}.  See {@link #getPCL} for
186          * an explanation of the levels of accuracy.
187          *
188          * @param accuracy {Number} The level of accuracy during PCL generation
189          */
190         setAccuracy:function (accuracy) {
191             this.accuracy = (accuracy > R.collision.broadphase.SpatialGrid.BETTER_ACCURACY ||
192                 accuracy < R.collision.broadphase.SpatialGrid.GOOD_ACCURACY) ?
193                 R.collision.broadphase.SpatialGrid.BETTER_ACCURACY : accuracy;
194         },
195 
196         /**
197          * Get the accuracy level of collision checks.
198          * @return {Number} The accuracy level
199          */
200         getAccuracy:function () {
201             return this.accuracy;
202         },
203 
204         /**
205          * Find the node that contains the specified point.
206          *
207          * @param point {R.math.Point2D} The point to locate the node for
208          * @return {R.spatial.SpatialGridNode}
209          */
210         findNodePoint:function (point) {
211             return this.getRoot()[Math.floor(point.x * this.xLocator) + (Math.floor(point.y * this.yLocator) * this.divisions)];
212         },
213 
214         /**
215          * Get the normalized node Id for the root node of a PCL
216          * @private
217          */
218         getNodeId:function (point) {
219             return Math.floor(point.x * this.xLocator) + (Math.floor(point.y * this.yLocator) * this.divisions);
220         },
221 
222         /**
223          * Get a node within the grid.  The X and Y coordinates are node coordinates, and
224          * not world coordinates.  For example, if a grid has 5 divisions, the cells are
225          * numbered 0 through 4 on each axis.
226          *
227          * @param x {Number} The virtual X coordinate in our grid
228          * @param y {Number} The virtual Y coordinate in our grid
229          * @return {R.collision.broadphase.SpatialGridNode}
230          */
231         getNode:function (x, y) {
232             // Normalize X and Y within the bounds of the grid
233             x = x < 0 ? 0 : (x > this.divisions - 1 ? this.divisions - 1 : x);
234             y = y < 0 ? 0 : (y > this.divisions - 1 ? this.divisions - 1 : y);
235             return this.getRoot()[x + (y * this.divisions)];
236         },
237 
238         /**
239          * Get the number of divisions along the horizontal and vertical axis.  The
240          * divisions are uniform for both axis, so the cells of the grid won't necessarily
241          * be square.
242          * @return {Number}
243          */
244         getDivisions:function () {
245             return this.divisions;
246         },
247 
248         /**
249          * @private
250          */
251         checkNode:function (nodeList, x, y, id) {
252             var node = this.getNode(x, y);
253             if (node.isDirty()) {
254                 nodeList.push(node);
255             }
256         },
257 
258         /**
259          * Get the list of objects with respect to the point given.  Objects will
260          * be returned from the nodes that make up the grid node containing
261          * the point, and the following adjacent nodes:
262          * <ul>
263          * <li><b>Good Accuracy</b> - Just the node containing the point (G)</li>
264          * <li><b>Better Accuracy</b> - The four polar nodes around the center (G, B)</li>
265          * <li><b>High Accuracy</b> - The eight nodes around the center (G, B, H)</li>
266          * </ul>
267          * For example, if you had a 3x3 grid with the object in the center node, the nodes
268          * marked below would be included in the result set:
269          * <pre>
270          *  +---+---+---+
271          *  | H | B | H |
272          *  +---+---+---+
273          *  | B | G | B |
274          *  +---+---+---+
275          *  | H | B | H |
276          *  +---+---+---+
277          * </pre>
278          *
279          * @param point {R.math.Point2D} The point to begin the search at.
280          * @return {R.struct.Container} A container of objects found that could be collision targets
281          */
282         getPCL:function (point) {
283             var p = this.normalizePoint(point);
284 
285             // Get the root node
286             var x = Math.floor(p.x * this.xLocator);
287             var y = Math.floor(p.y * this.yLocator);
288 
289             // Iff the object is inside the grid
290             if (x >= 0 && x <= this.divisions - 1 &&
291                 y >= 0 && y <= this.divisions - 1) {
292 
293                 // Create cache nodes for each normalized point in the grid
294                 var id = this.getNodeId(p);
295                 if (this.pclCache[id] == null) {
296                     this.pclCache[id] = R.struct.Container.create();
297                 }
298 
299                 var cachedPCL = this.pclCache[id];
300 
301                 // Build the node set
302                 var nodes = [], n;
303 
304                 // Start with GOOD_ACCURACY
305                 this.checkNode(nodes, x, y, id);
306 
307                 // if our borders cross the margin, we can drop up to two nodes
308                 if (this.accuracy >= R.collision.broadphase.SpatialGrid.BETTER_ACCURACY) {
309                     // -- Polar nodes
310                     if (x > 0 && x < this.divisions - 1 && y > 0 && y < this.divisions - 1) {
311                         this.checkNode(nodes, x - 1, y, id);
312                         this.checkNode(nodes, x + 1, y, id);
313                         this.checkNode(nodes, x, y - 1, id);
314                         this.checkNode(nodes, x, y + 1, id);
315                     } else if (x == 0 && y > 0 && y < this.divisions - 1) {
316                         this.checkNode(nodes, x + 1, y, id);
317                         this.checkNode(nodes, x, y - 1, id);
318                         this.checkNode(nodes, x, y + 1, id);
319                     } else if (x == this.divisions - 1 && y > 0 && y < this.divisions - 1) {
320                         this.checkNode(nodes, x - 1, y, id);
321                         this.checkNode(nodes, x, y - 1, id);
322                         this.checkNode(nodes, x, y + 1, id);
323                     } else if (y == 0 && x > 0 && x < this.divisions - 1) {
324                         this.checkNode(nodes, x - 1, y, id);
325                         this.checkNode(nodes, x + 1, y, id);
326                         this.checkNode(nodes, x, y + 1, id);
327                     } else if (y == this.divisions - 1 && x > 0 && x < this.divisions - 1) {
328                         this.checkNode(nodes, x - 1, y, id);
329                         this.checkNode(nodes, x + 1, y, id);
330                         this.checkNode(nodes, x, y - 1, id);
331                     } else if (x == 0 && y == 0) {
332                         this.checkNode(nodes, x + 1, y, id);
333                         this.checkNode(nodes, x, y + 1, id);
334                     } else if (x == this.divisions - 1 && y == 0) {
335                         this.checkNode(nodes, x - 1, y, id);
336                         this.checkNode(nodes, x, y + 1, id);
337                     } else if (x == 0 && y == this.divisions - 1) {
338                         this.checkNode(nodes, x + 1, y, id);
339                         this.checkNode(nodes, x, y - 1, id);
340                     } else if (x == this.divisions - 1 && y == this.divisions - 1) {
341                         this.checkNode(nodes, x - 1, y, id);
342                         this.checkNode(nodes, x, y - 1, id);
343                     }
344                 }
345 
346                 // For highest number of checks, we'll include all eight surrounding nodes
347                 if (this.accuracy == R.collision.broadphase.SpatialGrid.HIGH_ACCURACY) {
348                     // -- Corner nodes
349                     if (x > 0 && x < this.divisions - 1 && y > 0 && y < this.divisions - 1) {
350                         this.checkNode(nodes, x - 1, y - 1, id);
351                         this.checkNode(nodes, x + 1, y + 1, id);
352                         this.checkNode(nodes, x - 1, y + 1, id);
353                         this.checkNode(nodes, x + 1, y - 1, id);
354                     } else if (x == 0 && y > 0 && y < this.divisions - 1) {
355                         this.checkNode(nodes, x + 1, y + 1, id);
356                         this.checkNode(nodes, x + 1, y - 1, id);
357                     } else if (x == this.divisions - 1 && y > 0 && y < this.divisions - 1) {
358                         this.checkNode(nodes, x - 1, y + 1, id);
359                         this.checkNode(nodes, x - 1, y - 1, id);
360                     } else if (y == 0 && x > 0 && x < this.divisions - 1) {
361                         this.checkNode(nodes, x - 1, y + 1, id);
362                         this.checkNode(nodes, x + 1, y + 1, id);
363                     } else if (y == this.divisions - 1 && x > 0 && x < this.divisions - 1) {
364                         this.checkNode(nodes, x - 1, y - 1, id);
365                         this.checkNode(nodes, x + 1, y - 1, id);
366                     } else if (x == 0 && y == 0) {
367                         this.checkNode(nodes, x + 1, y + 1, id);
368                     } else if (x == this.divisions - 1 && y == 0) {
369                         this.checkNode(nodes, x - 1, y + 1, id);
370                     } else if (x == 0 && y == this.divisions - 1) {
371                         this.checkNode(nodes, x + 1, y - 1, id);
372                     } else if (x == this.divisions - 1 && y == this.divisions - 1) {
373                         this.checkNode(nodes, x - 1, y - 1, id);
374                     }
375                 }
376 
377                 // If there are any nodes which changed, update the PCL cache
378                 if (nodes.length != 0) {
379                     R.Engine.pclRebuilds++;
380 
381                     cachedPCL.clear();
382                     for (var d = 0; d < nodes.length; d++) {
383                         nodes[d].clearDirty();
384                         if (nodes[d].getCount() != 0) {
385                             cachedPCL.add(nodes[d]);
386                         }
387                     }
388                 }
389 
390                 return cachedPCL;
391             }
392 
393             p.destroy();
394 
395             // Outside the grid, return the empty container
396             return R.struct.Container.EMPTY;
397         },
398 
399         /**
400          * Returns all objects within every node of the spatial grid.
401          * @return {R.struct.Container} A container with all objects in the spatial grid
402          */
403         getObjects:function () {
404             var objs = this.base();
405             R.engine.Support.forEach(this.getRoot(), function (node) {
406                 objs.addAll(node.getObjects());
407             });
408             return objs;
409         }
410 
411         /* pragma:DEBUG_START */
412 
413         /**
414          * Dump the cached PCLs to the console so they can be inspected.  Passing an
415          * object to the method will return the PCL which contains that object.
416          * @param [obj] {Object} The object to find in the PCL, or <code>null</code> to return
417          *    all caches.
418          */, debugPCLCaches:function (obj) {
419             R.debug.Console.setDebugLevel(R.debug.Console.DEBUGLEVEL_DEBUG);
420             for (var pcl in this.pclCache) {
421                 for (var itr = this.pclCache[pcl].iterator(); itr.hasNext();) {
422                     var node = itr.next();
423                     if (obj) {
424                         if (node.getObjects.contains(obj)) {
425                             R.debug.Console.debug(pcl, node.getObjects());
426                             break;
427                         }
428                     } else {
429                         R.debug.Console.debug(pcl, node.getObjects());
430                     }
431                 }
432             }
433         },
434 
435         update:function (renderContext, time, dt) {
436             if (!R.Engine.getDebugMode()) {
437                 return;
438             }
439 
440             renderContext.pushTransform();
441 
442             this.base(renderContext, time, dt);
443 
444             // Draw the grid and highlight cells which contain objects
445             var vp = renderContext.getViewport(), xStep = vp.w / this.divisions, yStep = vp.h / this.divisions,
446                 pSt = R.math.Point2D.create(0, 0), pEn = R.math.Point2D.create(0, 0),
447                 rect = R.math.Rectangle2D.create(0, 0, 1, 1), x, y;
448 
449             // Grid
450             for (x = 0, y = 0; x < vp.w;) {
451                 renderContext.setLineStyle("gray");
452                 renderContext.drawLine(pSt.set(x, 0), pEn.set(x, vp.h));
453                 renderContext.drawLine(pSt.set(0, y), pEn.set(vp.w, y));
454                 x += xStep;
455                 y += yStep;
456             }
457             pSt.destroy();
458             pEn.destroy();
459 
460             // Occupied Cells
461             for (var c = 0, len = this.getRoot().length; c < len; c++) {
462                 if (this.getRoot()[c].getCount() != 0) {
463                     x = (c % this.divisions) * xStep;
464                     y = Math.floor(c / this.divisions) * yStep;
465                     renderContext.setFillStyle("rgba(192,192,192,0.4)");
466                     renderContext.drawFilledRectangle(rect.set(x, y, xStep, yStep));
467                 }
468             }
469 
470             renderContext.popTransform();
471         }
472         /* pragma:DEBUG_END */
473 
474     }, /** @scope R.collision.broadphase.SpatialGrid.prototype */{
475         /**
476          * Get the class name of this object
477          *
478          * @return {String} "R.collision.broadphase.SpatialGrid"
479          */
480         getClassName:function () {
481             return "R.collision.broadphase.SpatialGrid";
482         },
483 
484         /**
485          * Collision checks are limited to the exact node where the
486          * object being tested resides.
487          * @type {Number}
488          */
489         GOOD_ACCURACY:0,
490 
491         /**
492          * Collision checks are performed in the node where the object
493          * being tested resides, and in the four surrounding polar nodes.
494          * @type {Number}
495          * @deprecated
496          */
497         BEST_ACCURACY:1,
498 
499         /**
500          * Collision checks are performed in the node where the object
501          * being tested resides, and in the four surrounding polar nodes.
502          * @type {Number}
503          */
504         BETTER_ACCURACY:1,
505 
506         /**
507          * Collision checks are performed in the node where the object
508          * being tested resides, and in the eight surrounding nodes.
509          * @type {Number}
510          */
511         HIGH_ACCURACY:2
512     });
513 
514 };