Scope of Article

A supporting feature for any serious game, collision detection provides tangibility and depth to your game world’s objects. This article explores in brief the common types of collision detection you can employ in your games to add a sense of realism and interactivity.

The 3 Approaches

1. Grid-based Detection

This is by far the simplest form of collision detection. Essentially a grid is setup whereby the player is only allowed to stand on certain tiles. This is similar to chess where each piece occupies only a single square.

To implement this form of collision detection you need only use an array to represent each tile. This array can be as simple as a collection of booleans (false = empty, true = solid) or you can repurpose a tiled graphics layer to also store this information. Such layers store integers as indices into a tile array and it is typical to use 0 as the no tile value which is also useful for saying there is nothing with which to collide.

This approach is useful for board games like chess and for simulation games.

2. Bounding Boxes

Bounding boxes are imaginary, invisible boxes that surround solid objects. In this case collision detection involves ensuring that no two bounding boxes intersect. In the case of 3D games boxes are replaced by 3D cubes.

While easy to process this technique is not accurate unless the objects in question are rectangular and the same size as their bounding boxes. A workaround to this problem is the use of smaller bounding boxes. Since bounding boxes are invisible their size has no impact on the display of objects. This is at best a workaround and not a full solution however. Even smaller bounding boxes will not provide perfect results and in the worst cases may exhibit situations where two objects which appear to be colliding visually are not detected as a true collision.

This approach is useful for games with a large quantity of objects which can collide with the player or each other.

One caveat regarding bounding box testing

When using this technique in 3D or 2.5D games avoid floating point comparisons as bounds values can become skewed and are generally slower to compare than integer values.

3. Pixel-level collision detection

Introduced in MIDP 2.0, the Sprite class’ doPixelCollision/collidesWith methods offers pixel-level collision detection which involves detecting overlap between two objects’ visible pixels. This method is only applicable to 2D games and is more costly as the pixels from masks of both images must be tested for overlap. The larger the images, the more costly this approach becomes. There are cases, however, where this approach is the only viable one. Good examples would include testing whether a spaceship with a non-rectangle shape were really hit by an enemy
missile or one ball hit another on a billiard board.

The Need for Collision Detection

Without effective collision detection there would be nothing preventing gravity from dragging you through the ground or from walking through walls. Games like golf, tennis, and pinball simply wouldn’t work with collision detection.

When to Apply Collision Detection: Preventative VS Corrective Collision Detection

Collision detection is either applied before or after an object moves. If applied before, the object’s soon to be occupied position is used in the test and should a collision be detected the move is denied. If the collision detection is applied after the object move and a detection occurs the object
is moved back to its prior position. Both methods incur the same performance costs and which one you employ will largely be based on the ease of integration with the rest of your game logic.

Performance Costs

The time it takes to test for object collision in a scene is proportionate to the number of objects in that scene. If only two objects exist only one test need occur. If three objects exist three tests must occur. In grid based collision detection a simple lookup to see if the slot is occupied or not will suffice. With free-range 3D games each object’s moves are in need of testing.

Results of a Position Collision

When a sprite collides with an object it typically stops moving and prevent further incursions in the interest of maintaining the illusion of solidity. This, however, is not the only possible result of collision.

Fighting games often cause the injured player to be pushed back upon being punched or kicked to impress upon the player the amount of force that was just used. Billiard balls that collide transfer a portion of the kinetic energy to each other while retaining some which is used to move in a refracted direction. In these cases stopping motion is not desirable. The take away here is that each game can have its own appropriate response to collision.

In Closing

Collision detection, while a must for most games if not all games comes at a cost and decisions during the design phase need to take into account this performance impact. There are various techniques for providing solidity in game environments and they can be used singularly or in tandem.