Narrow Phase

Once we are done with the broad phase, we have to check whether the bounding shapes of the potentially colliding objects overlap. I mentioned earlier that we have a couple of options for bounding shapes. Triangle meshes are the most computationally expensive and cumbersome to create. It turns out that we can get away with bounding rectangles and bounding circles in most 2D games, so that's what we'll concentrate on here.

Circle Collision

Bounding circles are the cheapest way to check whether two objects collide. Let's define a simple Circle class. Listing 8-4 shows the code.

Listing 8-4. Circle.java, a Simple Circle Class package com.badlogic.androidgames.framework.math;

public class Circle {

public final Vector2 center = new Vector2(); public float radius;

public Circle(float x, float y, float radius) { this.center.set(x,y); this.radius = radius;

We just store the center as a Vector2 and the radius as a simple float. How can we check whether two circles overlap? Look at Figure 8-13.

Figure 8-13. Two circles overlapping (left), and two circles not overlapping (right)

It's really simple and computationally efficient. All we need to do is figure out the distance between the two centers. If the distance is greater then the sum of the two radii, then we know the two circles do not overlap. In code this will look as follows:

public boolean overlapCircles(Circle c1, Circle c2) { float distance = cl.center.dist(c2.center); return distance <= cl.radius + c2.radius;

We first measure the distance between the two centers and then check if the distance is smaller or equal to the sum of the radii.

We have to take a square root in the Vector2.dist() method. That's unfortunate, as taking the square root is a costly operation. Can we make this faster? Yes we can—all we need to do is reformulate our condition:

sqrt(dist.x x dist.x + dist.y x dist.y) <= radiusl + radius2

We can get rid of the square root by exponentiating both sides of the inequality, as follows:

dist.x x dist.x + dist.y x dist.y <= (radiusl + radius2) x (radiusl + radius2)

We trade the square root for an additional addition and multiplication on the right side. That's a lot better. Let's create aVector2.distSquared() function that will return the squared distance between two vectors:

public float distSquared(Vector2 other) { float distX = this.x - other.x; float distY = this.y - other.y; return distX*distX + distY*distY;

The overlapCircles() method then becomes the following:

public boolean overlapCircles(Circle cl, Circle c2) { float distance = cl.center.distSquared(c2.center); float radiusSum = cl.radius + c2.radius; return distance <= radiusSum * radiusSum;

Rectangle Collision

Let's move on to rectangles. First we need a class that can represent a rectangle. We previously said we want a rectangle to be defined by its lower-left corner position plus its width and height. We do just that in Listing 8-5.

Listing 8-5. Rectangle.java, a Rectangle Class package com.badlogic.androidgames.framework.math;

public class Rectangle {

public final Vector2 lowerLeft; public float width, height;

public Rectangle(float x, float y, float width, float height) { this.lowerLeft = new Vector2(x,y); this.width = width; this.height = height;

We store the lower-left corner's position in a Vector2 and the width and height in two floats. How can we check whether two rectangles overlap? Figure 8-14 should give you a hint.

Figure 8-14. Lots of overlapping and nonoverlapping rectangles

The first two cases of partial overlap and nonoverlap are easy. The last one is a surprise. A rectangle can of course be completely contained in another rectangle. That can happen in the case of circles as well. However, our circle overlap test will return the correct result if one circle is contained in the other circle.

Checking for overlap in the rectangle case looks complex at first. However, we can create a very simple test if we invoke a little logic. Here's the simplest method to check for overlap between two rectangles:

public boolean overlapRectangles(Rectangle rl, Rectangle r2) { if(r1.lowerLeft.x < r2.lowerLeft.x + r2.width && rl.lowerLeft.x + rl.width > r2.lowerLeft.x && rl.lowerLeft.y < r2.lowerLeft.y + r2.height && rl.lowerLeft.y + rl.height > r2.lowerLeft.y) return true;

else return false;

This looks a little bit confusing at first sight, so let's go over each condition. The first condition states that the left edge of the first rectangle must be to the left of the right edge of the second rectangle. The next condition states that the right edge of the first rectangle must be to the right of the left edge of the second rectangle. The other two conditions state the same for the top and bottom edges of the rectangles. If all these conditions are met, then the two rectangles overlap. Double-check this with Figure 8-14. It also covers the containment case.

Circle/Rectangle Collision

Can we check for overlap between a circle and a rectangle? Yes we can. However, it is a little more involved. Take a look at Figure 8-15.

Figure 8-15. Overlap-testing a circle and a rectangle by finding the closest point on/in the rectangle to the circle

The overall strategy for testing for overlap between a circle and a rectangle goes like this:

■ Find the closest x-coordinate on or in the rectangle to the circle's center. This coordinate can either be a point on the left or right edge of the rectangle, unless the circle center is contained in the rectangle, in which case the closest x-coordinate is the circle center's x-coordinate.

■ Find the closest y-coordinate on or in the rectangle to the circle's center. This coordinate can either be a point on the top or bottom edge of the rectangle, unless the circle center is contained in the rectangle, in which case the closest y-coordinate is the circle center's y-coordinate.

■ If the point composed of the closest x- and y-coordinates is within the circle, the circle and rectangle overlap.

While not depicted in Figure 8-15, this method also works for circles that completely contain the rectangle. Let's code it up:

public boolean overlapCircleRectangle(Circle c, Rectangle r) { float closestX = c.center.x; float closestY = c.center.y;

if(c.center.x < r.lowerLeft.x) { closestX = r.lowerLeft.x;

else if(c.center.x > r.lowerLeft.x + r.width) { closestX = r.lowerLeft.x + r.width;

if(c.center.y < r.lowerLeft.y) { closestY = r.lowerLeft.y;

else if(c.center.y > r.lowerLeft.y + r.height) { closestY = r.lowerLeft.y + r.height;

return c.center.distSquared(closestX, closestY) < c.radius * c.radius;

The description looked a lot scarier than the implementation. We determine the closest point on the rectangle to the circle, and then simply check whether the point lies inside the circle. If that's the case, there is an overlap between the circle and the rectangle.

Note that I added an overloaded distSquared() method to Vector2 that takes two float arguments instead of another Vector2. I did the same for the dist() function.

Putting It All Together

Checking whether a point lies inside a circle or rectangle can be useful too. Let's code up two more methods and put them into a class called OverlapTester, together with the other three methods we just defined. Listing 8-6 shows the code.

Listing 8-6. OverlapTester.java; Testing Overlap Between Circles, Rectangles, and Points package com.badlogic.androidgames.framework.math;

public class OverlapTester {

public static boolean overlapCircles(Circle c1, Circle c2) { float distance = c1.center.distSquared(c2.center); float radiusSum = cl.radius + c2.radius; return distance <= radiusSum * radiusSum;

public static boolean overlapRectangles(Rectangle rl, Rectangle r2) { if(rl.lowerLeft.x < r2.lowerLeft.x + r2.width && rl.lowerLeft.x + rl.width > r2.lowerLeft.x && rl.lowerLeft.y < r2.lowerLeft.y + r2.height && rl.lowerLeft.y + rl.height > r2.lowerLeft.y) return true;

else return false;

public static boolean overlapCircleRectangle(Circle c, Rectangle r) { float closestX = c.center.x; float closestY = c.center.y;

if(c.center.x < r.lowerLeft.x) { closestX = r.lowerLeft.x;

else if(c.center.x > r.lowerLeft.x + r.width) { closestX = r.lowerLeft.x + r.width;

if(c.center.y < r.lowerLeft.y) { closestY = r.lowerLeft.y;

else if(c.center.y > r.lowerLeft.y + r.height) { closestY = r.lowerLeft.y + r.height;

return c.center.distSquared(closestX, closestY) < c.radius * c.radius;

public static boolean pointInCircle(Circle c, Vector2 p) { return c.center.distSquared(p) < c.radius * c.radius;

public static boolean pointInCircle(Circle c, float x, float y) { return c.center.distSquared(x, y) < c.radius * c.radius;

public static boolean pointInRectangle(Rectangle r, Vector2 p) {

return r.lowerLeft.x <= p.x && r.lowerLeft.x + r.width >= p.x && r.lowerLeft.y <= p.y && r.lowerLeft.y + r.height >= p.y;

public static boolean pointInRectangle(Rectangle r, float x, float y) { return r.lowerLeft.x <= x && r.lowerLeft.x + r.width >= x && r.lowerLeft.y <= y && r.lowerLeft.y + r.height >= y;

Sweet, now we have a fully functional 2D math library we can use for all our little physics models and collision detection. Let's talk about the broad phase in a little more detail now.

0 0

Post a comment