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

Broad Phase
So how can we achieve the magic that the broad phase promises? Consider Figure 8-16 , which
shows a typical Super Mario Brothers scene.

Figure 8-16. Super Mario and his enemies. Boxes around objects are their bounding rectangles; the big boxes make up a
grid imposed on the world

Can you guess what you can do to eliminate some collision checks? The grid in Figure 8-16
represents cells with which we can partition our world. Each cell has the exact same size, and
the whole world is covered in cells. Mario is currently in two of those cells, and the other objects
with which Mario could potentially collide are in different cells. Thus, you don't need to check for
any collisions, as Mario is not in the same cells as any of the other objects in the scene. All we
need to do is the following:

ï?® Update all objects in the world based on our physics and controller step.

ï?® Update the position of the bounding shape of each object according to the

object's position. We can, of course, also include the orientation and scale.

ï?® Figure out in which cell or cells each object is contained, based on the

bounding shape, and add these to the list of objects contained in those
cells.

ï?® Check for collisions, but only between object pairs that can collide (for

example, Goombas don't collide with other Goombas) and are in the
same cell.