Graphics Reference
In-Depth Information
if (object overlaps east cell border)
check southeast neighbor cell
}
When testing neighboring cells, range checking of grid coordinates can be avoided
by placing a layer of sentinels (dummy cells) around the border of the grid.
7.1.7
Additional Grid Considerations
Some issues relevant to efficient implementations remain. First, the presentation
given here has implied that grids are kept from frame to frame and are incrementally
updated. Although this is a good approach in general, arguments can also be made for
a simpler approach in which the grid is simply cleared and all objects are readded from
scratch each frame. For example, if most or all objects move, the latter operation may
turn out cheaper than trying to update the grid data structure. Rebuilding the grid each
frame also typically requires simpler data structures, which tends to reduce memory
requirements (such as single-linked lists instead of double-linked lists). Readding all
objects each frame also means objects can be tested as they are added, avoiding the
potential problem of getting both
A-collides-with-B
and
B-collides-with-A
reported.
A second thing to keep in mind is that not all objects have to be added to the grid
at all times. When testing distinct collision groups against each other, the objects of
the first group can be directly added to the grid. Then, when testing the objects of the
second group against the grid they do not have to be added to the grid at all. They
only have to be used as query objects. An example of such a scenario is a group of
enemy objects and another group of player bullets.
Last, it is worthwhile considering grid cell volumes and cell orientations different
from those explored here. For instance, assume the grid is primarily used for per-
forming line segment queries against a given set of objects in the plane (as discussed
further in Section 7.4.2). Because lines at an angle may pass through more cells than
do horizontal or vertical lines, it would be possible to have two grids, both containing
the same set of objects but one grid at a 45-degree relative orientation to the other.
Based on the orientation of a given line segment, the appropriate grid can now be
used for the intersection query to improve efficiency.
Similarly, compare the regular uniform grid and the staggered hexagonal-like grid
cell arrangement shown in Figure 7.7. Assume the spherical objects
A
and
B
are at
most half the size of the grid cell side, are assigned to a single cell, and are tested
one at a time. In this scenario, if the objects are placed using their centers
A
must
check collisions against nine cells whereas
B
would have to check against just seven
cells. If instead
A
and
B
were boxes, assigned using the top left-hand corner,
A
would
have to test against five cells (center, east, south, southeast, and either northwest or
southwest) and
B
only four cells (center, east, southwest, and southeast).
