Game Development Reference
In-Depth Information
Our world will look like this later on, but for now we can overlay a spatial hash grid. How big
should the cells of the hash grid be? There's no silver bullet, but a good heuristic is to have them
five times bigger than the biggest object in the scene. In our example, the biggest object is the
cannon, but we don't collide anything with the cannon, so we can base the grid size on the next
biggest objects in our scene, the targets. These are 0.5×0.5 m in size. A grid cell should thus
have a size of 2.5×2.5 m. Figure 8-18 shows the grid overlaid onto our world.
Figure 8-18. Our cannon world, overlaid with a spatial hash grid consisting of 12 cells
We have a fixed number of cells—in the case of the cannon world, 12. We give each cell a
unique number, starting at the bottom-left cell, which gets the ID 0. Note that the top cells
actually extend outside the world. This is not a problem; we simply need to make sure all our
objects stay inside the boundaries of the world.
What we want to do is figure out to which cell(s) an object belongs. Ideally, we want to calculate
the IDs of the cells in which the object is contained. This allows you to use the following simple
data structure to store your cells:
List<GameObject>[] cells;
That's right; we represent each cell as a list of GameObject is The spatial hash grid itself is just
composed of an array of lists of GameObject s.
Now we can figure out the IDs of the cells in which an object is contained. Figure 8-18 shows
a couple of targets that span two cells. In fact, a small object can span up to four cells, and
an object bigger than a grid cell can span more than four cells. We can make sure this never
happens by choosing the grid cell size to be a multiple of the size of the biggest object in our
game. This leaves us with the possibility of one object being contained in, at most, four cells.
To calculate the cell IDs for an object, we simply take the four corner points of the bounding
rectangle and check which cell each corner point is in. Determining the cell that a point is in is
easy—we just need to divide its coordinates by the cell width. Say you have a point at (3,4) and
a cell size of 2.5×2.5 m: the point would be in the cell with ID 5, as in Figure 8-18 .
 
Search WWH ::




Custom Search