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 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.
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
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.
The Example Code
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.
Conclusions
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