1 /** 2 * The Render Engine 3 * AbstractSpatialContainer 4 * 5 * @fileoverview An abstract broad-phase collision model. 6 * 7 * @author: Brett Fattori (brettf@renderengine.com) 8 * 9 * @author: $Author: bfattori $ 10 * @version: $Revision: 1555 $ 11 * 12 * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com) 13 * 14 * Permission is hereby granted, free of charge, to any person obtaining a copy 15 * of this software and associated documentation files (the "Software"), to deal 16 * in the Software without restriction, including without limitation the rights 17 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 18 * copies of the Software, and to permit persons to whom the Software is 19 * furnished to do so, subject to the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be included in 22 * all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 25 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 26 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 27 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 28 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 29 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 30 * THE SOFTWARE. 31 * 32 */ 33 34 // The class this file defines and its required classes 35 R.Engine.define({ 36 "class":"R.collision.broadphase.AbstractCollisionModel", 37 "requires":[ 38 "R.engine.BaseObject", 39 "R.struct.Container" 40 ] 41 }); 42 43 /** 44 * @class An abstract class to represent broad-phase collision models. Broad-phase models 45 * contain game-world objects and can report on potential objects within a defined 46 * space of that container. 47 * 48 * @param name {String} The name of the model 49 * @param width {Number} The total width of the model's space 50 * @param height {Number} The total height of the model's space 51 * @extends R.engine.BaseObject 52 * @constructor 53 * @description Abstract class for all broad-phase collision models 54 */ 55 R.collision.broadphase.AbstractCollisionModel = function () { 56 "use strict"; 57 return R.engine.BaseObject.extend(/** @scope R.collision.broadphase.AbstractCollisionModel.prototype */{ 58 59 root:null, 60 width:0, 61 height:0, 62 pcl:null, 63 64 /** @private */ 65 constructor:function (name, width, height) { 66 this.base(name || "BroadPhaseCollisionModel"); 67 this.width = width; 68 this.height = height; 69 this.pcl = R.struct.Container.create(); 70 }, 71 72 /** 73 * Release the spatial container back into the pool for reuse 74 */ 75 release:function () { 76 this.base(); 77 this.root = null; 78 this.width = 0; 79 this.height = 0; 80 this.pcl = null; 81 }, 82 83 /** 84 * Get the width of the model's world space. 85 * @return {Number} The width 86 */ 87 getWidth:function () { 88 return this.width; 89 }, 90 91 /** 92 * Get the height of the model's world space. 93 * @return {Number} The height 94 */ 95 getHeight:function () { 96 return this.height; 97 }, 98 99 /** 100 * Get the root object of the model. 101 * @return {Object} The root 102 */ 103 getRoot:function () { 104 return this.root; 105 }, 106 107 /** 108 * Set the root object of the model. 109 * 110 * @param root {Object} The root object of this model 111 */ 112 setRoot:function (root) { 113 this.root = root; 114 }, 115 116 /** 117 * [ABSTRACT] Reset the collision model, removing any references to objects 118 * from all collision nodes. 119 */ 120 reset:function () { 121 }, 122 123 /** 124 * [ABSTRACT] Find the node that contains the specified point. 125 * 126 * @param point {R.math.Point2D} The point to locate the node for 127 * @return {R.spatial.AbstractSpatialNode} 128 */ 129 findNodePoint:function (point) { 130 return null; 131 }, 132 133 /** 134 * Normalize a point to keep it within the boundaries of the collision model. 135 * @param point {R.math.Point2D} The point 136 * @return {R.math.Point2D} The normalized point 137 */ 138 normalizePoint:function (point) { 139 // Keep it within the boundaries 140 var p = R.math.Point2D.create(point); 141 p.x = p.x < 0 ? 0 : p.x > this.getWidth() ? this.getWidth() : p.x; 142 p.y = p.y < 0 ? 0 : p.y > this.getHeight() ? this.getHeight() : p.y; 143 return p; 144 }, 145 146 /** 147 * Add an object to the node which corresponds to the position of the object provided 148 * provided. Adding an object at a specific point will remove it from whatever 149 * node it was last in. 150 * 151 * @param obj {R.engine.BaseObject} The object to add to the collision model 152 * @param point {R.math.Point2D} The world position where the object is 153 */ 154 addObject:function (obj, point) { 155 var p = this.normalizePoint(point); 156 157 // See if the object is already in a node and remove it 158 var oldNode = this.getObjectSpatialData(obj, "lastNode"); 159 if (oldNode != null) { 160 if (!oldNode.contains(p)) { 161 // The object is no longer in the same node 162 oldNode.removeObject(obj); 163 } else { 164 // The object hasn't left the node 165 p.destroy(); 166 return; 167 } 168 } 169 170 // Find the node by position and add the object to it 171 var node = this.findNodePoint(p); 172 if (node != null) { 173 node.addObject(obj); 174 175 // Update the collision data on the object 176 this.setObjectSpatialData(obj, "lastNode", node); 177 } 178 179 p.destroy(); 180 }, 181 182 /** 183 * Remove an object from the collision model. 184 * 185 * @param obj {R.engine.BaseObject} The object to remove 186 */ 187 removeObject:function (obj) { 188 var oldNode = this.getObjectSpatialData(obj, "lastNode"); 189 if (oldNode != null) { 190 oldNode.removeObject(obj); 191 } 192 this.clearObjectSpatialData(obj); 193 }, 194 195 /** 196 * Get the spatial data for the game object. If <tt>key</tt> is provided, only the 197 * data for <tt>key</tt> will be returned. If the data has not yet been assigned, 198 * an empty object will be created to contain the data. 199 * 200 * @param obj {R.engine.BaseObject} The object which has the data 201 * @param [key] {String} Optional key which contains the data, or <tt>null</tt> for the 202 * entire data model. 203 */ 204 getObjectSpatialData:function (obj, key) { 205 var mData = obj.getObjectDataModel(R.collision.broadphase.AbstractCollisionModel.DATA_MODEL); 206 if (mData == null) { 207 mData = obj.setObjectDataModel(R.collision.broadphase.AbstractCollisionModel.DATA_MODEL, {}); 208 } 209 return key ? mData[key] : mData; 210 }, 211 212 /** 213 * Set a key, within the game object's spatial data, to a specific value. This allows a 214 * collision system, or model, to store related information directly on a game object. 215 * The data can be retrieved, as needed, from within the collision system or model. 216 * 217 * @param obj {R.engine.BaseObject} The object to receive the data 218 * @param key {String} The key to set the data for 219 * @param value {Object} The value to assign to the key 220 */ 221 setObjectSpatialData:function (obj, key, value) { 222 var mData = this.getObjectSpatialData(obj); 223 mData[key] = value; 224 }, 225 226 /** 227 * Clear all of the spatial data on the given game object. 228 * 229 * @param obj {R.engine.BaseObject} The object which has the data model 230 */ 231 clearObjectSpatialData:function (obj) { 232 obj.setObjectDataModel(R.collision.broadphase.AbstractCollisionModel.DATA_MODEL, null); 233 }, 234 235 /** 236 * Returns a potential collision list (PCL) of objects that are contained 237 * within the defined sub-space of the container. 238 * 239 * @param point {R.math.Point2D} The point to begin the search at. 240 * @return {R.struct.Container} An empty PCL 241 */ 242 getPCL:function (point) { 243 return this.pcl; 244 }, 245 246 /** 247 * Returns all objects within the collision model. 248 * @return {R.struct.Container} A container of all objects in the model 249 */ 250 getObjects:function () { 251 return R.struct.Container.create(); 252 }, 253 254 /** 255 * Returns all objects within the spatial container of a particular 256 * class type. 257 * 258 * @param clazz {Object} A class type to restrict the collection to 259 * @return {Array} An array of objects in the container, filtered by class 260 */ 261 getObjectsOfType:function (clazz) { 262 return this.getObjects().filter(function (obj) { 263 return (obj instanceof clazz); 264 }, this); 265 }, 266 267 /** 268 * Query the collision model using a testing function. All objects in the 269 * model will be passed through the function, and if the function returns 270 * <code>true</code>, indicating it passed the test, it will be included 271 * in the list. 272 * @param testFn {Function} The testing function 273 * @return {Array} An array of objects in the container which pass the test 274 */ 275 query:function (testFn) { 276 return this.getObjects().filter(testFn, this); 277 }, 278 279 /** 280 * Query the collision model for objects near a point. Specify the point 281 * and the radius from that point to test. The test will be performed 282 * against the position of the object being tested, not its boundaries. 283 * @param point {R.math.Point2D} 284 * @param radius {Number} 285 * @return {Array} An array of objects in the container which satisfy the query 286 */ 287 queryNear:function (point, radius) { 288 return this.query(function (obj) { 289 var pos = obj.getPosition(); 290 var distSqr = (point.x - pos.x) * (point.x - pos.x) + 291 (point.y - pos.y) * (point.y - pos.y); 292 return (distSqr < radius); 293 }); 294 }, 295 296 /** 297 * Cast a ray through the collision model, looking for collisions along the 298 * ray. If a collision is found, a {@link R.struct.CollisionData} object 299 * will be returned or <code>null</code> if otherwise. If the object being 300 * tested has a convex hull, that will be used to test for collision with 301 * the ray. Otherwise, its world box will be used. 302 * <p/> 303 * If a collision occurs, the value stored in {@link R.struct.CollisionData#shape1} 304 * is the object which was collided with. The value in {@link R.struct.CollisionData#impulseVector} 305 * is the point at which the intersection was determined. 306 * 307 * @param fromPoint {R.math.Point2D} The origination of the ray 308 * @param direction {R.math.Vector2D} A vector whose magnitude specifies the direction and 309 * length of the ray being cast. The ray will be truncated at {@link #MAX_RAY_LENGTH}. 310 * @param [testFn] {Function} A test function which will be executed when a collision occurs. The 311 * argument to the function will be a {@link R.struct.CollisionData}. Returning <code>true</code> will indicate 312 * that the raycast testing should stop, <code>false</code> to continue testing. 313 * @return {R.struct.CollisionData} The collision info, or <code>null</code> if 314 * no collision would occur. 315 */ 316 castRay:function (fromPoint, direction, testFn) { 317 // Get all of the points along the line and test them against the 318 // collision model. At the first collision, we stop performing any more checks. 319 var begin = R.math.Point2D.create(fromPoint), end = R.math.Point2D.create(fromPoint), 320 dir = R.math.Vector2D.create(direction), line, 321 pt = 0, test, node, itr, object, wt = R.Engine.worldTime, dt = R.Engine.lastTime, 322 vec = R.math.Vector2D.create(direction).neg(), did = false; 323 324 // Create the collision structure only once 325 var collision = R.struct.CollisionData.create(0, vec, null, null, null, wt, dt); 326 327 // Make sure the length isn't greater than the max 328 if (dir.len() > R.collision.broadphase.AbstractCollisionModel.MAX_RAY_LENGTH) { 329 dir.normalize().mul(R.collision.broadphase.AbstractCollisionModel.MAX_RAY_LENGTH); 330 } 331 332 // Use Bresenham's algorithm to calculate the points along the line 333 end.add(dir); 334 line = R.math.Math2D.bresenham(begin, end); 335 336 /* pragma:DEBUG_START */ 337 if (R.Engine.getDebugMode() && arguments[3]) { 338 var start = R.math.Point2D.create(begin), finish = R.math.Point2D.create(end); 339 340 arguments[3].postRender(function () { 341 this.setLineStyle("yellow"); 342 this.setLineWidth(1); 343 this.drawLine(start, end); 344 start.destroy(); 345 end.destroy(); 346 }); 347 } 348 /* pragma:DEBUG_END */ 349 350 351 while (!collision.shape1 && pt < line.length) { 352 test = line[pt++]; 353 354 // If the point is outside our boundaries, we can move to the next point 355 if (test.x < 0 || test.y < 0 || test.x > this.width || test.y > this.height) { 356 continue; 357 } 358 359 // Find the node for the current point 360 node = this.findNodePoint(test); 361 362 // Get all of the objects in the node 363 for (itr = node.getObjects().iterator(); itr.hasNext();) { 364 object = itr.next(); 365 did = false; 366 367 // If the object has a collision hull, we'll test against that 368 // otherwise we'll use its world box 369 if (object.getCollisionHull) { 370 var hull = object.getCollisionHull(); 371 if (hull.getType() == R.collision.ConvexHull.CONVEX_CIRCLE) { 372 // Point to circle hull test 373 did = R.math.Math2D.pointInCircle(test, hull.getCenter(), hull.getRadius()); 374 } else { 375 // Point to polygon hull test 376 did = R.math.Math2D.pointInPoly(test, hull.getVertexes()); 377 } 378 } else if (object.getWorldBox && object.getWorldBox().containsPoint(test)) { 379 did = true; 380 } 381 382 // If we find a collision, prep collision structure 383 if (did) { 384 collision.shape1 = object; 385 collision.impulseVector = R.math.Vector2D.create(test); 386 387 if (!testFn) { 388 // No test function, just return the collision 389 break; 390 } else if (testFn(collision.shape1)) { 391 // Test function returned true, return the collision 392 break; 393 } else { 394 // Test function returned false, move onto another test 395 collision.shape1 = null; 396 collision.impulseVector.destroy(); 397 } 398 } 399 } 400 401 // Clean up the iterator over the objects in the node 402 itr.destroy(); 403 } 404 405 // Clean up a bit 406 begin.destroy(); 407 end.destroy(); 408 dir.destroy(); 409 410 // Destroy the points in the line 411 while (line.length > 0) { 412 line.shift().destroy(); 413 } 414 415 if (collision.shape1 == null) { 416 collision.destroy(); 417 collision = null; 418 } 419 420 return collision; 421 } 422 423 }, /** @scope R.collision.broadphase.AbstractCollisionModel.prototype */ { 424 /** 425 * Get the class name of this object 426 * 427 * @return {String} "R.collision.broadphase.AbstractCollisionModel" 428 */ 429 getClassName:function () { 430 return "R.collision.broadphase.AbstractCollisionModel"; 431 }, 432 433 /** @private */ 434 DATA_MODEL:"BroadPhaseCollisionData", 435 436 /** 437 * The maximum length of a cast ray (1000) 438 * @type {Number} 439 */ 440 MAX_RAY_LENGTH:1000 441 }); 442 443 };