Game Development of .Nettrix: GDI+ and Collision Detection - Proximity Algorithms
(Page 5 of 22 )
In the previous code example, we discussed a simple method for checking the proximity of two bounding boxes. Here we’ll show you other ways to calculate proximities for circles and between circles and squares.
The basic idea behind such algorithms is to calculate the distance between the centers of two objects, and then check the value against a formula that describes approximately the objects’ shapes. This method is as precise as the formula used to approximate the object shape—for example, you can have perfect collision detection between balls, in a snooker simulator game, using the right formula.
Some of the most common formulas calculate the distances between squares, circles, and polygons.
Calculating Collision for Circle Objects
Figure 1-13. Circle proximity
When dealing with circular objects, you achieve a perfect calculation using the Pythagorean theorem, which allows you to calculate the distance between the centers (hypotenuse) using the square root of the sum of the squares of the other sides.
Dx = Math.Abs(Object1.CenterX - Object2.CenterX);
Dy = Math.Abs(Object1.CenterY - Object2.CenterY);
double Distance = Math.Sqrt(Dx*Dx + Dy*Dy);
if (Distance > Object1.radius + Object2.radius)
// => The circles do not collide.
else
// => The circles are overlapping.
If you just want to check the distance against a constant value, you don’t need to calculate the square root, making operations faster.
Calculating Collision between Circles and Squares The next algorithm is actually a commonly used formula called Arvo’s Algorithm (named after Jim Arvo, who pioneered many graphics algorithms). It is based on a principal similar to the proximity check between circles, using the Pythagorean theorem once again to help you decide whether the circle and square intersect. Figure 1-14 depicts some different types of proximities that a circle and square could have.
Figure 1-14. Square/Circle proximities
Before we show you the algorithm, create a unit of code, a class, that describes what an Axis Aligned Bounding Box looks like. You’ll use a class to create multiple AABBs, which are called objects. This is the core concept of object-oriented programming, which we’ll cover in more detail as we go along. Since you should already have a beginner’s knowledge of C# syntax, you should find this class description very familiar.
public class AxisAlignedBoundingBox {
private float centerX, centerY; // Coordinate centers of the box
private float extentX, extentY; // Extents (width from center) of x and y
// Constructor
public AxisAlignedBoundingBox
(float CenterX, float CenterY, float ExtentX, float ExtentY) {…}
public float MaxX { get { return centerX+extentX } }
public float MinX { get { return centerX-extentX } }
public float MaxY { get { return centerY+extentY } }
public float MinY { get { return centerY-extentY } }
…
public bool CircleIntersect
(float CircleCenterX, float CircleCenterY, float Radius) {…}
…
}
Now that you have a simple description of the class, look at the CircleIntersect method more closely.
public bool CircleIntersect
(float CircleCenterX, float CircleCenterY, float Radius) {
float dist = 0;
// Check x axis. If Circle is outside box limits, add to distance.
if (CircleCenterX < this.MinX)
dist += Math.Sqr(CircleCenterX – this.MinX);
else if (CircleCenterX > this.MaxX)
dist += Math.Sqr(CircleCenterX – this.MaxX);
// Check y axis. If Circle is outside box limits, add to distance.
if (CircleCenterY < this.MinY)
dist += Math.Sqr(CircleCenterY – this.MinY);
else if (CircleCenterY > this.MaxY)
dist += Math.Sqr(CircleCenterY – this.MaxY);
// Now that distances along x and y axis are added, check if the square
// of the Circle's radius is longer and return the boolean result.
return (Radius*Radius) < dist;
}
Figure 1-15 shows what the calculation would look like for a circle that intersects an AABB near a corner.
Figure 1-15. Square/Circle proximity algorithm in action
If you think this is too much math, this is probably the place where you should take this book back and take up something less mathematically demanding, like nuclear physics! Honestly, we can’t overemphasize how important math is when it comes to computer games. Basic algebra and geometry are essential for simple games, and very quickly in your career you will need advanced knowledge of linear algebra and physics in order to be an effective game developer. Well over 90 percent of the programming you’ll do when writing games will be related to math (Now don’t you wish you had stayed awake in algebra class??)
 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: Optimizing the Number of Calculations >>
More .NET Articles
More By Apress Publishing
/ 8 
