Game Development Reference
Figure 6.4. The structure of the grid-cell-based spatial hash. The black dot at the top is
a fluid particle, which is mapped to hash buckets—the rectangular grid—using the hash
function H ( x ) . A hash bucket contains a list of grid cells instead of fluid particles, rep-
resented by the variable-length chains of squares. The discretized position D ( x ) of the
fluid particle is used to find the grid cell (if any) it belongs to. Every grid cell references
a list of fluid particles located within the grid cell—the bottom layer. Note that this figure
shows only the concept of the structure; it is not representative of the memory layout for
an optimized implementation.
Calculate the hash bucket to which the fluid particle maps using the hash
function H ( x ) in the same way as for the original spatial hash. However,
keep the discretized fluid-particle position D ( x ) as its grid cell coordinates.
Using the hash index and grid cell coordinates, select the grid cell list of
the indexed hash bucket and iterate over it to find the grid cell matching the
grid cell coordinates.
- If a grid cell is found, insert the fluid particle into the list of fluid
particles referenced by the grid cell.
- Otherwise, a new grid cell is created and inserted into the hash bucket,
after which the fluid particle is inserted into the grid cell.
The complexity of this operation is not constant anymore, as we have to traverse
the list of grid cells mapped to the hash bucket. Instead, it is of time complexity