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 java.util.Comparator; 20 21 import com.replica.replicaisland.CollisionParameters.HitType; 22 23 /** 24 * A system for calculating collisions between moving game objects. This system accepts collision 25 * volumes from game objects each frame and performs a series of tests to see which of them 26 * overlap. Collisions are only considered between offending "attack" volumes and receiving 27 * "vulnerability" volumes. This implementation works by using a sweep-and-prune algorithm: 28 * objects to be considered are sorted in the x axis and then compared in one dimension for 29 * overlaps. A bounding volume that encompasses all attack and vulnerability volumes is used for 30 * this test, and when an intersection is found the actual offending and receiving volumes are 31 * compared. If an intersection is detected both objects receive notification via a 32 * HitReactionComponent, if one has been specified. 33 */ 34 public class GameObjectCollisionSystem extends BaseObject { 35 private static final int MAX_COLLIDING_OBJECTS = 256; 36 private static final int COLLISION_RECORD_POOL_SIZE = 256; 37 private static final CollisionVolumeComparator sCollisionVolumeComparator 38 = new CollisionVolumeComparator(); 39 private static CollisionVolume.FlipInfo sFlip = new CollisionVolume.FlipInfo(); 40 private static CollisionVolume.FlipInfo sOtherFlip = new CollisionVolume.FlipInfo(); 41 42 FixedSizeArray<CollisionVolumeRecord> mObjects; 43 CollisionVolumeRecordPool mRecordPool; 44 private boolean mDrawDebugBoundingVolume = false; 45 private boolean mDrawDebugCollisionVolumes = false; 46 47 GameObjectCollisionSystem()48 public GameObjectCollisionSystem() { 49 super(); 50 mObjects = new FixedSizeArray<CollisionVolumeRecord>(MAX_COLLIDING_OBJECTS); 51 mObjects.setComparator(sCollisionVolumeComparator); 52 //mObjects.setSorter(new ShellSorter<CollisionVolumeRecord>()); 53 mRecordPool = new CollisionVolumeRecordPool(COLLISION_RECORD_POOL_SIZE); 54 } 55 56 @Override reset()57 public void reset() { 58 final int count = mObjects.getCount(); 59 60 for (int x = 0; x < count; x++) { 61 mRecordPool.release(mObjects.get(x)); 62 } 63 mObjects.clear(); 64 65 mDrawDebugBoundingVolume = false; 66 mDrawDebugCollisionVolumes = false; 67 } 68 69 /** 70 * Adds a game object, and its related volumes, to the dynamic collision world for one frame. 71 * Once registered for collisions the object may damage other objects via attack volumes or 72 * receive damage from other volumes via vulnerability volumes. 73 * @param object The object to consider for collision. 74 * @param reactionComponent A HitReactionComponent to notify when an intersection is calculated. 75 * If null, the intersection will still occur and no notification will be sent. 76 * @param boundingVolume A volume that describes the game object in space. It should encompass 77 * all of the attack and vulnerability volumes. 78 * @param attackVolumes A list of volumes that can hit other game objects. May be null. 79 * @param vulnerabilityVolumes A list of volumes that can receive hits from other game objects. 80 * May be null. 81 */ registerForCollisions(GameObject object, HitReactionComponent reactionComponent, CollisionVolume boundingVolume, FixedSizeArray<CollisionVolume> attackVolumes, FixedSizeArray<CollisionVolume> vulnerabilityVolumes)82 public void registerForCollisions(GameObject object, 83 HitReactionComponent reactionComponent, 84 CollisionVolume boundingVolume, 85 FixedSizeArray<CollisionVolume> attackVolumes, 86 FixedSizeArray<CollisionVolume> vulnerabilityVolumes) { 87 CollisionVolumeRecord record = mRecordPool.allocate(); 88 if (record != null && object != null && boundingVolume != null 89 && (attackVolumes != null || vulnerabilityVolumes != null)) { 90 record.object = object; 91 record.boundingVolume = boundingVolume; 92 record.attackVolumes = attackVolumes; 93 record.vulnerabilityVolumes = vulnerabilityVolumes; 94 record.reactionComponent = reactionComponent; 95 mObjects.add(record); 96 } 97 } 98 99 @Override update(float timeDelta, BaseObject parent)100 public void update(float timeDelta, BaseObject parent) { 101 // Sort the objects by their x position. 102 mObjects.sort(true); 103 104 final int count = mObjects.getCount(); 105 for (int x = 0; x < count; x++) { 106 final CollisionVolumeRecord record = mObjects.get(x); 107 final Vector2 position = record.object.getPosition(); 108 sFlip.flipX = (record.object.facingDirection.x < 0.0f); 109 sFlip.flipY = (record.object.facingDirection.y < 0.0f); 110 sFlip.parentWidth = record.object.width; 111 sFlip.parentHeight = record.object.height; 112 113 if (sSystemRegistry.debugSystem != null) { 114 drawDebugVolumes(record); 115 } 116 117 final float maxX = record.boundingVolume.getMaxXPosition(sFlip) + position.x; 118 for (int y = x + 1; y < count; y++) { 119 final CollisionVolumeRecord other = mObjects.get(y); 120 final Vector2 otherPosition = other.object.getPosition(); 121 sOtherFlip.flipX = (other.object.facingDirection.x < 0.0f); 122 sOtherFlip.flipY = (other.object.facingDirection.y < 0.0f); 123 sOtherFlip.parentWidth = other.object.width; 124 sOtherFlip.parentHeight = other.object.height; 125 126 if (otherPosition.x + other.boundingVolume.getMinXPosition(sOtherFlip) > maxX) { 127 // These objects can't possibly be colliding. And since the list is sorted, 128 // there are no potentially colliding objects after this object 129 // either, so we're done! 130 break; 131 } else { 132 final boolean testRequired = (record.attackVolumes != null && other.vulnerabilityVolumes != null) || 133 (record.vulnerabilityVolumes != null && other.attackVolumes != null); 134 if (testRequired && record.boundingVolume.intersects(position, sFlip, 135 other.boundingVolume, otherPosition, sOtherFlip)) { 136 // These two objects are potentially colliding. 137 // Now we must test all attack vs vulnerability boxes. 138 final int hit = testAttackAgainstVulnerability( 139 record.attackVolumes, 140 other.vulnerabilityVolumes, 141 position, 142 otherPosition, 143 sFlip, 144 sOtherFlip); 145 if (hit != HitType.INVALID) { 146 boolean hitAccepted = false; 147 if (other.reactionComponent != null) { 148 hitAccepted = other.reactionComponent.receivedHit( 149 other.object, record.object, hit); 150 } 151 if (record.reactionComponent != null) { 152 record.reactionComponent.hitVictim( 153 record.object, other.object, hit, hitAccepted); 154 } 155 156 } 157 158 final int hit2 = testAttackAgainstVulnerability( 159 other.attackVolumes, 160 record.vulnerabilityVolumes, 161 otherPosition, 162 position, 163 sOtherFlip, 164 sFlip); 165 if (hit2 != HitType.INVALID) { 166 boolean hitAccepted = false; 167 if (record.reactionComponent != null) { 168 hitAccepted = record.reactionComponent.receivedHit( 169 record.object, other.object, hit2); 170 } 171 if (other.reactionComponent != null) { 172 other.reactionComponent.hitVictim( 173 other.object, record.object, hit2, hitAccepted); 174 } 175 176 } 177 } 178 } 179 } 180 // This is a little tricky. Since we always sweep forward in the list it's safe 181 // to invalidate the current record after we've tested it. This way we don't have to 182 // iterate over the object list twice. 183 mRecordPool.release(record); 184 } 185 186 mObjects.clear(); 187 } 188 189 /** Compares the passed list of attack volumes against the passed list of vulnerability volumes 190 * and returns a hit type if an intersection is found. 191 * @param attackVolumes Offensive collision volumes. 192 * @param vulnerabilityVolumes Receiving collision volumes. 193 * @param attackPosition The world position of the attacking object. 194 * @param vulnerabilityPosition The world position of the receiving object. 195 * @return The hit type of the first attacking volume that intersects a vulnerability volume, 196 * or HitType.INVALID if no intersections are found. 197 */ testAttackAgainstVulnerability( FixedSizeArray<CollisionVolume> attackVolumes, FixedSizeArray<CollisionVolume> vulnerabilityVolumes, Vector2 attackPosition, Vector2 vulnerabilityPosition, CollisionVolume.FlipInfo attackFlip, CollisionVolume.FlipInfo vulnerabilityFlip)198 private int testAttackAgainstVulnerability( 199 FixedSizeArray<CollisionVolume> attackVolumes, 200 FixedSizeArray<CollisionVolume> vulnerabilityVolumes, 201 Vector2 attackPosition, 202 Vector2 vulnerabilityPosition, 203 CollisionVolume.FlipInfo attackFlip, 204 CollisionVolume.FlipInfo vulnerabilityFlip) { 205 int intersectionType = HitType.INVALID; 206 if (attackVolumes != null && vulnerabilityVolumes != null) { 207 final int attackCount = attackVolumes.getCount(); 208 for (int x = 0; x < attackCount && intersectionType == HitType.INVALID; x++) { 209 final CollisionVolume attackVolume = attackVolumes.get(x); 210 final int hitType = attackVolume.getHitType(); 211 if (hitType != HitType.INVALID) { 212 final int vulnerabilityCount = vulnerabilityVolumes.getCount(); 213 for (int y = 0; y < vulnerabilityCount; y++) { 214 final CollisionVolume vulnerabilityVolume = vulnerabilityVolumes.get(y); 215 final int vulnerableType = vulnerabilityVolume.getHitType(); 216 if (vulnerableType == HitType.INVALID || vulnerableType == hitType) { 217 if (attackVolume.intersects(attackPosition, attackFlip, 218 vulnerabilityVolume, vulnerabilityPosition, 219 vulnerabilityFlip)) { 220 intersectionType = hitType; 221 break; 222 } 223 } 224 } 225 } 226 } 227 } 228 229 return intersectionType; 230 } 231 drawDebugVolumes(CollisionVolumeRecord record)232 private final void drawDebugVolumes(CollisionVolumeRecord record) { 233 final Vector2 position = record.object.getPosition(); 234 if (mDrawDebugBoundingVolume) { 235 final CollisionVolume boundingVolume = record.boundingVolume; 236 sSystemRegistry.debugSystem.drawShape( 237 position.x + boundingVolume.getMinXPosition(sFlip), position.y + boundingVolume.getMinYPosition(sFlip), 238 boundingVolume.getMaxX() - boundingVolume.getMinX(), 239 boundingVolume.getMaxY() - boundingVolume.getMinY(), 240 DebugSystem.SHAPE_CIRCLE, 241 DebugSystem.COLOR_OUTLINE); 242 } 243 if (mDrawDebugCollisionVolumes) { 244 if (record.attackVolumes != null) { 245 final int attackVolumeCount = record.attackVolumes.getCount(); 246 for (int y = 0; y < attackVolumeCount; y++) { 247 CollisionVolume volume = record.attackVolumes.get(y); 248 sSystemRegistry.debugSystem.drawShape( 249 position.x + volume.getMinXPosition(sFlip), position.y + volume.getMinYPosition(sFlip), 250 volume.getMaxX() - volume.getMinX(), 251 volume.getMaxY() - volume.getMinY(), 252 volume.getClass() == AABoxCollisionVolume.class ? DebugSystem.SHAPE_BOX : DebugSystem.SHAPE_CIRCLE, 253 DebugSystem.COLOR_RED); 254 } 255 } 256 257 if (record.vulnerabilityVolumes != null) { 258 final int vulnVolumeCount = record.vulnerabilityVolumes.getCount(); 259 for (int y = 0; y < vulnVolumeCount; y++) { 260 CollisionVolume volume = record.vulnerabilityVolumes.get(y); 261 sSystemRegistry.debugSystem.drawShape( 262 position.x + volume.getMinXPosition(sFlip), position.y + volume.getMinYPosition(sFlip), 263 volume.getMaxX() - volume.getMinX(), 264 volume.getMaxY() - volume.getMinY(), 265 volume.getClass() == AABoxCollisionVolume.class ? DebugSystem.SHAPE_BOX : DebugSystem.SHAPE_CIRCLE, 266 DebugSystem.COLOR_BLUE); 267 } 268 } 269 } 270 } 271 setDebugPrefs(boolean drawBoundingVolumes, boolean drawCollisionVolumes)272 public void setDebugPrefs(boolean drawBoundingVolumes, boolean drawCollisionVolumes) { 273 mDrawDebugBoundingVolume = drawBoundingVolumes; 274 mDrawDebugCollisionVolumes = drawCollisionVolumes; 275 } 276 277 /** A record of a single game object and its associated collision info. */ 278 private class CollisionVolumeRecord extends AllocationGuard { 279 public GameObject object; 280 public HitReactionComponent reactionComponent; 281 public CollisionVolume boundingVolume; 282 public FixedSizeArray<CollisionVolume> attackVolumes; 283 public FixedSizeArray<CollisionVolume> vulnerabilityVolumes; 284 reset()285 public void reset() { 286 object = null; 287 attackVolumes = null; 288 vulnerabilityVolumes = null; 289 boundingVolume = null; 290 reactionComponent = null; 291 } 292 } 293 294 /** A pool of collision volume records. */ 295 private class CollisionVolumeRecordPool extends TObjectPool<CollisionVolumeRecord> { 296 CollisionVolumeRecordPool(int count)297 public CollisionVolumeRecordPool(int count) { 298 super(count); 299 } 300 301 @Override fill()302 protected void fill() { 303 for (int x = 0; x < getSize(); x++) { 304 getAvailable().add(new CollisionVolumeRecord()); 305 } 306 } 307 308 @Override release(Object entry)309 public void release(Object entry) { 310 ((CollisionVolumeRecord)entry).reset(); 311 super.release(entry); 312 } 313 314 } 315 316 /** 317 * Comparator for game objects that considers the world position of the object's bounding 318 * volume and sorts objects from left to right on the x axis. */ 319 public final static class CollisionVolumeComparator implements Comparator<CollisionVolumeRecord> { 320 private static CollisionVolume.FlipInfo sCompareFlip = new CollisionVolume.FlipInfo(); compare(CollisionVolumeRecord object1, CollisionVolumeRecord object2)321 public int compare(CollisionVolumeRecord object1, CollisionVolumeRecord object2) { 322 int result = 0; 323 if (object1 == null && object2 != null) { 324 result = 1; 325 } else if (object1 != null && object2 == null) { 326 result = -1; 327 } else if (object1 != null && object2 != null) { 328 sCompareFlip.flipX = (object1.object.facingDirection.x < 0.0f); 329 sCompareFlip.flipY = (object1.object.facingDirection.y < 0.0f); 330 sCompareFlip.parentWidth = object1.object.width; 331 sCompareFlip.parentHeight = object1.object.height; 332 333 final float minX1 = object1.object.getPosition().x 334 + object1.boundingVolume.getMinXPosition(sCompareFlip); 335 336 sCompareFlip.flipX = (object2.object.facingDirection.x < 0.0f); 337 sCompareFlip.flipY = (object2.object.facingDirection.y < 0.0f); 338 sCompareFlip.parentWidth = object2.object.width; 339 sCompareFlip.parentHeight = object2.object.height; 340 341 final float minX2 = object2.object.getPosition().x 342 + object2.boundingVolume.getMinXPosition(sCompareFlip); 343 344 final float delta = minX1 - minX2; 345 if (delta < 0.0f) { 346 result = -1; 347 } else if (delta > 0.0f) { 348 result = 1; 349 } 350 } 351 return result; 352 } 353 } 354 355 356 357 } 358