Game Development of .Nettrix: GDI+ and Collision Detection - Collision Detection
(Page 4 of 22 )
As we said at the start of the chapter, one of the most important concepts in game development is the collision detection algorithm. Some commercial games have gathered significant market shares just because their collision detection routines are faster, leaving more time for the graphics routines and allowing more responsive game play.
Just try to imagine some games without collision detection: a pinball game where the ball won’t bounce; a 3-D labyrinth where players go through the walls and the bullets don’t hit the enemy; an adventure game where the cursor doesn’t know if it’s over a specific object on screen. Without collision detection, a game loses any sense of predictability or reality.
Collision detection is a frequent research topic, and is a constant struggle between the balances of precision versus performance. The main goal here is to examine some basic concepts, so you can use them within the scope of the book and have a stepping stone to provide you with the basic tools and terms used in collision detection.
Note: For those who want to look into this topic in more detail, a simple search on the Internet will show many improved algorithms for advanced collision detection in 2-D and, mostly, in 3-D envi ronments. See Appendix A for other books and papers on collision detection. |
In the next sections, you’ll see some common collision detection algorithms.
Bounding Boxes One of the most common collision detection algorithms, the bounding boxes algorithm, uses the idea of creating boxes around objects in order to test a collision with minimum overhead and, depending on the object, an acceptable degree of precision. In Figure 1-7 you see some objects that you want to test for collisions, along with their bounding boxes.
Figure 1-7. Bounding boxes for an archer and a monster
In the game code, you must test if there’s any overlap between the boxes to test for collision, instead of testing every single pixel of the images. In Figure 1-7, for example, if the box surrounding the arrow touches the box surrounding the monster, it’s a hit.
Using bounding boxes on the sample in Figure 1-7 will probably lead to good results, although as a rule it’s better to use smaller boxes for the player. If a monster blows up when a bullet (or arrow) just misses it by a pixel, the player won’t complain; but if the situation is reversed, the player will feel cheated by the game. It’s better to create a narrower box for the archer to give the player a little more satisfaction.
You can now redefine the boxes as shown in Figure 1-8.
Figure 1-8. Revised bounding boxes for an archer and a monster
Generally speaking, the collision detection technique we’ll describe deals with Axis Aligned Bounding Boxes (AABB). These are bounding boxes that are specifically aligned with the x and y axis on a screen, which keeps all the calculations very simple. The 2-D techniques described here will generally apply to 3-D techniques as well, but the algorithms can get much more complex in three dimensions. In any case, simple 2-D collision detection isn’t really mathematically complex. An easy way to implement the AABB test is to divide the problem into two separate tests.
The first test, called the broad phase, simply tests to see if there’s a chance the two bounding boxes overlap. Imagine that you have a driving game and want to see if two cars are colliding. If one is in Seattle, and the other in New York, there’s little chance they will collide. A broad phase test gives you a sanity check on the boxes in question. If the absolute value of the distance between the centers of the two boxes is less than the sum of the extents (half the width or height of each box), then there’s a chance they overlap on that axis. If the boxes are colliding, then the broad phase test must be true for both axes. This approach is also called a proximity test, which we’ll go into in more detail later in this chapter. Let’s examine this graphically and in code.
In Figure 1-9, you see two rectangles that overlap on the x axis, but not on the y axis. Although the x axis test is true, the y axis test isn’t. Look at the code that does this test:
float Dx = Math.Abs(r2.x - r1.x);
float Dy = Math.Abs(r2.y - r1.y);
…
if (Dx > (r1.extentX+r2.extentX) && (Dy > (r1.extentY+r2.extentY))
// The boxes do not overlap.
else
// The boxes overlap.
Figure 1-9. Two nonoverlapping boxes
According to the code sample, the two boxes will only overlap if both x and y coordinates of rectangle 2 are within range of rectangle 1. Looking at the diagram, you see that the distance between the two boxes in the x axis is less than their combined extents, so there’s a chance of an overlap. This means that your boxes may be colliding. But the distance in the y axis is greater than the combined extents, which means that no collision is possible.
In Figure 1-10, you do have a collision, because the distances between the boxes (on both axes) are less than the combined extents.
If your broad phase test tells you the two rectangles are in proximity, then you can begin testing for finer-grained collisions. This is done in a variety of ways, but you’ll stick to simple proximity tests for now. You can easily see where the complexity gets higher and higher when you’re dealing with hundreds, if not thousands, of these types of tests. To make it even more complex, imagine that all these bounding boxes are moving in real time. It’s pretty easy to see why complex games need faster computers and graphics cards when you think about challenges like collision testing.
Figure 1-10. Two overlapping boxes
Creating Custom Rectangle Objects A simple improvement you can do in the algorithm is to create a custom rectangle object that stores two points of the box, the upper-left corner and the bottom-right one, so you can do the tests directly on the variables without having to perform a sum operation.
This method can be easily extended to nonrectangular objects, creating for each object a set of rectangles instead of a single rectangle. For example, for a plane, instead of using a single box (Figure 1-11), you can achieve much better precision using two overlapping boxes (Figure 1-12).
Figure 1-11. Approximating a plane shape with one box
Figure 1-12. Approximating a plane shape with two boxes
The drawback of this approach is that if you use too many boxes, the calculations will take longer, so you need to find a balance between precision and speed for each game or object. In many 3-D graphics applications, proximity tests are done to break the test down into smaller and smaller areas, until you are finally checking the intersection of the part you’re interested in. Using the preceding example, you might break the fuselage bounding box into additional boxes for the landing gear. Then you could do a collision check to see if any of the wheels were touching the runway. You can achieve greater and greater accuracy by successively doing collision checks against smaller and smaller bounding boxes.
Accuracy vs. Precision: What’s the Difference? Most programmers get confused with issues related to accuracy versus precision, which are two very different things. Look at two examples. Imagine you’re at an archery range with your friend. Your friend shoots an arrow and hits the outside ring of her target. She was accurate, but not precise. You draw your bow and fire, hitting the bull’s-eye—on your friend’s target! Your shot was precise, but not accurate. Another example is the value of pi (p). The number 3 can represent pi, but it’s not very precise. However, it’s a better choice than 2.14159, which is precise, but not accurate.
Computers are precise and accurate with scalar (countable) values like 1, 2, 3, etc., but have challenges with the precision of real numbers. This is based on two fundamental problems in modern computer technology. First, real numbers must be stored in a binary format. While this might seem trivial, it’s a very big challenge. For instance, the simple value of 1/10 cannot be represented consistently in a computer’s floating-point format, because the numbers are stored in base 2 (1/10 in base 2 yields a repeating number). The second challenge stems from how many bits can be dedicated to representing a real number, which limits the accuracy of the number. This results in bunching, where numbers have greater accuracy near zero and for very large values, but not as much in between.
For an advanced paper on this topic, see the reference for “What Every Computer Scientist Should Know About Floating-Point Arithmetic” in Appendix A.
 This chapter is from Beginning .NET Game Programming in C#, by David Weller, et al., (Apress, 2004, ISBN: 1590593197). Check it out at your favorite bookstore today.
Buy this book now. |
Next: Proximity Algorithms >>
More .NET Articles
More By Apress Publishing
/ 7 
