I was looking for an efficient way to implement collision detection in a 2D game. A way that won't result in an O(n^2) level of complexity.
A lot of people recommend to use Uniform Grids for this purpose. From what I gather, this means (please confirm if this is accurate):
- Dividing the screen to a grid of equally sized square areas. Each area is represented by a 'cell' inside a 2d array.
- Each cell is a data structure such as a List, or an object containing such a data structure.
- The cell contains references to all of the game objects that overlap with the area the cell represents (objects 'inside' the cell).
Each update step, every object in a cell is checked for collision with every other object in the same cell.
I understand all of this. But one thing is still not clear to me:
Every update step, I need to check if any game object left the cell it was inside of and moved to another cell. I always need to know which object is in what cell.
The only idea I had of how to do this, is each update step: 1- clear all of the cells. 2- Reassign all the objects to the cells.
Meaning: If I have 40 cells and 70 game objects on screen, every object of 70 is going to have to go through 40
if (object overlaps area 1) put it in cell 1; if (object overlaps area 2) put it in cell 2; ... // until 40
if statements (or a big
switch) for every object isn't reasonable. Please suggest a more efficient way to keep track of what objects are in what cells.
Thank you for your help, will be appreciated.