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 };