PS2 Linux Programming
2D Collision Detection and Response
Introduction
Collision detection is a large subject area ranging from simple 2d techniques such as bounding boxes, through to the complex mathematics describing the interaction of lines, objects and shapes in three dimensional geometry.
A collision response is the action that takes place once a collision has been detected. This may be as simple as incrementing a number to indicate a score or a more complex response such as the movement of an object in a new direction as a result of a collision.
The intention of this tutorial is to provide an introduction to collision detection and response in two dimensions. Some techniques will be described and demonstrated in the accompanying program.
2D Collision Detection.
2D collision detection involves the detection of collisions between objects on the screen. One of the simplest methods is to use bounding circles in 2D (or spheres in 3D).
Any object is considered to be contained within a circle the centre and radius of which are known as shown in the diagram above. A collision has occurred between the objects if:
Notice that it is not necessary to compute the square root (which is a slow operation) to work out the actual distance between the objects. If a collision occurs then suitable action can be taken within the game code.
An alternative method of determining collisions is to use a bounding box round the object as shown below.
If the position (x, y) and size (w, h) of the objects is known this information can be used to determine if the objects have collided as illustrated in the function below. Note that the logic in this function actually determined if a collision has not occurred – which turns out to be computationally simpler and faster to determine.
bool CollisionTest(SPRITE * r1, SPRITE * r2)
{
if(((r1->x + r1->w) < r2->x) ||
(r1->x > (r2->x + r2->w)) ||
((r1->y + r1->h) < r2->y) ||
(r1->y > (r2->y + r2->h))) return(FALSE); //no collision
else return(TRUE); //collision
}
Obviously, bounding circles or boxes only give an approximation to the actual collision of objects within a game. If more accurate collision detection is required then pixel based collision detection algorithms can be used. Also, the methods described above take no detailed account of the velocity that objects are moving; it is possible that collisions are missed due to the high speed of objects. In these circumstances more complex algorithms are required.
There are many more advanced collision detection techniques available but the bounding shapes described here provide a quick first approximation method to collision detection in 2 dimensions. It must be remembered that a computer game is an illusion, and if it is possible to use a simple collision detection method which provides the correct illusion, then this should be used instead of more complex methods which, although being more accurate, may be detrimental to the overall speed and performance of the game.
Collision response is what happens after a collision is detected. The exact details of a collision response will be determined by the game play of the game being written. An example of a collision response is described below.
In the example code provided there are a number of circular balls moving about the screen with velocity vectors that are chosen at random at the start of the program. The bounding circle method is used to determine when two balls collide and this is the function Collision() contained within the file collision.cpp (all the collision detection and response code is in this file).
Two collision response functions are provided. One is relatively simple CollisionResponseFake(), and as the name suggests, it “fakes” the collision response by simply swapping the velocity vectors of the colliding balls. This looks realistic under certain conditions but sometimes the collision response is seen to be obviously wrong.
The second collision function CollisionResponseTrue() provides a more realistic collision response by simulating the momentum transfer and dynamic equations that exist is real ball collisions. The method being employed is taken from chapter 13, p841 (Real 2D Object-to-Object Collision Response (Advanced)) of the book: “Tricks of the Windows Game Programming Gurus” by Andre LaMothe.
Some introductory collision detection and response algorithms and methods have been provided in this tutorial. The accompanying code demonstrates some collision detection and response methods.
Dr Henry S Fortuna
University of Abertay Dundee