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 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 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. */ 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. 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 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. */ 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 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 */ 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 */ 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 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 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 */ 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 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 */ 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 { 595 public TileVisitor() { 596 super(); 597 } 598 599 // If true is returned, tile scanning continues. Otherwise it stops. 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 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 */ 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 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 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. */ 686 public void set(Vector2 start, Vector2 end, Vector2 norm) { 687 mStartPoint.set(start); 688 mEndPoint.set(end); 689 mNormal.set(norm); 690 } 691 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 */ 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 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> { 809 public LineSegmentPool() { 810 super(); 811 } 812 813 public LineSegmentPool(int count) { 814 super(count); 815 } 816 817 @Override 818 public void reset() { 819 820 } 821 822 @Override 823 protected void fill() { 824 for (int x = 0; x < getSize(); x++) { 825 getAvailable().add(new LineSegment()); 826 } 827 } 828 829 @Override 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 844 public CollisionTile(int maxSegments) { 845 super(); 846 segments = new FixedSizeArray<LineSegment>(maxSegments); 847 } 848 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
