Detecting and responding to dynamic collisions.

In the last post I discussed how Replica Island uses line segments organized as a 2D regular grid of tiles as the basis for its background collision system. This time I will explain how dynamic collisions (collisions between moving objects) are detected and resolved.

In Replica Island I draw a distinction between collisions that occur with the background geometry (falling on the ground, sliding on a slope, hitting the Android's head on the ceiling) and collisions that occur between game objects (the Android depressing a button, or hitting an enemy, or collecting a coin). While both of those cases are forms of "collision detection," they represent very different types of tests and I have two (entirely separate--mostly) systems for dealing with them.

Moving objects vs the background

Since I alluded to how background collision detection works in the last post, I'll start with that system. If Android is falling through space and passes into the ground, I need to detect that intersection and then fix it so that he doesn't actually fall through the floor. This is actually a pretty tricky problem because the frame rate of any Android game (and really, any modern game on any platform) can fluctuate as the game is played. The Android moves through space in game units / second, but the game is displayed in frames per second, and depending on the current speed of the game there's no good way to predict how far he'll move in a single frame. So I need a method that can cover a range of space between the last frame and this one so that even a dramatic movement won't allow the player to pass through walls.

The solution is to "sweep" the space in between the character's position at the last frame and his current position, and snap the character back if an intersection is detected. I use rays to do this: rays are cast from a character's previous position to his current position, and the first intersection along the ray (that is, the intersection that is closest to the ray's start point) is considered to be the spot at which the character hit a wall. I also filter my ray test by the normals of the surfaces I am considering; surfaces that do not oppose the direction of the ray can be ignored (that is, I only care about surfaces whose dot product against the direction of the ray is less that 0). Characters are not well described by a single, thin ray, however, so I do two tests: one filtered against horizontal surfaces and one filtered against vertical surfaces (angled surfaces fall into one bucket or the other depending on their slope). This is a nice method because it allows me to tune exactly how I test a volume against collision; often I want to allow a small amount of intersection: when the character is standing on a sloped surface, for example, I want to allow his bounding box to intersect with the slope slightly so that it looks like his feet are on the ground. With a couple of simple ray tests this method covers the space between the previous frame and the current frame pretty well without too much processor overhead. I briefly experimented with a final volume test pass to make sure that collisions were not being missed by the ray tests, but in the end such a test wasn't necessary (and actually, despite being more technically correct, the results were a lot less fun).

Sometimes I want game objects that act like background collision but are not part of the collision tile map. For example, a moving platform might act in every way like a background element except that it can move. In these cases, I allow entities to submit temporary line segments to the background collision system which will then be used along with all the rest of the background collision line segment data. This way characters in the world can be made to act exactly like solid objects without remaining static, and other characters can come along and react to them without any special code.

Moving objects vs each other

However, the more common case is when two game objects--a bullet and the player, an enemy and some spikes, etc--that are moving and non-solid come into contact. In this case we need to detect the intersection and then let code specific to each entity decide what to do about it. Still, we can generalize the system a little bit more: usually in such collisions we can name one of the entities as the "offender" and the other entity as the "victim." When a bullet hits the player, the bullet is the offender and the player is the victim. When a robot runs into some spikes, the spikes are the offender and the robot the victim. In fact, if we consider an animating character, we might want to mark some parts of a given frame of animation as "offensive" and other parts "vulnerable." In a game where a character can punch, we probably want the character's fist to deal damage to other characters but at the same time we'd expect other parts of the character, say his back and head, to be vulnerable to hits. So in order to detect collisions between game entities, I decided to give my entities multiple collision volumes, some associated with offensive areas and others associated with areas that are vulnerable to hits.

Each animation frame in Replica Island can carry a list of "attack" volumes and "vulnerability" volumes. When detecting collisions, I stipulate that collisions can only occur between a single attack volume and a single vulnerability volume. Furthermore, volumes can be set to deal and receive specific types of hits, which allows me to filter the number of actual volume intersection tests I need to perform (for example, the coin is only vulnerable to a "collection" hit, so only collection-hit-dealing attack volumes will be tested against the coin.

Each time an animation frame changes a new set of attack and vulnerability volumes may become active. These volumes are unioned together into a sphere that is guaranteed to encompass them called the bounding sphere. The volumes, along with the bounding sphere, are then submitted to the runtime collision detection system. Each frame, the collision detection system sorts all of the bounding spheres that have been submitted and tests them for intersections. The sort is by the left-most point of the sphere, so objects end up sorted along the x-axis of the level. This is a type of sweep and prune algorithm, and it makes it easy to quickly find overlapping bounding spheres because potentially colliding sphere pairs are guaranteed to be grouped together in the sorted list. When a pair of bounding spheres that intersect is found, each of the related entities' attack and vulnerability volumes are tested for intersection. If an intersection between an attack volume and a vulnerability volume is found, we know that these two entities have hit each other and some other code needs to run in order to respond.

For a long time the Replica Island engine only supported sphere collision volumes for these kinds of dynamic tests. About half-way through development I added an axis-aligned box collision type as well, but otherwise no complicated collision volume tests have been necessary. I'm very happy with the way that this system turned out: it's reliable, fast, and easy to extend.