So how can we achieve the magic that the broad phase promises us? Look at 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 already guess what we could do to eliminate some checks? The blue grid in Figure 8-16 represents cells we partition our world with. 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 Mario could potentially collide with are in different cells. We thus 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 each bounding shape of each object according to the object's position. We can of course also include the orientation and scale as well here.

■ Figure out which cell or cells each object is contained in based on its bounding shape, and add it to the list of objects contained in those cells.

■ Check for collisions, but only between object pairs that can collide (e.g., Goombas don't collide with other Goombas) and are in the same cell.

This is called a spatial hash grid broad phase, and it is very easy to implement. The first thing we have to define is the size of each cell. This is highly dependent on the scale and units we use for our game's world.

0 0