Section 21.4. Basic Collisions

21.4. Basic Collisions

Detecting when objects collide with one another is an important aspect of game programming. A collision could take place between a character and a barrier in the game, between two characters, between a character and a computer enemy, or between characters and projectiles. The way to detect these collision types can be simple and can result in an approximation, or it can be a much more complicated, yet precise, detection.

There is a danger when performing collision detection on the client using a collision object and storing the state of the character on it. By prototyping a new collision object, a malicious hacker could create a character that could never get hit. For simplicity, though, this detection will be done on the client.

The simplest of these detection techniques is rectangular collision detection. The level of precision in rectangular collision detection depends on the accuracy of the bounding boxes being tested. Next, there is circular collision detection, which can approximate large projectiles better than a rectangle can. Finally, there is linear collision detection, which accurately detects a collision based on two lines intersecting. Of course, there are other techniques, but they become more complex and require a lot more mathematics and computer computation (requiring more computer hardware speed), and frankly, they are beyond the scope of this book. You can find more information on collision detection in AI for Game Developers by David M. Bourg and Glenn Seeman (O'Reilly).

For good collision detection, all of the objects and barriers in the game will have to have bounding boxes, circles, or lines to detect collision properly. To this end, our character must have collision bounding constraints to test against. This requires a simple addition to the character class:

var character = Class.create( );
character.prototype = {
    collision: {
        _boundings: [],
        .
        .
        .

Objects and barriers would have something similar so that they too could be tested for collisions.

Now that we know the basics of collision detection, it's time to decide which method of collision detection we want to use in our game.

21.4.1. Rectangular Collision Detection

Rectangular collision detection determines whether there is an intersection between two boxes. This is actually a simple process. Each object to be tested will have a bounding box with an (x1, y1) coordinate that represents the upper-left corner of the box and an (x2, y2) coordinate that represents the lower-right corner of the box. You can also express this second coordinate as (x1 + width, y1 + height). You perform two tests on the boxes to see whether they have collided. First you check whether one box's right x coordinate is greater than the other box's left x coordinate and then whether one box's left x coordinate is less than the second box's right x coordinate. This determines whether they are intersected vertically, and you can express it as follows:

if ((ego.GetBoundX(1) < char[0].GetBoundX(2)) &&
    (ego.GetBoundX(2) > char[0].GetBoundX(1)))

Rectangular collision detection is also known as square collision detection. Rectangular collision detection is the more common name, as a square is only a specialized rectangle in the first place.

Once you have found that the two bounding boxes have intersected vertically, you would run these tests on the two boxes' y coordinates to determine whether the boxes have intersected horizontally as well. You would express this as follows:

if ((ego.GetBoundY(1) < char[0].GetBoundY(2)) &&
    (ego.GetBoundY(2) > char[0].GetBoundY(1)))

When both statements are found to be true, the two bounding boxes have collided. Unfortunately, as you will notice in Figure 21-12, though the boxes have collided with each other, they are not accurately describing a true collision between the two characters (Tux is not really colliding with the BSD daemon).

Figure 21-12. An example of two bounding boxes colliding, yet not accurately describing an actual collision

Tightening the bounding boxes will provide more accurate collision detection, though this can be only so accurate, as a rectangle cannot describe most sprites to a high degree of accuracy. Example 21-6 shows what the addition to the Logic class would entail for this test.

Example 21-6. Additions to the Logic class for testing rectangular collisions

Code View: /** * This object, Logic, is the container for all mathematical logic functionality * for the game. */ var Logic = { //. //. //. /** * This method, RectangularCollisionDetect, tests for a collision between the * two rectangles that are passed to it. * * @member Logic * @param {Array} p_box1 The points for the first bounding box. * @param {Array} p_box2 The points for the second bounding box. * @return Whether the two boxes have collided or not. * @type Boolean */ RectangularCollisionDetect: function(p_box1, p_box2) { /* Is there a vertical collision between the boxes? */ if ((p_box1[0][0] < p_box2[1][0]) && (p_box1[1][0] > p_box2[0][0])) /* Is there a horizontal collision between the boxes? */ if ((p_box1[0][1] < p_box2[1][1]) && (p_box1[1][1] > p_box2[0][1])) return (true); return (false); } };

Once this is in place, the tests can happen within the character class, as shown in Example 21-7.

Example 21-7. The character class with collision detection and other necessary functionality added

Code View: /** * This class, character, will store all of the functionality needed by a * character in the game, including animation, movement, and statistics. */ var character = Class.create( ); character.prototype = { //. //. //. /** * This member, collision, holds all of the methods for testing collisions * between this character and other objects in the game. * * @member character */ collision: { /** * This member, _boundings, holds the bounding box coordinates for * the character. * @private */ _boundings: [], /** * This method, SetBounding, sets the new bounding box coordinates of * the character with the passed points. * * @member collision * @param {Array} p_points An array containing the new bounding box * points of the character. */ SetBounding: function(p_points) { try { this._bounding[0] = [p_points[0][0], p_points[0][1]]; this._bounding[1] = [p_points[1][0], p_points[1][1]]; } catch (ex) { this._bounding = null; } }, /** * This method, GetBoundX, gets one of the current x-coordinates of * the character. * * @member collision * @param {Integer} p_corner The coordinate to return (1 or 2 for x1 and x2). * @return The x-coordinate. * @type Integer */ GetBoundX: function(p_corner) { /* Does the character have a bounding box? */ if (this._bounding) return (this._bounding[p_corner - 1][0]); return (null); }, /** * This method, GetBoundY, gets one of the current y-coordinates of * the character. * * @member collision * @param {Integer} p_corner The coordinate to return (1 or 2 for y1 and y2). * @return The y-coordinate. * @type Integer */ GetBoundY: function(p_corner) { /* Does the character have a bounding box? */ if (this._bounding) return (this._bounding[p_corner - 1][1]); return (null); }, /** * This method, GetBoundingBox, gets the current bounding box coordinates * of the character. * * @member collision * @return The current bounding box coordinates of the character. * @type Array */ GetBoundingBox( ) { /* Does the character have a bounding box? */ if (this._bounding) return ([[this._bounding[0]], this._bounding[1]]); return (null); } }, /** * This method, GetBoundX, is the public way of getting one of the current * x-coordinates of the character. * * @member character * @param {Integer} p_corner The coordinate to return (1 or 2 for x1 and x2). * @return The x-coordinate. * @type Integer */ GetBoundX: function(p_corner) { return (this.collision.GetBoundX(p_corner)); }, /** * This method, GetBoundY, is the public way of getting one of the current * y-coordinates of the character. * * @member character * @param {Integer} p_corner The coordinate to return (1 or 2 for y1 and y2). * @return The y-coordinate. * @type Integer */ GetBoundY: function(p_corner) { return (this.collision.GetBoundY(p_corner)); }, /** * This method, GetBoundingBox, is the public way of getting the current * bounding box coordinates of the character. * * @member character * @return The current bounding box coordinates of the character. * @type Array */ GetBoundingBox: function( ) { return (this.collision.GetBoundingBox( )); }, /** * This method, TestCollision, tests for a collision between the character's * bounding box and the box that was passed using rectangular collision * detection. * * @member character * @param {Array} p_box The bounding box to test against. * @return Whether or not the passed bounding box collided with the * character's bounding box. * @type Boolean */ TestCollision: function(p_box) { return (Logic.RectangularCollisionDetect(this.GetBoundingBox( ), p_box)); } }

If you need to test a character with a small projectile, it would be better to represent the projectile as a single point instead of a bounding box. It takes two comparisons to detect a collision, one vertical and one horizontal: if ((obj.GetBoundX( ) > ego.GetBoundX(1)) && (obj.GetBoundX( ) < ego.GetBoundX(2))) if ((obj.GetBoundY( ) > ego.GetBoundY(1)) && (objGetBoundY( ) < ego.GetBoundY(2))) return (true); return (false); This varies only slightly from the original rectangular collision detection.

This is simple collision detection with easy and fast calculations. Sometimes, however, to get more accurate results, a different bounding technique may be required.

21.4.2. Circular Collision Detection

Circular collision detection requires more calculations than rectangular collision detection does; therefore, you should use it only when you have a larger object that would benefit from collision detection with a circle as its bounding area. The object must have a radius and a center coordinate so that it can be tested correctly. For example:

var object = Class.create( );
object.prototype = {
    collision: {
        _boundingRadius: 0,
        _boundingCenter: [0, 0],
        //.
        //.
        //.
    }
};

We will consider anything within the object's radius as something with which we have collided. To calculate this, we will use the Pythagorean theorem (http://en.wikipedia.org/wiki/Pythagorean_theorem) to determine a point's distance to the center of the object.

The Pythagorean theorem says that for a right triangle, the square of the hypotenuse is equal to the sum of the squares of the other two sides. That is, x2 + y2 = r2. To solve for r (the radius) we take (x2 + y2). Testing a point (x, y) to see whether it is within a certain number of pixels from our center, we calculate the following: ((x - centerX)2 + (y - centerY)2).

It does not matter whether you calculate (x - centerX) or (centerX - x); both will give you the same result once the difference is found and squared. For example (6 - 3)2 and (3 – 6)2 both yield 9.

Now that we have this distance, we check it against the object's radius and see whether this value is less than the calculated radius. When the calculated radius is less than the object's radius, the objects have collided.

The bad thing about this method of testing is that it can be a bit slow because of the square root function, which takes some time to calculate. This can be bad if several detections must be checked at every interval. To overcome this speed issue, the radius of the object squared can also be stored in the object for the sole purpose of testing against collisions. Then, the test is checking the object's radius squared against the calculation, ((x - centerX)² + (y - centerY)²). This speeds up the calculation, but it is still slower than rectangular collision detection.

Example 21-8 shows this collision testing as part of the Logic object. As an alternative, you could use a lookup table, or LUT (http://en.wikipedia.org/wiki/Lookup_table), of square root values to calculate more quickly than you can with the sqrt( ) function.

Example 21-8. The circular collision test added to the Logic object

Code View: /** * This object, Logic, is the container for all mathematical logic functionality * for the game. */ var Logic = { //. //. //. /** * This method, CircularCollisionDetect, tests for a collision between a * passed point and the passed circle (through its important values). * * @member Logic * @param {Array} p_point The point to test. * @param {Array} p_center The center point of the circle to test. * @param {Integer} p_r2 The radius squared from the circle to test. * @return Whether or not the point and the circle have collided. * @type Boolean */ CircularCollisionDetect: function(p_point, p_center, p_r2) { var r2 = Math.pow((p_point[0] - p_center[0]), 2) + Math.pow((p_point[1] - p_center[1]), 2); /* Is there a collision between the circle and point? */ if (r2 < p_r2) return (true); return (false); } };

Keep in mind that this only tests a point and a circle for collision. What if we want to test the circle with another circle? Such a test would be only slightly more complicated than our circle-point test. To test two circles for collision, you calculate the distance between their center points, and if this is less than the sum of their radii, the two circles have collided. For example:

var r2 = Math.pow((obj1.GetCenterX( ) - obj2.GetCenterX( )), 2) +
    Math.pow((obj1.GetCenterY( ) - obj2.GetCenterY( )), 2);

/* Is there a collision between the two circles? */
if (r2 < Math.pow((obj1.GetRadius( ) + obj2.GetRadius( )), 2))
    return (true);
return (false);

Our final test is a test for a circle and a rectangle. This will require a few more calculations: the circle must be tested for a collision against all four of the rectangle's corners, all four of the rectangle's sides, and the rectangle's inside area. Figure 21-13 gives an example of each case.

Figure 21-13. Detecting collisions between circles and rectangles

The following test will need to be checked against all four corners of the rectangle for collision against a corner of the rectangle:

var r2 = Math.pow((obj.GetCenterX( ) - ego.GetBoundX(1)), 2) +
    Math.pow((obj.GetCenterX( ) - ego.GetBoundY(1)), 2);

/* Is there a collision between the corner and the circle? */
if (r2 < obj.GetRadiusSquared( ))
    return (true);
return (false);

Once the corners have been checked—(x1, y1), (x1, y2), (x2, y1), and (x2, y2)—we must test all four sides for a collision with the circle:

Code View:

/* Does the circle's center collide vertically with the bounding box? */
if ((obj.GetCenterX( ) > ego.GetBoundX(1)) && obj.GetCenterX( ) < ego.GetBoundX(2))
    /*
     * Does the circle's center collide horizontally with the bottom side of the
     * bounding box?
     */
    if (Math.abs((ego.GetBoundY(2) - obj.GetCenterY( ))) < obj.GetRadius( ))
        return (true);
    /*
     * Does the circle's center collide horizontally with the top side of the
     * bounding box?
     */
    else if (Math.abs((ego.GetBoundY(1) - obj.GetCenterY( ))) < obj.GetRadius( ))
        return (true);
return (false);


					  

This tests the top and bottom sides of the bounding box, and the right and left sides would have similar calculations. The easiest part of this test is to check whether the circle collided somewhere inside the rectangle. The center of the circle must be tested against the rectangle. This is the point against a bounding box check I discussed in the preceding section.

That is all there is to circular collision detection. It is not too complicated, and certainly not too processor-intensive. However, if you will be conducting hundreds or thousands of these checks, you will have a problem. If this is the case, bounding all objects with bounding rectangles will result in much faster (albeit less accurate) testing for collisions.

21.4.3. Linear Collision Detection

When you need a higher degree of accuracy for collision detection, a good solution is to test for the intersection of two lines (or line segments for our purposes). More computations are involved with this sort of test, unfortunately, so if you can get by without this accuracy, do.

OK, kids, break out your math books, because this is some fun algebra! For our algorithm, we will assume that we have two line segments, L1 and L2, where L1 goes from P1 to P2 and L2 goes from P3 to P4. The equations of these lines are:

Pa = P1 + ua(P2 - P1)
Pb = P3 + ub(P4 - P3)

Solving for the point where P_a = P_b will give us the following two equations in two unknowns (u_a and u_b):

x1 + ua(x2 - x1) = x3 + ub(x4 - x3)
y1 + ua(y2 - y1) = y3 + ub(y4 - y3)

The next step is to solve these two equations, which gives us expressions for u_a and u_b:

ua = ((x4 - x3)(y1 - y3) - (y4 - y3)(x1 - x3)) /
    ((y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1))
ub = ((x2 - x1)(y1 - y3) - (y2 - y1)(x1 - x3)) /
    ((y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1))

Substituting either of these expressions into the corresponding equation for the line gives the intersection point. Example 21-9 shows this algorithm as an addition to the Logic object.

Example 21-9. The Logic object with the linear collision detection added to it

Code View: /** * This object, Logic, is the container for all mathematical logic functionality * for the game. */ var Logic = { //. //. //. /** * This method, LinearCollisionDetect, tests for a collision (intersection) * between the two passed line segments. * * @member Logic * @param {Array} p_line1 The first line segment for the test. * @param {Array} p_line2 The second line segment for the test. * @return Whether or not the two line segments intersect, or collide. * @type Boolean */ LinearCollisionDetect(p_line1, p_line2) { var denom = ((p_line2[1][1] - p_line2[0][1]) * (p_line1[1][0] - p_line1[0][0])) - ((p_line2[1][0] - p_line2[0][0]) * (p_line1[1][1] - p_line1[0][1])); var numA = ((p_line2[1][0] - p_line2[0][0]) * (p_line1[0][1] - p_line2[0][1])) - ((p_line2[1][1] - p_line2[0][1]) * (p_line1[0][0] - p_line2[0][0])); var numB = ((p_line1[1][0] - p_line1[0][0]) * (p_line1[0][1] - p_line2[0][1])) - ((p_line1[1][1] - p_line1[0][1]) * (p_line1[0][0] - p_line2[0][0])); /* Are the lines parallel? */ if (!denom) { /* Are the lines on top of each other? */ if (!numA && !numB) return (true); return (false); } var uA = numA / denom; var uB = numB / denom; /* Is there an intersection? */ if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) return (true); return (false); } };

There are a few things to note about this algorithm. When the denominator for the expressions u_a and u_b is 0, the two lines are parallel. When the denominator and numerator for the expressions u_a and u_b are 0, the two lines are coincident (they lie on top of each other). When both u_a and u_b lie between 0 and 1, the intersection point is within both line segments.

In case you're curious, you calculate the point of intersection between the two line segments as follows: x = x1 + ua(x2-x1) y = y1 + ua(y2 -y1)

That is linear collision detection at its finest. It involves quite a few calculations, so it would be a bad idea to use this technique if you had to execute several collision tests. However, it does result in more accurate collision detection, as characters and objects can have bounding polygons, and each line segment of the polygon can be tested (but then you are talking a lot of calculations!).