Optimising object management for performance and gameplay (e.g., collision detection).
Spatial grids avoid creating N2 problems when you want to perform collision detection between units in games. Without using spacing grids (or other culling approaches) very basic collision detection follows this sequence:
- For all other units
- Check if this unit collides
The output of a spatial grid, is a (semi) unique identifier to each grid space (you can define the grid to be any size you want). Along with this a fast lookup table is created whereby we can quickly lookup which objects exist in any give grid position.
For a good overview see the following links:
- https://matthias-research.github.io/pages/tenMinutePhysics/11-hashing.pdf
- https://github.com/SebLague/Fluid-Sim/tree/Episode-01
But simply, when a unit wants to check for collisions it can now follow a different sequence:
- Determine which surrounding grid square need to be checked
- For each grid square
- Check collisions only with units in that grid square
Now, there is a reasonable amount of setup required to get these spatial grids setup and working. The most intensive part is the requirement to sort objects based on their spatial grid position. Given that units will be regularly moving, this sorting must happen repeatedly
- Enhancements – spread frame sorting