2d - How to implement uniform grids

Up until now, I implemented all-against-all collision detection in my games. It worked fine.

But I reached a point where implementing this kind of collision detection, makes the game run poorly, because there are two many objects to iterate through and check for collision.

I have searched this site and found something about 'uniform grids'. But I didn't completely understand what it is and how to implement it. Tried to Google it but nothing easy enough to understand came up.

I am a beginner to 2D-game programming. Do you mind trying to explain to uniform-grids, or link me to some good tutorial?

Thanks a lot

Answer

1. Create a 2d-array with approximately one square cell per the one collide-able object (considering the approximate max amount).


2. Each cell in the 2d-array is a iterate-able container (data structure) of your choosing (list preferably) of collide-able objects with a bounding box that currently overlaps / intersects with that cell. It needs to be updated every frame (if the object moves).


3. You only check for collisions between objects that are in the same cell(s) and you only check once every frame.

See the image, you would check the green ellipse against the green circle cause they are both in (1, 2).