Collision Detection

After a group of entities has been created for the game, it’s time to define the fundamental ways in which they can interact with the game world. The algorithmic process of determining where two game objects have intersected with each other or with the environment is called collision detection. The concept of collision detection is a fundamental premise in almost every game.

Fundamentally, two types of collisions exist.

Collisions with environments: Collisions with environments represent objects that are overlapping segments of the game world that offer some sort of response. Consider the outlines of the court in the basic game of Pong. When the ball reaches the top of the screen, the ball finds the upper-most border of the game world and determines that a collision has occurred. Look at Figure 2.4.

image from book
Figure 2.4: Collision is detected between the ball and the wall.

The incoming ball determines that collision has happened when the outline of the ball equals or overlaps the boundary. Most of the time, programming basic outlines such as this can be done using points. Some sample code for detecting collisions against environments follows:

if(Ball.getX()<=0) //Test the left wall    return true; if(Ball.getY()+Ball.getWidth()>= SCREEN_WIDTH) //Test right wall    return true; if(Ball.GetY()<=0) //Test Top;    return true; if(Ball.getY()+Ball.getHeight()>=SCREEN_HEIGHT)//test bottom wall    return true;

If any one of these statements is evaluated to be true, the function returns properly.

Collisions with objects: Let’s look at object-to-object collisions.

Figure 2.5 sets up the most common type of collision detection in the form of object-to-object collision. A basic collision detection algorithm used in games is called the bounding box. The basic idea is that a box surrounds an object on all four sides. During a game, collision is checked on all four sides of the box. The collision check returns true when any two collidable objects overlap.

image from book
Figure 2.5: Collision is detected between the ball and a paddle.

Figure 2.6 shows the bounding box algorithm on a typical game-styled sprite.

image from book
Figure 2.6: Collision is detected between a ship and a meteor.

The small overlap between the outlined boxes represents the point where these boxes overlap. It is important to carefully bound objects based on how accurate the collision needs to be.

Testing for bounding box collision is particularly simple when using the Rectangle2D class. The Rectangle2D class is abstract, so it must be created with one of the subclasses. In this case, the choices are either Rectangle2D.Double or Rectangle2D.Float. The float version will be more than enough for the basic algorithm used here.

When the rectangle has been initialized with a given Actor class’s height and width, the process of detecting collisions between Rectangle2D.Float objects works as follows:

rectangle1.intersects(rectangle2.getBounds2D());

 On the CD  This call returns a Boolean as to whether the intersection was found given the current coordinates in both of these rectangles. This is a good addition to the Actor class and will be presented for the remainder of the chapter. Check the sample code on the CD-ROM for further implementation details.

Detecting collisions is only part of the process. When a collision has been found, the game must then specify how it plans to react. In some cases, a collision causes the player’s lives count to drop by one. Other games might determine that the game is over when collision happens. Whatever the response chosen, the reaction walks hand-in-hand with the detection.

Let’s take another look at the collision detected by the ball against the wall in Figure 2.4. Those who remember the original Pong game know that the ball reflects off in what appears to be a fairly accurate collision by reversing the vector on which the collision is first detected. It is completely possible to program axis-aligned and non-axis-aligned vector reflections to maintain a reasonably accurate reflection in all cases. For this example, let’s distill out the vector math and get to the point.

When the ball intersects with the wall, the vector is multiplied by –1. Figure 2.7 demonstrates the resulting vector of the collision based on this method.

image from book
Figure 2.7: Vector reflection off the wall after collision.

With this new information, we can modify the collision-detection code to include the reaction as follows:

if(Ball.getX()<=0) //Test the left wall    Ball.setVectorX(-1*Ball.getVectorX); ...

Using a method like this incorporates the result immediately into gameplay without requiring an additional infrastructure.

The same process is also possible for object-to-object collisions, but it is much more common to take an iterative approach to working through the object collisions. Remember the ActorManager from earlier in this chapter? There already exists an Updater interface that is capable of handling the collision detection for us. All that is needed is a list of collidable objects. Thankfully, courtesy of the ActorManager, all of the collidable objects in the game are in one place. Our collision pass ends up looking something like the following code:

for (int i = 0; i<actorList.size(); i++)   {     u = (Updater)actorList.get(i);     if(u.collidesWith((Actor)actorList.get(i))        handleCollision();        }

This check goes through each of the Actor classes in the list, testing collision against each other. The actual implementation of the handleCollision function is left to the actual game implementation. It’s important that the collidesWith method tests for equality to avoid returning true collisions against the Actor classes in the list when they test collisions against themselves. The easiest way to do this follows:

if(actor1 == actor2) return false;  else return actor1.getRect().intersects(actor2.getRect());

The art and science of collision detection is wide and varied, based on the needs of a given game. 3D collision detection requires the ability to perform quickly determined test conditions. These calculations require mathematics that are beyond the scope of this chapter. Check out Chapter 12, “3D Graphics Foundations,” for a more in-depth discussion regarding 3D collision.



Practical Java Game Programming
Practical Java Game Programming (Charles River Media Game Development)
ISBN: 1584503262
EAN: 2147483647
Year: 2003
Pages: 171

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net