How are objects organized in a spatial partition?
This pattern is about applying that idea to spaces that have more than one dimension. For a set of objects, each has a position in space. Store them in a spatial data structure that organizes the objects by their positions. This data structure lets you efficiently query for objects at or near a location .
When do you update the spatial data structure?
When an object’s position changes, update the spatial data structure so that it can continue to find the object. This is a common pattern for storing both live, moving game objects and also the static art and geometry of the game world.
How are objects stored in a spatial data structure?
Store them in a spatial data structure that organizes the objects by their positions. This data structure lets you efficiently query for objects at or near a location . When an object’s position changes, update the spatial data structure so that it can continue to find the object.
What does space partitioning do to a space?
In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.
How are regions organized in a space partitioning tree?
Overview. The regions can be organized into a tree, called a space-partitioning tree . Most space-partitioning systems use planes (or, in higher dimensions, hyperplanes) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one…
How are units partitioned in a war game?
Opposing armies with hundreds of units will clash together on the field of battle. Warriors need to know which nearby enemy to swing their blades at. The naïve way to handle this is by looking at every pair of units and seeing how close they are to each other: