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.