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