Spatial partitioning refers to dividing up some space (such as the game world) into regions with the intent to efficiently search or traverse those regions or the objects within those regions.

Spatial partitioning is an important divide-and-conquer technique used in games, typically for optimizing queries for game objects.

Hierarchical data structures such as trees are common in spatial partitioning techniques (BSP trees, kd-tree, bounding volume hierarchies), but non-hierarchical solutions, such as grid partitioning, are also applicable.

history | excerpt history