Grid based Broad-Phase Collision detection

4 May

This method is best suited when uniformly or very similarly sized objects are being tracked. If objects do not differ much in size each cell should be the size of the largest object. This makes it so only the center of each object needs to be tracked.

 

Example below:

PSizeOverlap from shapes in non-adjacent cells is impossible if the cells are as large or larger than every shape tracked. If shapes end up being larger however overlap is possible and we need to track the shape in every grid cell it exists.

 

If the cells are smaller that the largest object overlap will exist as demonstrated below.

If thisTooLarge happens we need to track more than just an objects center (covered below.) There are a few ways to solve this, increase the grid size, use another detection system or track more than just an objects center.  Increasing the grid size can have unexpected consequences.

 

If the cells are too large, there will be an excess of results in each cell eliminating efficiency and increasing computation to or towards On^2. As the picture to the left demonstrates. TooSmallEvery object in each cell will have to be checked against each other for overlap.

Spatial grid tracking can be accomplished using a hash table or a 2/3d array.  A 2d array is fairly straight forward.

The next post will cover creating a hash table, generating a cells key (from coordinates), finding neighbors and detecting overlap.  Followed by a post on creating bounding shapes to cover objects that are larger than a grids cell size.