• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2010 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.replica.replicaisland;
18 
19 import android.content.res.AssetManager;
20 
21 import java.io.IOException;
22 import java.io.InputStream;
23 
24 /**
25  * Collision detection system.  Provides a ray-based interface for finding surfaces in the collision
26  * world.   This version is based on a collision world of line segments, organized into an array of
27  * tiles.  The underlying detection algorithm isn't relevant to calling code, however, so this class
28  * may be extended to provide a completely different collision detection scheme.
29  *
30  * This class also provides a system for runtime-generated collision segments.  These temporary
31  * segments are cleared each frame, and consequently must be constantly re-submitted if they are
32  * intended to persist.  Temporary segments are useful for dynamic solid objects, such as moving
33  * platforms.
34  *
35  * CollisionSystem.TileVisitor is an interface for traversing individual collision tiles.  Ray casts
36  * can be used to run user code over the collision world by passing different TileVisitor
37  * implementations to executeRay.  Provided is TileTestVisitor, a visitor that compares the segments
38  * of each tile visited with the ray and searches for points of intersection.
39  *
40  */
41 public class CollisionSystem extends BaseObject {
42     private TiledWorld mWorld;
43     private CollisionTile[] mCollisionTiles;
44     private LineSegmentPool mSegmentPool;
45     private int mTileWidth;
46     private int mTileHeight;
47     private TileTestVisitor mTileSegmentTester;
48     private FixedSizeArray<LineSegment> mTemporarySegments;
49     private FixedSizeArray<LineSegment> mPendingTemporarySegments;
50     private byte[] mWorkspaceBytes;     // Included here to avoid runtime allocation during file io.
51 
52     private static final int MAX_TEMPORARY_SEGMENTS = 256;
53 
CollisionSystem()54     public CollisionSystem() {
55         super();
56         mTileSegmentTester = new TileTestVisitor();
57         mSegmentPool = new LineSegmentPool(MAX_TEMPORARY_SEGMENTS);
58 
59         mTemporarySegments = new FixedSizeArray<LineSegment>(MAX_TEMPORARY_SEGMENTS);
60         mPendingTemporarySegments = new FixedSizeArray<LineSegment>(MAX_TEMPORARY_SEGMENTS);
61 
62         mWorkspaceBytes = new byte[4];
63     }
64 
65     @Override
reset()66     public void reset() {
67         mWorld = null;
68         mCollisionTiles = null;
69 
70         final int count = mTemporarySegments.getCount();
71         for (int x = 0; x < count; x++) {
72             mSegmentPool.release(mTemporarySegments.get(x));
73             mTemporarySegments.set(x, null);
74         }
75         mTemporarySegments.clear();
76 
77         final int pendingCount = mPendingTemporarySegments.getCount();
78         for (int x = 0; x < pendingCount; x++) {
79             mSegmentPool.release(mPendingTemporarySegments.get(x));
80             mPendingTemporarySegments.set(x, null);
81         }
82         mPendingTemporarySegments.clear();
83     }
84 
85     /* Sets the current collision world to the supplied tile world. */
initialize(TiledWorld world, int tileWidth, int tileHeight)86     public void initialize(TiledWorld world, int tileWidth, int tileHeight) {
87         mWorld = world;
88 
89         mTileWidth = tileWidth;
90         mTileHeight = tileHeight;
91     }
92 
93     /**
94      * Casts a ray into the collision world.  The ray is bound by the start and end points supplied.
95      * The first intersecting segment that is found is returned; in the case where more than one
96      * segment is found, the segment closest to the start point is returned.
97      *
98      * @param startPoint  The starting point for the ray in world units.
99      * @param endPoint  The end point for the ray in world units.
100      * @param movementDirection  If set, only segments with normals that oppose this direction will
101      *      be counted as valid intersections.  If null, all intersecting segments will be
102      *      considered valid.
103      * @param hitPoint  The point of intersection between a ray and a surface, if one is found.
104      * @param hitNormal  The normal of the intersecting surface if an intersection is found.
105      * @param excludeObject If set, dynamic surfaces from this object will be ignored.
106      * @return  true if a valid intersecting surface was found, false otherwise.
107      */
108     // TODO: switch to return data as a HitPoint.
castRay(Vector2 startPoint, Vector2 endPoint, Vector2 movementDirection, Vector2 hitPoint, Vector2 hitNormal, GameObject excludeObject)109     public boolean castRay(Vector2 startPoint, Vector2 endPoint, Vector2 movementDirection,
110             Vector2 hitPoint, Vector2 hitNormal, GameObject excludeObject) {
111 
112         boolean hit = false;
113 
114         mTileSegmentTester.setup(movementDirection, mTileWidth, mTileHeight);
115 
116         if (mCollisionTiles != null &&
117                 executeRay(startPoint, endPoint, hitPoint, hitNormal, mTileSegmentTester) != -1) {
118             hit = true;
119         }
120 
121         if (mTemporarySegments.getCount() > 0) {
122             VectorPool vectorPool = sSystemRegistry.vectorPool;
123             Vector2 tempHitPoint = vectorPool.allocate();
124             Vector2 tempHitNormal = vectorPool.allocate();
125 
126             if (testSegmentAgainstList(mTemporarySegments, startPoint, endPoint, tempHitPoint,
127                     tempHitNormal, movementDirection, excludeObject)) {
128                 if (hit) {
129                     // Check to see whether this collision is closer to the one we already found or
130                     // not.
131                     final float firstCollisionDistance = startPoint.distance2(hitPoint);
132                     if (firstCollisionDistance > startPoint.distance2(tempHitPoint)) {
133                         // The temporary surface is closer.
134                         hitPoint.set(tempHitPoint);
135                         hitNormal.set(tempHitNormal);
136                     }
137                 } else {
138                     hit = true;
139                     hitPoint.set(tempHitPoint);
140                     hitNormal.set(tempHitNormal);
141                 }
142             }
143 
144             vectorPool.release(tempHitPoint);
145             vectorPool.release(tempHitNormal);
146         }
147 
148         return hit;
149     }
150 
testBox(float left, float right, float top, float bottom, Vector2 movementDirection, FixedSizeArray<HitPoint> hitPoints, GameObject excludeObject, boolean testDynamicSurfacesOnly)151     public boolean testBox(float left, float right, float top, float bottom,
152             Vector2 movementDirection, FixedSizeArray<HitPoint> hitPoints,
153             GameObject excludeObject, boolean testDynamicSurfacesOnly) {
154 
155         boolean foundHit = false;
156 
157         // Test against the background.
158         if (!testDynamicSurfacesOnly) {
159             float startX = left;
160             float endX = right;
161             float startY = bottom;
162             float endY = top;
163             int xIncrement = 1;
164             int yIncrement = 1;
165 
166             if (movementDirection != null) {
167                 if (movementDirection.x < 0.0f) {
168                     startX = right;
169                     endX = left;
170                     xIncrement = -1;
171                 }
172                 if (movementDirection.y < 0.0f) {
173                     startY = top;
174                     endY = bottom;
175                     yIncrement = -1;
176                 }
177             }
178             final int startTileX = Utils.clamp((int)(startX / mTileWidth), 0, mWorld.getWidth() - 1);
179             final int endTileX = Utils.clamp((int)(endX / mTileWidth), 0, mWorld.getWidth() - 1);
180             final int startTileY = Utils.clamp((int)(startY / mTileHeight), 0, mWorld.getHeight() - 1);
181             final int endTileY = Utils.clamp((int)(endY / mTileHeight), 0, mWorld.getHeight() - 1);
182 
183             VectorPool vectorPool = sSystemRegistry.vectorPool;
184             Vector2 worldTileOffset = vectorPool.allocate();
185 
186             final int[][] tileArray = mWorld.getTiles();
187             final int worldHeight = mWorld.getHeight() - 1;
188 
189 
190             for (int y = startTileY; y != endTileY + yIncrement; y += yIncrement) {
191                 for (int x = startTileX; x != endTileX + xIncrement; x += xIncrement) {
192                     final int tileIndex = tileArray[x][worldHeight - y];
193                     if (tileIndex >= 0 && tileIndex < mCollisionTiles.length
194                             && mCollisionTiles[tileIndex] != null) {
195 
196                         final float xOffset = x * mTileWidth;
197                         final float yOffset = y * mTileHeight;
198 
199                         final float tileSpaceLeft = left - xOffset;
200                         final float tileSpaceRight = right - xOffset;
201                         final float tileSpaceTop = top - yOffset;
202                         final float tileSpaceBottom = bottom - yOffset;
203 
204                         worldTileOffset.set(xOffset, yOffset);
205 
206                         boolean hit = testBoxAgainstList(mCollisionTiles[tileIndex].segments,
207                                 tileSpaceLeft, tileSpaceRight, tileSpaceTop, tileSpaceBottom,
208                                 movementDirection, excludeObject, worldTileOffset, hitPoints);
209 
210                         if (hit) {
211                             foundHit = true;
212                         }
213 
214                     }
215                 }
216             }
217 
218             vectorPool.release(worldTileOffset);
219         }
220         // temporary segments
221         boolean tempHit = testBoxAgainstList(mTemporarySegments,
222                 left, right, top, bottom,
223                 movementDirection, excludeObject, Vector2.ZERO, hitPoints);
224 
225         if (tempHit) {
226             foundHit = true;
227         }
228 
229 
230 
231         return foundHit;
232     }
233 
234     /* Inserts a temporary surface into the collision world.  It will persist for one frame. */
addTemporarySurface(Vector2 startPoint, Vector2 endPoint, Vector2 normal, GameObject ownerObject)235     public void addTemporarySurface(Vector2 startPoint, Vector2 endPoint, Vector2 normal,
236             GameObject ownerObject) {
237         LineSegment newSegment = mSegmentPool.allocate();
238 
239         newSegment.set(startPoint, endPoint, normal);
240         newSegment.setOwner(ownerObject);
241 
242         mPendingTemporarySegments.add(newSegment);
243     }
244 
245     @Override
update(float timeDelta, BaseObject parent)246     public void update(float timeDelta, BaseObject parent) {
247         // Clear temporary surfaces
248         final int count = mTemporarySegments.getCount();
249         if (mCollisionTiles != null && count > 0) {
250             for (int x = 0; x < count; x++) {
251                 mSegmentPool.release(mTemporarySegments.get(x));
252                 mTemporarySegments.set(x, null);
253             }
254             mTemporarySegments.clear();
255         }
256 
257         // Temporary surfaces must persist for one frame in order to be reliable independent of
258         // frame execution order.  So each frame we queue up inserted segments and then swap them
259         // into activity when this system is updated.
260         FixedSizeArray<LineSegment> swap = mTemporarySegments;
261         mTemporarySegments = mPendingTemporarySegments;
262         mPendingTemporarySegments = swap;
263     }
264 
265     /**
266      * Shoots a ray through the collision world.  This function is similar to executeRay() below,
267      * except that it is optimized for straight lines (either completely horizontal or completely
268      * vertical).
269      *
270      * @param startPoint  The starting point for the ray, in world space.
271      * @param endPoint  The ending point for the ray in world space.
272      * @param hitPoint  Set to the intersection coordinates if an intersection is found.
273      * @param hitNormal  Set to the normal of the intersecting surface if an intersection is found.
274      * @param visitor  Class defining what work to perform at each tile step.
275      * @return  The index of the tile that intersected the ray, or -1 if no intersection was found.
276      */
executeStraigtRay(final Vector2 startPoint, final Vector2 endPoint, final int startTileX, final int startTileY, final int endTileX, final int endTileY, final int deltaX, final int deltaY, Vector2 hitPoint, Vector2 hitNormal, TileVisitor visitor)277     protected int executeStraigtRay(final Vector2 startPoint, final Vector2 endPoint,
278             final int startTileX, final int startTileY, final int endTileX, final int endTileY,
279             final int deltaX, final int deltaY,
280             Vector2 hitPoint, Vector2 hitNormal, TileVisitor visitor) {
281 
282         int currentX = startTileX;
283         int currentY = startTileY;
284 
285         int xIncrement = 0;
286         int yIncrement = 0;
287         int distance = 0;
288 
289         if (deltaX != 0) {
290             distance = Math.abs(deltaX) + 1;
291             xIncrement = Utils.sign(deltaX);
292         } else if (deltaY != 0) {
293             distance = Math.abs(deltaY) + 1;
294             yIncrement = Utils.sign(deltaY);
295         }
296 
297         int hitTile = -1;
298         final int worldHeight = mWorld.getHeight() - 1;
299         final int[][] tileArray = mWorld.getTiles();
300         for (int x = 0; x < distance; x++) {
301             final int tileIndex = tileArray[currentX][worldHeight - currentY];
302             if (tileIndex >= 0 && tileIndex < mCollisionTiles.length
303                     && mCollisionTiles[tileIndex] != null) {
304                 if (visitor.visit(mCollisionTiles[tileIndex], startPoint, endPoint,
305                         hitPoint, hitNormal, currentX, currentY)) {
306                     hitTile = tileIndex;
307                     break;
308                 }
309             }
310             currentX += xIncrement;
311             currentY += yIncrement;
312         }
313 
314         return hitTile;
315     }
316 
317     /**
318      * Shoots a ray through the collision world.  Since the collision world is a 2D array of tiles,
319      * this algorithm traces a line in tile space and tests against each non-empty tile it visits.
320      * The Bresenham line algorithm is used for the actual traversal, but the action taken at each
321      * tile is defined by the visitor class passed to this function.
322      *
323      * @param startPoint  The starting point for the ray, in world space.
324      * @param endPoint  The ending point for the ray in world space.
325      * @param hitPoint  Set to the intersection coordinates if an intersection is found.
326      * @param hitNormal  Set to the normal of the intersecting surface if an intersection is found.
327      * @param visitor  Class defining what work to perform at each tile step.
328      * @return  The index of the tile that intersected the ray, or -1 if no intersection was found.
329      */
executeRay(Vector2 startPoint, Vector2 endPoint, Vector2 hitPoint, Vector2 hitNormal, TileVisitor visitor)330     protected int executeRay(Vector2 startPoint, Vector2 endPoint,
331             Vector2 hitPoint, Vector2 hitNormal, TileVisitor visitor) {
332 
333         final int worldHeight = mWorld.getHeight();
334         final int worldWidth = mWorld.getWidth();
335 
336         final int startTileX = worldToTileColumn(startPoint.x, worldWidth);
337         final int startTileY = worldToTileRow(startPoint.y, worldHeight);
338 
339         final int endTileX = worldToTileColumn(endPoint.x, worldWidth);
340         final int endTileY = worldToTileRow(endPoint.y, worldHeight);
341 
342         int currentX = startTileX;
343         int currentY = startTileY;
344 
345         final int deltaX = endTileX - startTileX;
346         final int deltaY = endTileY - startTileY;
347 
348         int hitTile = -1;
349 
350         if (deltaX == 0 || deltaY == 0) {
351             hitTile = executeStraigtRay(startPoint, endPoint, startTileX, startTileY,
352                     endTileX, endTileY, deltaX, deltaY, hitPoint, hitNormal, visitor);
353         } else {
354 
355             final int xIncrement = deltaX != 0 ? Utils.sign(deltaX) : 0;
356             final int yIncrement = deltaY != 0 ? Utils.sign(deltaY) : 0;
357 
358             // Note: I'm deviating from the Bresenham algorithm here by adding one to force the end
359             // tile to be visited.
360             final int lateralDelta = (endTileX > 0 && endTileX < worldWidth - 1) ? Math.abs(deltaX) + 1 : Math.abs(deltaX);
361             final int verticalDelta = (endTileY > 0 && endTileY < worldHeight - 1) ? Math.abs(deltaY) + 1 : Math.abs(deltaY);
362 
363             final int deltaX2 = lateralDelta * 2;
364             final int deltaY2 = verticalDelta * 2;
365 
366             final int worldHeightMinusOne = worldHeight - 1;
367             final int[][]tileArray = mWorld.getTiles();
368 
369             // Bresenham line algorithm in tile space.
370             if (lateralDelta >= verticalDelta) {
371                 int error = deltaY2 - lateralDelta;
372                 for (int i = 0; i < lateralDelta; i++) {
373                     final int tileIndex = tileArray[currentX][worldHeightMinusOne - currentY];
374                     if (tileIndex >= 0 && tileIndex < mCollisionTiles.length
375                             && mCollisionTiles[tileIndex] != null) {
376                         if (visitor.visit(mCollisionTiles[tileIndex], startPoint, endPoint,
377                                 hitPoint, hitNormal, currentX, currentY)) {
378                             hitTile = tileIndex;
379                             break;
380                         }
381                     }
382 
383                     if (error > 0) {
384                         currentY += yIncrement;
385                         error -= deltaX2;
386                     }
387 
388                     error += deltaY2;
389                     currentX += xIncrement;
390                 }
391             }
392             else if (verticalDelta >= lateralDelta) {
393                 int error = deltaX2 - verticalDelta;
394 
395                 for (int i = 0; i < verticalDelta; i++) {
396                     final int tileIndex = tileArray[currentX][worldHeightMinusOne - currentY];
397                     if (tileIndex >= 0 && tileIndex < mCollisionTiles.length
398                             && mCollisionTiles[tileIndex] != null) {
399                         if (visitor.visit(mCollisionTiles[tileIndex], startPoint, endPoint,
400                                 hitPoint, hitNormal, currentX, currentY)) {
401                             hitTile = tileIndex;
402                             break;
403                         }
404                     }
405 
406                     if (error > 0) {
407                         currentX += xIncrement;
408                         error -= deltaY2;
409                     }
410 
411                     error += deltaX2;
412                     currentY += yIncrement;
413                 }
414             }
415         }
416         return hitTile;
417     }
418 
worldToTileColumn(final float x, final int width)419     protected final int worldToTileColumn(final float x, final int width) {
420         return Utils.clamp((int)Math.floor(x / mTileWidth), 0, width - 1);
421     }
422 
worldToTileRow(float y, final int height)423     protected final int worldToTileRow(float y, final int height) {
424         return Utils.clamp((int)Math.floor(y / mTileHeight), 0, height - 1);
425     }
426 
427     /*
428      * Given a list of segments and a ray, this function performs an intersection search and
429      * returns the closest intersecting segment, if any exists.
430      */
testSegmentAgainstList(FixedSizeArray<LineSegment> segments, Vector2 startPoint, Vector2 endPoint, Vector2 hitPoint, Vector2 hitNormal, Vector2 movementDirection, GameObject excludeObject)431     protected static boolean testSegmentAgainstList(FixedSizeArray<LineSegment> segments,
432             Vector2 startPoint, Vector2 endPoint, Vector2 hitPoint, Vector2 hitNormal,
433             Vector2 movementDirection, GameObject excludeObject) {
434         boolean foundHit = false;
435         float closestDistance = -1;
436         float hitX = 0;
437         float hitY = 0;
438         float normalX = 0;
439         float normalY = 0;
440         final int count = segments.getCount();
441         final Object[] segmentArray = segments.getArray();
442         for (int x = 0; x < count; x++) {
443             LineSegment segment = (LineSegment)segmentArray[x];
444             // If a movement direction has been passed, filter out invalid surfaces by ignoring
445             // those that do not oppose movement.  If no direction has been passed, accept all
446             // surfaces.
447             final float dot = movementDirection.length2() > 0.0f ?
448                     movementDirection.dot(segment.mNormal) : -1.0f;
449 
450             if (dot < 0.0f &&
451                     (excludeObject == null || segment.owner != excludeObject) &&
452                     segment.calculateIntersection(startPoint, endPoint, hitPoint)) {
453                 final float distance = hitPoint.distance2(startPoint);
454 
455                 if (!foundHit || closestDistance > distance) {
456                     closestDistance = distance;
457                     foundHit = true;
458                     normalX = segment.mNormal.x;
459                     normalY = segment.mNormal.y;
460                     // Store the components on their own so we don't have to allocate a vector
461                     // in this loop.
462                     hitX = hitPoint.x;
463                     hitY = hitPoint.y;
464                 }
465             }
466         }
467 
468         if (foundHit) {
469             hitPoint.set(hitX, hitY);
470             hitNormal.set(normalX, normalY);
471         }
472         return foundHit;
473     }
474 
testBoxAgainstList(FixedSizeArray<LineSegment> segments, float left, float right, float top, float bottom, Vector2 movementDirection, GameObject excludeObject, Vector2 outputOffset, FixedSizeArray<HitPoint> outputHitPoints)475     protected static boolean testBoxAgainstList(FixedSizeArray<LineSegment> segments,
476             float left, float right, float top, float bottom,
477             Vector2 movementDirection, GameObject excludeObject, Vector2 outputOffset,
478             FixedSizeArray<HitPoint> outputHitPoints) {
479         int hitCount = 0;
480         final int maxSegments = outputHitPoints.getCapacity() - outputHitPoints.getCount();
481         final int count = segments.getCount();
482         final Object[] segmentArray = segments.getArray();
483 
484         VectorPool vectorPool = sSystemRegistry.vectorPool;
485         HitPointPool hitPool = sSystemRegistry.hitPointPool;
486 
487         Vector2 tempHitPoint = vectorPool.allocate();
488 
489         for (int x = 0; x < count && hitCount < maxSegments; x++) {
490             LineSegment segment = (LineSegment)segmentArray[x];
491             // If a movement direction has been passed, filter out invalid surfaces by ignoring
492             // those that do not oppose movement.  If no direction has been passed, accept all
493             // surfaces.
494             final float dot = movementDirection.length2() > 0.0f ?
495                     movementDirection.dot(segment.mNormal) : -1.0f;
496 
497             if (dot < 0.0f &&
498                     (excludeObject == null || segment.owner != excludeObject) &&
499                     segment.calculateIntersectionBox(left, right, top, bottom, tempHitPoint)) {
500 
501                 Vector2 hitPoint = vectorPool.allocate(tempHitPoint);
502                 Vector2 hitNormal = vectorPool.allocate(segment.mNormal);
503 
504                 hitPoint.add(outputOffset);
505                 HitPoint hit = hitPool.allocate();
506 
507                 hit.hitPoint = hitPoint;
508                 hit.hitNormal = hitNormal;
509 
510                 outputHitPoints.add(hit);
511 
512                 hitCount++;
513             }
514         }
515 
516         vectorPool.release(tempHitPoint);
517 
518         return hitCount > 0;
519     }
520 
521     /*
522      * Loads line segments from a binary file and builds the tiled collision database
523      * accordingly.
524      */
loadCollisionTiles(InputStream stream)525     public boolean loadCollisionTiles(InputStream stream) {
526         boolean success = false;
527         AssetManager.AssetInputStream byteStream = (AssetManager.AssetInputStream) stream;
528         int signature;
529 
530         // TODO: this is a hack.  I really should only allocate an array that is the size of the
531         // tileset, but at this point I don't actually know that size, so I allocate a buffer that's
532         // probably large enough.
533         mCollisionTiles = new CollisionTile[256];
534         try {
535             signature = (byte)byteStream.read();
536             if (signature == 52) {
537                 // This file has the following deserialization format:
538                 //   read the number of tiles
539                 //   for each tile
540                 //     read the tile id
541                 //     read the number of segments
542                 //     for each segment
543                 //       read startx, starty, endx, endy, normalx, normaly
544                 final int tileCount = byteStream.read();
545                 final int size = (1 + 1 + 4 + 4 + 4 + 4 + 4 + 4) * tileCount;
546                 if (byteStream.available() >= size) {
547                     for (int x = 0; x < tileCount; x++) {
548                         final int tileIndex = byteStream.read();
549                         final int segmentCount = byteStream.read();
550 
551                         if (mCollisionTiles[tileIndex] == null && segmentCount > 0) {
552                             mCollisionTiles[tileIndex] = new CollisionTile(segmentCount);
553                         }
554 
555                         for (int y = 0; y < segmentCount; y++) {
556                             byteStream.read(mWorkspaceBytes, 0, 4);
557                             final float startX = Utils.byteArrayToFloat(mWorkspaceBytes);
558                             byteStream.read(mWorkspaceBytes, 0, 4);
559                             final float startY = Utils.byteArrayToFloat(mWorkspaceBytes);
560                             byteStream.read(mWorkspaceBytes, 0, 4);
561                             final float endX = Utils.byteArrayToFloat(mWorkspaceBytes);
562                             byteStream.read(mWorkspaceBytes, 0, 4);
563                             final float endY = Utils.byteArrayToFloat(mWorkspaceBytes);
564                             byteStream.read(mWorkspaceBytes, 0, 4);
565                             final float normalX = Utils.byteArrayToFloat(mWorkspaceBytes);
566                             byteStream.read(mWorkspaceBytes, 0, 4);
567                             final float normalY = Utils.byteArrayToFloat(mWorkspaceBytes);
568 
569                             // TODO: it might be wise to pool line segments.  I don't think that
570                             // this data will be loaded very often though, so this is ok for now.
571                             LineSegment newSegment = new LineSegment();
572                             newSegment.mStartPoint.set(startX, startY);
573                             newSegment.mEndPoint.set(endX, endY);
574                             newSegment.mNormal.set(normalX, normalY);
575 
576                             mCollisionTiles[tileIndex].addSegment(newSegment);
577                         }
578                     }
579                 }
580             }
581         } catch (IOException e) {
582             //TODO: figure out the best way to deal with this.  Assert?
583         }
584 
585         return success;
586     }
587 
588 
589     /**
590      * An interface for visiting tiles during a ray cast.  Implementations of TileVisitor
591      * can be passed to executeRay(); the visit() function will be invoked for each tile touched by
592      * the ray until the traversal is completed or visit() returns false.
593      */
594     public abstract class TileVisitor extends AllocationGuard {
TileVisitor()595         public TileVisitor() {
596             super();
597         }
598 
599         // If true is returned, tile scanning continues.  Otherwise it stops.
visit(CollisionTile tile, Vector2 startPoint, Vector2 endPoint, Vector2 hitPoint, Vector2 hitNormal, int tileX, int tileY)600         public abstract boolean visit(CollisionTile tile, Vector2 startPoint, Vector2 endPoint,
601             Vector2 hitPoint, Vector2 hitNormal, int tileX, int tileY);
602     }
603 
604     /**
605      * TileTestVisitor tests the ray against a list of segments assigned to each tile.  If any
606      * segment in any tile of the ray's path is found to be intersecting with the ray, traversal
607      * stops and intersection information is recorded.
608      */
609     protected class TileTestVisitor extends TileVisitor {
610         // These vectors are all temporary storage variables allocated as class members to avoid
611         // runtime allocation.
612         private Vector2 mDelta;
613         private Vector2 mTileSpaceStart;
614         private Vector2 mTileSpaceEnd;
615         private Vector2 mTileSpaceOffset;
616         private int mTileHeight;
617         private int mTileWidth;
618 
TileTestVisitor()619         public TileTestVisitor() {
620             super();
621             mDelta = new Vector2();
622             mTileSpaceStart = new Vector2();
623             mTileSpaceEnd = new Vector2();
624             mTileSpaceOffset = new Vector2();
625         }
626 
627         /**
628          * Sets the visitor up for a ray test.  Initializes the size of the tiles and the direction
629          * of movement by which intersections should be filtered.
630          */
setup(Vector2 movementDirection, int tileWidth, int tileHeight)631         public void setup(Vector2 movementDirection, int tileWidth, int tileHeight) {
632             if (movementDirection != null) {
633                 mDelta.set(movementDirection);
634                 mDelta.normalize();
635             } else {
636                 mDelta.zero();
637             }
638             mTileWidth = tileWidth;
639             mTileHeight = tileHeight;
640         }
641 
642         /**
643          * Converts the ray into tile space and then compares it to the segments
644          * stored in the current tile.
645          */
646         @Override
visit(CollisionTile tile, Vector2 startPoint, Vector2 endPoint, Vector2 hitPoint, Vector2 hitNormal, int tileX, int tileY)647         public boolean visit(CollisionTile tile, Vector2 startPoint, Vector2 endPoint,
648                 Vector2 hitPoint, Vector2 hitNormal, int tileX, int tileY) {
649             mTileSpaceOffset.set(tileX * mTileWidth, tileY * mTileHeight);
650             mTileSpaceStart.set(startPoint);
651             mTileSpaceStart.subtract(mTileSpaceOffset);
652             mTileSpaceEnd.set(endPoint);
653             mTileSpaceEnd.subtract(mTileSpaceOffset);
654             // find all the hits in the tile and pick the closest to the start point.
655             boolean foundHit = testSegmentAgainstList(tile.segments, mTileSpaceStart, mTileSpaceEnd,
656                     hitPoint, hitNormal, mDelta, null);
657 
658             if (foundHit) {
659                 // The hitPoint is in tile space, so convert it back to world space.
660                 hitPoint.add(mTileSpaceOffset);
661             }
662 
663             return foundHit;
664         }
665     }
666 
667     /**
668      * A class describing a single surface in the collision world.  Surfaces are stored as a line
669      * segment and a normal. The normal must be normalized (its length must be 1.0) and should
670      * describe the direction that the segment "pushes against" in a collision.
671      */
672     protected class LineSegment extends AllocationGuard {
673         private Vector2 mStartPoint;
674         private Vector2 mEndPoint;
675         public Vector2 mNormal;
676         public GameObject owner;
677 
LineSegment()678         public LineSegment() {
679             super();
680             mStartPoint = new Vector2();
681             mEndPoint = new Vector2();
682             mNormal = new Vector2();
683         }
684 
685         /* Sets up the line segment.  Values are copied to local storage. */
set(Vector2 start, Vector2 end, Vector2 norm)686         public void set(Vector2 start, Vector2 end, Vector2 norm) {
687             mStartPoint.set(start);
688             mEndPoint.set(end);
689             mNormal.set(norm);
690         }
691 
setOwner(GameObject ownerObject)692         public void setOwner(GameObject ownerObject) {
693             owner = ownerObject;
694         }
695         /**
696          * Checks to see if these lines intersect by projecting one onto the other and then
697          * assuring that the collision point is within the range of each segment.
698          */
calculateIntersection(Vector2 otherStart, Vector2 otherEnd, Vector2 hitPoint)699         public boolean calculateIntersection(Vector2 otherStart, Vector2 otherEnd,
700                 Vector2 hitPoint) {
701             boolean intersecting = false;
702 
703             // Reference: http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
704             final float x1 = mStartPoint.x;
705             final float x2 = mEndPoint.x;
706             final float x3 = otherStart.x;
707             final float x4 = otherEnd.x;
708             final float y1 = mStartPoint.y;
709             final float y2 = mEndPoint.y;
710             final float y3 = otherStart.y;
711             final float y4 = otherEnd.y;
712 
713             final float denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
714             if (denom != 0) {
715              final float uA = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
716              final float uB = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
717 
718              if (uA >= 0.0f && uA <= 1.0f && uB >= 0.0f && uB <= 1.0f) {
719                  final float hitX = x1 + (uA * (x2 - x1));
720                  final float hitY = y1 + (uA * (y2 - y1));
721                  hitPoint.set(hitX, hitY);
722                  intersecting = true;
723              }
724             }
725             return intersecting;
726         }
727 
728         // Based on http://www.garagegames.com/community/resources/view/309
calculateIntersectionBox(float left, float right, float top, float bottom, Vector2 hitPoint)729         public boolean calculateIntersectionBox(float left, float right, float top, float bottom,
730                 Vector2 hitPoint) {
731 
732             final float x1 = mStartPoint.x;
733             final float x2 = mEndPoint.x;
734             final float y1 = mStartPoint.y;
735             final float y2 = mEndPoint.y;
736 
737             float startIntersect;
738             float endIntersect;
739             float intersectTimeStart = 0.0f;
740             float intersectTimeEnd = 1.0f;
741 
742             if (x1 < x2) {
743                 if (x1 > right || x2 < left) {
744                     return false;
745                 }
746                 final float deltaX = x2 - x1;
747                 startIntersect = (x1 < left) ? (left - x1) / deltaX : 0.0f;
748                 endIntersect = (x2 > right) ? (right - x1) / deltaX : 1.0f;
749             } else {
750                 if (x2 > right || x1 < left) {
751                     return false;
752                 }
753                 final float deltaX = x2 - x1;
754                 startIntersect = (x1 > right) ? (right - x1) / deltaX : 0.0f;
755                 endIntersect = (x2 < left) ? (left - x1) / deltaX : 1.0f;
756             }
757 
758             if (startIntersect > intersectTimeStart) {
759                 intersectTimeStart = startIntersect;
760             }
761             if (endIntersect < intersectTimeEnd) {
762                 intersectTimeEnd = endIntersect;
763             }
764             if (intersectTimeEnd < intersectTimeStart) {
765                 return false;
766             }
767 
768             // y
769             if (y1 < y2) {
770                 if (y1 > top || y2 < bottom) {
771                     return false;
772                 }
773                 final float deltaY = y2 - y1;
774                 startIntersect = (y1 < bottom) ? (bottom - y1) / deltaY : 0.0f;
775                 endIntersect = (y2 > top) ? (top - y1) / deltaY : 1.0f;
776             } else {
777                 if (y2 > top || y1 < bottom) {
778                     return false;
779                 }
780                 final float deltaY = y2 - y1;
781                 startIntersect = (y1 > top) ? (top - y1) / deltaY : 0.0f;
782                 endIntersect = (y2 < bottom) ? (bottom - y1) / deltaY : 1.0f;
783             }
784 
785             if (startIntersect > intersectTimeStart) {
786                 intersectTimeStart = startIntersect;
787             }
788             if (endIntersect < intersectTimeEnd) {
789                 intersectTimeEnd = endIntersect;
790             }
791             if (intersectTimeEnd < intersectTimeStart) {
792                 return false;
793             }
794 
795             hitPoint.set(mEndPoint);
796             hitPoint.subtract(mStartPoint);
797             hitPoint.multiply(intersectTimeStart);
798             hitPoint.add(mStartPoint);
799 
800             return true;
801         }
802 
803     }
804 
805     /**
806      * A pool of line segments.
807      */
808     protected class LineSegmentPool extends TObjectPool<LineSegment> {
LineSegmentPool()809         public LineSegmentPool() {
810             super();
811         }
812 
LineSegmentPool(int count)813         public LineSegmentPool(int count) {
814             super(count);
815         }
816 
817         @Override
reset()818         public void reset() {
819 
820         }
821 
822         @Override
fill()823         protected void fill() {
824             for (int x = 0; x < getSize(); x++) {
825                 getAvailable().add(new LineSegment());
826             }
827         }
828 
829         @Override
release(Object entry)830         public void release(Object entry) {
831             ((LineSegment)entry).owner = null;
832             super.release(entry);
833         }
834 
835 
836     }
837 
838     /**
839      * A single collision tile.  Manages a list of line segments.
840      */
841     protected class CollisionTile extends AllocationGuard {
842         public FixedSizeArray<LineSegment> segments;
843 
CollisionTile(int maxSegments)844         public CollisionTile(int maxSegments) {
845             super();
846             segments = new FixedSizeArray<LineSegment>(maxSegments);
847         }
848 
addSegment(LineSegment segment)849         public boolean addSegment(LineSegment segment) {
850             boolean success = false;
851             if (segments.getCount() < segments.getCapacity()) {
852                 success = true;
853             }
854             segments.add(segment);
855             return success;
856         }
857     }
858 }
859