Game Development Reference
In-Depth Information
The grid has the structure
struct Grid
{
unsigned int xExtent;
unsigned int zExtent;
ObjectSet *locations; // An array of size (xExtent * zExtent)
Vector origin;
Vector oneOverCellSize;
};
where xExtent and zExtent store the number of cells in each direction of the grid;
the x and z components of the oneOverCellSize vector contain 1 divided by the size
of each cell (we use 1 over the value rather than the actual size to speed up the next
algorithm); the y component is normally set to 1; origin is the origin of the grid. The
grid should be large enough so that any object in the game is contained within it.
To determine the location in which the center of an object is contained, we use a
simple algorithm:
struct Grid
{
// ... Previous code as before ...
def getLocationIndex(const Vector& object)
{
Vector square = object.componentProduct(oneOverCellSize);
return (unsigned int)(square.x) + xExtent*(unsigned int)(square.z);
}
};
In this code snippet, we first find which square the object is in by dividing each com-
ponent by the size of the squares (we do the division by multiplying by 1 over the
value). This gives us a floating-point value for each component in the vector called
square . These floating-point values need to be converted into unsigned integers. The
integer values are then used to find the index in the grid array, which is returned.
Just as in the BSP and quad-tree cases we need to decide what to do with objects
that overlap the edge of a square. It is most common to simply place them into one cell
or the other, although it would be possible to place them into all the cells they overlap.
Just as before, the latter makes it faster to determine the set of possible collisions, but
can take up considerably more memory. I'll look at this simpler case before returning
to the more complex case.