2D Game Programming Tricks - Beginning Android Games - page 378

Of course, there's some correspondence between Bob's bounding shape and his graphical
representation in the texture, as we base the bounding shape on that graphical representation.
Our MVC pattern is thus not entirely clean, but we can live with that.
Broad-Phase and Narrow-Phase Collision Detection
We still don't know how to check for collisions between our objects and their bounding shapes,
however. There are two phases in collision detection:
Broad phase : In this phase, we try to figure out which objects might potentially
collide. Imagine having 100 objects that could collide with each other. We'd
need to perform 100 × 100 / 2 overlap tests if we chose, naively, to test each
object against the other objects. This naïve overlap testing approach is of O( n 2 )
asymptotic complexity, meaning it would take n2 steps to complete (it actually
could be finished in half that many steps, but the asymptotic complexity leaves
out any constants). In a good, non-brute-force broad phase, we can try to figure
out which pairs of objects are actually in danger of colliding. Other pairs (for
example, two objects that are too far apart for a collision to happen) will not
be checked. We can reduce the computational load this way, as narrow-phase
testing is usually pretty expensive.
Narrow phase : Once we know which pairs of objects can potentially collide, we
test whether they really collide or not by doing an overlap test on their bounding
shapes.
We'll discuss the narrow phase first and leave the broad phase for later, as the broad phase
depends on some characteristics of our game, while the narrow phase can be implemented
independently.
Narrow Phase
Once we are done with the broad phase, we have to check whether the bounding shapes
of the potentially colliding objects overlap. As discussed earlier, we have a few options for
bounding shapes. Triangle meshes are the most computationally expensive and cumbersome to
create, but in most 2D games you don't need them and can get away with using only bounding
rectangles and bounding circles, so that's what we'll concentrate on here.
Circle Collision
Bounding circles are the cheapest way to check whether two objects collide, so 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;