Chapter 11. Collision Detection
Topics in This Chapter
• 11.1 The Collision Detection Process
• 11.2 Collision Detection Techniques
• 11.3 Snail Bait’s Collision Detection
• 11.4 Select Candidates for Collision Detection
• 11.5 Detect Collisions Between the Runner and Another Sprite
• 11.7 Optimize Collision Detection
• 11.8 Monitor Collision Detection Performance
• 11.9 Implement Collision Detection Edge Cases
Nearly all computer games implement collision detection. Even games that are mostly static, such as puzzles, must detect collisions. Collision detection is a deep and varied topic, with entire books devoted to the subject. And the math required to implement certain types of collision detection can get pretty intense.
In spite of collision-detection complexities, for many games it’s relatively simple to implement. The level of difficulty depends to a great extent on how fast sprites move and how big they are; it’s fairly easy to detect collisions between large and slow-moving sprites, but it’s more challenging to detect collisions between small sprites moving at high speeds.
Besides detecting collisions, you must do something about them when they occur. Figure 11.1, for example, shows Snail Bait’s runner exploding after colliding with a bee in the upper-left corner of the game.
Figure 11.1. Detecting and reacting to collisions
In this chapter, you will learn how to do the following:
• Choose a particular type of collision detection for your game (Section 11.2 on p. 273)
• Implement collision detection as sprite behaviors (Section 11.3.2 on p. 279)
• Select sprites that are candidates for collision detection (Section 11.4 on p. 281)
• Use the HTML5 Canvas context for hit detection (Section 11.5 on p. 282)
• Process collisions (Section 11.6 on p. 284)
• Optimize collision detection (Section 11.7 on p. 286)
• Monitor collision-detection performance (Section 11.8 on p. 290)
• Implement collision-detection edge cases (Section 11.9 on p. 292)
The online examples for this chapter are listed in Table 11.1.
Table 11.1. Collision-detection examples online
11.1. The Collision Detection Process
Collision detection is a three-step process, one of which is the actual detection of collisions:
1. Disqualify sprites that are not candidates for collision detection.
2. Detect collisions between candidate sprites.
3. Process collisions.
Collision detection can be computationally expensive, so it’s essential to avoid it for sprites that cannot possibly collide. For example, Snail Bait’s runner runs through other sprites when they are exploding. Because it takes less time to check whether a sprite is exploding than it does to perform collision detection, Snail Bait excludes exploding sprites from collision detection.
Let’s start with an overview of collision detection techniques.
11.2. Collision Detection Techniques
You can detect collisions between sprites in several ways. Three popular techniques, in order of increasing sophistication and complexity, are
• Bounding areas (bounding volumes for 3D games)
• Ray casting
• The Separating Axis Theorem
Collision detection with bounding areas detects intersections between circles or polygons. In the example in Figure 11.2, the smaller circle is the bounding area that represents the ball, and the larger circle is a bounding area representing the top of the bucket. When those two circular bounding areas intersect, the ball is in the bucket.
Figure 11.2. Bounding areas: Collisions between circles
Detecting collisions between two circles is the simplest of all collision-detection techniques: if the distance between the circles’ centers is less than the circles’ combined radii, the circles intersect and the associated sprites have collided.
Bounding-area collision detection is simple, but it can fail when bounding areas are too small or are moving too fast. In either case, sprites can pass by each other in a single animation frame, thereby avoiding detection.
A more reliable technique for small, fast-moving sprites is ray casting, illustrated in Figure 11.3. Ray casting detects the intersection of two sprites’ velocity vectors.
In each of the five frames in Figure 11.3, the ball’s velocity vector is the diagonal line drawn in blue, and the velocity vector for the bucket is the red horizontal line. The ball lands in the bucket when the intersection of those vectors lies within the opening at the top of the bucket and the ball is below the opening, as illustrated in the rightmost screenshot in Figure 11.3.
Ray casting works well for simple shapes under circumstances—such as the ball landing in the bucket in Figure 11.3—where it’s easy to determine if two shapes have collided, given the intersection of their velocity vectors.
For more complicated scenarios, such as collisions between polygons of arbitrary size and shape, the Separating Axis Theorem is one of the most reliable—and most complicated—collision-detection techniques. The Separating Axis Theorem is the mathematical equivalent of shining a light on two polygons from different angles, as shown in Figure 11.4. If the shadow on one of the walls behind the polygons reveals a gap, the polygons are not colliding.
Figure 11.4. The Separating Axis Theorem
This book does not cover ray casting or the Separating Axis Theorem any further. You can read in-depth discussions of each approach in Core HTML5 Canvas (Prentice Hall, 2012).
11.3. Snail Bait’s Collision Detection
Snail Bait’s collision detection involves relatively large sprites moving at slow speeds, so the game detects collisions with bounding boxes. Those bounding boxes are shown in Figure 11.5.
Figure 11.5. Snail Bait’s collision detection bounding boxes
11.3.1. Sprite Collision Rectangles
To calculate collision-detection bounding boxes for sprites, we add a calculateCollisionRectangle() to the Sprite object, as shown in Example 11.1.
The calculateCollisionRectangle() method listed in Example 11.1 returns an object containing the positions of each corner of the sprite’s collision rectangle and the rectangle’s center. The method uses the sprite’s left, top, and hOffset properties, along with the sprite’s collision margin, to calculate those coordinates.
The left and top properties represent the coordinates of the upper-left corner of the sprite. The hOffset property represents the sprite’s horizontal offset, which Snail Bait uses to scroll sprites horizontally (see Chapter 3 for more information about how Snail Bait scrolls sprites). A collision margin, discussed in Section 11.7, “Optimize Collision Detection,” on p. 286, also factors into the sprite’s collision rectangle calculation.
Example 11.1. Calculating sprite collision-detection rectangles
Sprite.prototype = {
...
calculateCollisionRectangle: function () {
// Return an object with properties left, right, top, and bottom
return {
left: this.left - this.hOffset + this.collisionMargin.left,
right: this.left - this.hOffset +
this.width - this.collisionMargin.right,
top: this.top + this.collisionMargin.top,
bottom: this.top + this.collisionMargin.top +
this.height - this.collisionMargin.bottom,
centerX: this.left + this.width/2,
centerY: this.top + this.height/2
}
},
...
};
Initially, a sprite’s collision margin has no effect on its collision rectangle because the margin’s properties are all zero, as you can see in Example 11.2; however, as Example 11.1 attests, the margin will have an effect if you modify its properties. In Example 11.10, we modify the collision margin to modify sprite collision rectangles when we refine Snail Bait’s collision detection.
Example 11.2. Adding collision margins to sprites
var Sprite = function (type, artist, behaviors) {
...
this.collisionMargin = {
left: 0,
right: 0,
top: 0,
bottom: 0
};
...
};
Now that we’ve seen how sprites calculate their collision rectangles and margins, let’s see how Snail Bait implements a collide behavior for the runner.
11.3.2. The Runner’s Collide Behavior
As you saw in previous chapters, Snail Bait implements sprite activities, such as running, jumping, and exploding, as sprite behaviors, and the same is true for collision detection. At this point in Snail Bait’s development, the runner has three behaviors: she can run, jump, and collide with other sprites. Example 11.3 shows the instantiation of the runner sprite with those three behaviors.
Example 11.3. Adding the collide behavior to the runner’s array of behaviors
var SnailBait = function () {
...
this.runner = new Sprite('runner', // type
this.runnerArtist, // artist
[ this.runBehavior, // behaviors
this.jumpBehavior,
this.collideBehavior
]);
...
};
Example 11.4 shows an excerpt from the runner’s collide behavior.
The collideBehavior object is a sprite behavior by virtue of its execute() method, meaning that Snail Bait invokes the behavior’s execute() method for every animation frame. And because the collideBehavior object is associated with the runner, the sprite that Snail Bait passes to the execute() method is always the runner. See Chapter 7 for more information about sprite behaviors.
Example 11.4. The runner’s collide behavior (excerpt)
var SnailBait = function () {
...
this.collideBehavior = {
...
execute: function (sprite, time, fps, context) { // sprite is the runner
var otherSprite;
for (var i=0; i < snailBait.sprites.length; ++i) {
otherSprite = snailBait.sprites[i];
if (this.isCandidateForCollision(sprite, otherSprite)) {
if (this.didCollide(sprite, otherSprite, context)) {
this.processCollision(sprite, otherSprite);
}
}
}
},
...
};
...
};
The collideBehavior object’s execute() method encapsulates the three collision-detection steps listed earlier with calls to the following methods:
• isCandidateForCollision(sprite, otherSprite)
• didCollide(sprite, otherSprite, context)
• processCollision(sprite, otherSprite)
The implementations of each of those methods are discussed in the following sections.
11.4. Select Candidates for Collision Detection
Sprites are eligible to collide with the runner when
• The sprite is not the runner
• Both the sprite and the runner are visible
• Neither the sprite nor the runner is exploding
The collideBehavior object’s isCandidateForCollision() method, shown in Example 11.5, implements that logic.
Example 11.5. Selecting candidates for collision detection: isCandidateForCollision()
var SnailBait = function () {
...
this.collideBehavior = {
...
isCandidateForCollision: function (sprite, otherSprite) {
// sprite is the runner
return sprite !== otherSprite && // not runner
sprite.visible && otherSprite.visible &&
// visible
!sprite.exploding && !otherSprite.exploding;
// not exploding
},
...
};
...
};
Next, let’s see how to detect collisions between qualifying sprites.
11.5. Detect Collisions Between the Runner and Another Sprite
The collideBehavior object’s didCollide() method, which determines whether the runner has collided with another sprite, is shown in Example 11.6.
Given the runner’s collision rectangle, didCollide() checks to see whether one of the rectangle’s corners or its center lies within the other sprite’s bounding box, as illustrated in Figure 11.6.
Figure 11.6. If one of the five points (yellow dots) lies within another sprite’s collision rectangle (white rectangle), it’s a collision
Determining whether a point lies within a rectangle does not require a great deal of mathematical acuity. The HTML5 canvas element’s 2D context makes it even easier with the isPointInPath() method, which returns true if a point lies within the canvas context’s current path.
The didCollide() method creates a rectangular path representing the other sprite’s bounding box with calls to beginPath() and rect(). The didCollide() method subsequently calls isPointInPath() to determine if any of the aforementioned five points within the runner lies within the other sprite’s bounding box.
You’ve seen how to implement collision detection with bounding boxes, but the technique can be more accurate and perform better than as presently described. In the sections that follow, you’ll see how to refine Snail Bait’s collision detection by modifying the runner’s bounding box and partitioning the game’s space.
Now that you’ve seen how to detect collisions, let’s take a look at how to process them.
Example 11.6. Check for collisions
var SnailBait = function () {
...
this.collideBehavior = {
...
didCollide: function (sprite, otherSprite, context) {
var o = otherSprite.calculateCollisionRectangle(),
r = sprite.calculateCollisionRectangle();
// Determine if either of the runner's four corners or its
// center lies within the other sprite's bounding box.
context.beginPath();
context.rect(o.left, o.top, o.right - o.left, o.bottom - o.top);
return context.isPointInPath(r.left, r.top) ||
context.isPointInPath(r.right, r.top) ||
context.isPointInPath(r.centerX, r.centerY) ||
context.isPointInPath(r.left, r.bottom) ||
context.isPointInPath(r.right, r.bottom);
},
...
};
...
};
Note: HTML5 Canvas 2D context hit detection
The canvas context’s isPointInPath() method, which determines whether a point lies within an arbitrary path, is a useful method for game developers.
Snail Bait uses isPointInPath() to determine whether points lie within rectangles, which is easy to do on your own. However, determining whether a point lies within an irregularly shaped path is a more challenging task, and that makes isPointInPath() more valuable.
11.6. Process Collisions
Once you detect a collision, you must do something about it. The collide behavior’s processCollision() method processes collisions between the runner and other sprites, as you can see from Example 11.7.
Example 11.7. Process collisions: processCollision()
var SnailBait = function () {
...
this.collideBehavior = {
...
processCollision: function (sprite, otherSprite) {
if (sprite.jumping && 'platform' === otherSprite.type) {
this.processPlatformCollisionDuringJump(sprite, otherSprite);
}
else if ('coin' === otherSprite.type ||
'sapphire' === otherSprite.type ||
'ruby' === otherSprite.type ||
'snail' === otherSprite.type) {
this.processAssetCollision(otherSprite);
}
if ('bat' === otherSprite.type ||
'bee' === otherSprite.type ||
'snail bomb' === otherSprite.type) {
this.processBadGuyCollision(sprite);
}
},
processBadGuyCollision: function (sprite) {
snailBait.explode(sprite); // sprite is the runner
...
},
processAssetCollision: function (sprite) {
sprite.visible = false; // sprite is the asset
...
},
...
};
...
};
When the runner collides with assets—coins, sapphires, or rubies—the collide behavior’s processCollision() method invokes processAssetCollision(), which makes the asset invisible by setting its visible attribute to false. In [Missing XREF!], we come back to processAssetCollision() to update the game’s score when the runner captures an asset.
When the runner collides with bad guys—bats, bees, or the snail bomb—processBadGuyCollision() explodes the runner with Snail Bait’s explode() method. That explode() method is discussed in Chapter 13.
Finally, the processPlatformCollisionDuringJump() method, shown in Example 11.8, processes platform collisions while the runner is jumping.
Example 11.8. processPlatformCollisionDuringJump()
SnailBait = function () {
...
this.collideBehavior = {
...
processPlatformCollisionDuringJump: function (sprite, platform) {
var isDescending = sprite.descendTimer.isRunning();
sprite.stopJumping();
if (isDescending) { // Collided with platform while descending
sprite.track = platform.track;
sprite.top = snailBait.calculatePlatformTop(sprite.track) -
sprite.height;
}
else { // Collided with platform while ascending
sprite.fall();
}
},
...
};
...
};
When the runner collides with a platform while she’s descending during a jump, she stops jumping and lands on the platform. If the runner was ascending, she collided with the platform from underneath it, so she falls. For now, the runner’s fall() method is implemented as shown in Example 11.9.
Example 11.9. Stopgap method for falling
SnailBait.prototype = {
...
// Snail Bait calls equipRunnerForFalling() at startup
equipRunnerForFalling: function () {
...
this.runner.fall = function () {
snailBait.runner.track = 1;
snailBait.runner.top =
snailBait.calculatePlatformTop(snailBait.runner.track) -
snailBait.runner.height;
};
...
},
...
};
The runner’s fall() method immediately places the runner on the bottom track, meaning the top of the lowest platform. In Chapter 12, you’ll see how to reimplement that method with realistic falling by incorporating gravity over time.
11.7. Optimize Collision Detection
There’s always room for improvement when it comes to collision detection. Snail Bait employs two techniques to increase accuracy and performance: refine the size of sprite collision rectangles and use spatial partitioning.
11.7.1. Refine Bounding Boxes
As you can see from Figure 11.7, collision-detection rectangles enclose the sprite they represent. The corners of those rectangles, however, are often transparent. That’s the case for the runner, as Figure 11.7 illustrates. Those transparent corners can result in false collisions, that are especially noticeable when two transparent corners collide.
Figure 11.7. The runner’s original bounding box
One way to eliminate false collisions resulting from transparent corner areas is to reduce the size of the sprite’s collision rectangle, as shown in Figure 11.8.
Figure 11.8. The runner’s revised bounding box
Snail Bait reduces the size of the runner’s collision rectangle by specifying a collision margin, shown in Example 11.10.
Sprites use their collision margins to shrink their collision rectangles, as discussed in Section 11.3.1, “Sprite Collision Rectangles,” on p. 278.
Reducing the runner’s bounding box makes Snail Bait’s collision detection more accurate than previously described because it eliminates false collisions. Next, let’s see how to make collision detection perform even better.
Example 11.10. Modifying the runner’s collision rectangle
SnailBait.prototype = {
...
createRunnerSprite: function () {
...
this.runner.collisionMargin = { // All values represent pixels
left: 20,
top: 15,
right: 15,
bottom: 20
};
...
},
...
};
11.7.2. Use Spatial Partitioning
Spatial partitioning involves partitioning a game’s space into cells, so that only sprites in the same cell can possibly collide. By eliminating collision detection for sprites that reside in certain cells, spatial partitioning often results in substantial performance increases. Snail Bait gets just such a performance increase by partitioning space, as shown in Figure 11.9.
Figure 11.9. Partitioning space into collision detection cells. In the screenshot, only three sprites are candidates for collision with the runner.
Example 11.11 shows a revised implementation of the collision behavior’s isCandidateForCollision() method whereby Snail Bait excludes all sprites in the right-hand cell in Figure 11.9 from collision detection, thus greatly reducing the amount of collision detection the game performs.
Note: More on spatial partitioning
Snail Bait’s spatial partitioning is as primitive as spatial partitioning gets. Other implementations of spatial partitioning such as octrees and binary space partitioning are appropriate for more complicated collision-detection scenarios.
Example 11.11. Refining the selection of sprites for collision detection
var SnailBait = function () {
...
this.collideBehavior = {
...
isCandidateForCollision: function (sprite, otherSprite) {
// sprite is the runner
return sprite !== otherSprite &&
sprite.visible && otherSprite.visible &&
!sprite.exploding && !otherSprite.exploding &&
otherSprite.left - otherSprite.offset < sprite.left + sprite.width;
},
...
};
...
};
11.8. Monitor Collision Detection Performance
Collision detection can easily be a performance bottleneck, especially for more mathematically intense collision-detection algorithms such as the Separating Axis Theorem. This chapter has illustrated simple techniques you can use to improve performance, such as refining bounding boxes and using spatial partitioning. But it’s also a good idea to constantly monitor your game’s performance so you can catch and fix performance problems soon after they appear.
All modern browsers come with sophisticated development environments; for example, Chrome, Safari, Firefox, Internet Explorer, and Opera all let you profile your code as it runs. Figure 11.10 shows Chrome’s profiler, which depicts how much time, relative to the total, is spent in individual methods. See Chapter 2 for more about profilers and development tools in general.
Figure 11.10. Collision-detection performance
Note: Snail Bait doesn’t always idle 90% of the time
Remarkable performance from hardware acceleration for games that run in the ubiquitous browser can easily be degraded by other activities unrelated to the game; for example, if your system backup software runs while you are playing a game, the game’s performance can degrade considerably.
HTML5 games, therefore, must be on constant lookout for unacceptably slow frame rates and should alert the player when the game runs too slowly. We discuss doing that in [Missing XREF!].
You can see in Figure 11.10 that Snail Bait’s didCollide() method takes only 0.05 percent of the game’s time. (The Self column, whose value for didCollide() is 0.01 percent, represents only the time spent directly in a method, not including time spent in methods that the method calls.)
11.9. Implement Collision Detection Edge Cases
Collision detection nearly always involves specific code for edge cases in addition to generalized code that accounts for collisions between arbitrary sprites. So far in this chapter, we discussed Snail Bait’s generalized code for collision detection and in this section we discuss one of Snail Bait’s collision-detection edge cases.
Snail Bait has two edge cases that are not properly handled by its generalized collision-detection code:
1. Collisions between the runner and the snail bomb
2. Collisions between the runner and platforms during a fall
In Chapter 12, we discuss the runner’s falling and the consequent collisions between the runner and platforms. In this section we discuss collisions between the runner and the snail bomb, as illustrated in Figure 11.11, which shows the runner and the snail bomb shortly before they collide.
Figure 11.11. Detecting collisions between the runner and the snail bomb
Recall from Section 11.5, “Detect Collisions Between the Runner and Another Sprite,” on p. 282 that the runner’s collide behavior detects collisions between the runner and other sprites by testing to see if one of five points within the runner’s collision rectangle lies within the collision rectangle of the other sprite. If so, a collision has occurred, as illustrated in Figure 11.6. That strategy, however, does not work when the other sprite is the snail bomb, as illustrated in Figure 11.12, which shows that the bomb can pass through the runner without any of the runner’s five points intersecting the bomb’s collision rectangle.
Figure 11.12. The snail bomb passes through the runner undetected
Because the generalized collision-detection code in the runner’s collide behavior does not always properly handle collisions between the runner and the snail bomb, we implement an edge case for that collision, as illustrated in Figure 11.13.
Figure 11.13. Invert collision detection for the snail bomb
We check for collisions between the runner and the snail bomb by effectively inverting the algorithm that we used to detect collisions between the runner and other types of sprites. Instead of checking to see whether points within the runner lie within the bomb’s collision rectangle, we check to see if the center of the bomb lies within the runner’s collision rectangle. We begin by modifying the runner’s collide behavior, as shown in Example 11.12.
Example 11.12. Check for collisions, revised
var SnailBait = function () {
...
this.collideBehavior = {
...
didCollide: function (sprite, otherSprite, context) {
var o = otherSprite.calculateCollisionRectangle(),
r = sprite.calculateCollisionRectangle();
if (otherSprite.type === 'snail bomb') {
return this.didRunnerCollideWithSnailBomb(r, o, context);
}
else {
return this.didRunnerCollideWithOtherSprite(r, o, context);
}
},
...
};
...
};
Like the original implementation of the collide behavior’s didCollide() method, the revised implementation obtains references to collision rectangles for the runner and the other sprite. Unlike the original implementation, however, the didCollide() method subsequently invokes one of two helper methods, depending on the type of the other sprite. The didRunnerCollideWithOtherSprite() method is listed in Example 11.13.
Example 11.13. Check for collision with sprites other than the snail bomb
var SnailBait = function () {
...
this.collideBehavior = {
...
didRunnerCollideWithOtherSprite: function (r, o, context) {
// Determine if either of the runner's four corners or its
// center lies within the other sprite's bounding box.
context.beginPath();
context.rect(o.left, o.top, o.right - o.left, o.bottom - o.top);
return context.isPointInPath(r.left, r.top) ||
context.isPointInPath(r.right, r.top) ||
context.isPointInPath(r.centerX, r.centerY) ||
context.isPointInPath(r.left, r.bottom) ||
context.isPointInPath(r.right, r.bottom);
},
...
};
...
};
The didRunnerCollideWithOtherSprite() method checks to see if any of the runner’s five points lie within the collision rectangle of the other sprite, which is identical to the original implementation of didCollide(). The most interesting aspect of the revised didCollide() method is the didRunnerCollideWithSnailBomb() method, an operation listed in Example 11.14.
The didRunnerCollideWithSnailBomb() method creates a rectangular path that outlines the location of the runner. The method then checks to see whether the bomb’s center lies inside that path; if so, the runner and the snail bomb have collided.
Example 11.14. Check for collision with the snail bomb
var SnailBait = function () {
...
this.collideBehavior = {
...
didRunnerCollideWithSnailBomb: function (r, o, context) {
// Determine if the center of the snail bomb lies
// within the runner's bounding box.
context.beginPath();
context.rect(r.left + snailBait.spriteOffset,
r.top, r.right - r.left, r.bottom - r.top);
return context.isPointInPath(o.centerX, o.centerY);
},
...
};
...
};
11.10. Conclusion
Collision detection can be one of the most challenging aspects of implementing video games.
In this chapter you saw an overview of collision-detection techniques, followed by an in-depth examination of Snail Bait’s bounding box collision detection. The collision detection that we implemented in this chapter has the curious distinction of not performing any math whatsoever other than addition and subtraction, which is rare among collision detection algorithms. The reason we were able to eschew mathematics of any complexity entirely in this chapter is because of the isPointInPath() method of the HTML5 canvas element’s 2D graphics context. That method, which determines whether a point is in the current path, performs all the math that we needed in this chapter.
Optimizing collision detection is as important as implementing it in first place, so in this chapter we discussed two common techniques for making collision detection more accurate with better performance: refining bounding boxes and using spatial partition.
This chapter is the least of the collision-detection arcana; indeed, entire books are available on the topic. When you implement collision detection for your own game, explore your options and select the simplest implementation that will suffice for your needs.
Finally, the collision detection that we implemented in this chapter cannot detect collisions between the runner and a platform when the runner falls from the topmost platform to the bottommost. In that case the runner is moving too fast and the platforms are too thin for the simple bounding box collision detection that we implemented this chapter. At the end of Chapter 12 we see how to implement collision detection for that edge case.
11.11. Exercises
1. Profile the final version of Snail Bait and note how much time Snail Bait is idle. Subsequently, remove spatial partitioning from Snail Bait’s collision detection and run the profiler again. How does spatial partitioning affect performance?
2. Implement a method that draws sprite collision rectangles as the game is in progress, as illustrated in Figure 11.5.
3. Experiment with bounding-box sizes by modifying the collision margins for different sprites.