3
\$\begingroup\$

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

\$\endgroup\$
2

1 Answer 1

Reset to default
3
\$\begingroup\$
  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).

enter image description here

\$\endgroup\$
5
  • \$\begingroup\$ To see if I understand: Each 'cell' in the grid is a data structure, preferably a list. When checking for collisions, I loop through the 2nd array, and in every cell (a list), I loop through all of it's objects, and check if they collide with each other. This way, for a tank, I only need to check if it intersects with missiles in the grid that it's in, and not with every missile in the screen. Right? \$\endgroup\$
    – user3150201
    Jan 25, 2014 at 16:59
  • \$\begingroup\$ Yeah, correct. It is important to remember that it will probably be in multiple cells some of the time. \$\endgroup\$
    – AturSams
    Jan 26, 2014 at 9:13
  • \$\begingroup\$ In the beginning of each turn, reset each cell (in the grid) that you have used in the previous turn. It's sometimes better to keep a SET (list with no duplicates) of currently active cells (so you don't have to clear all the cells). Good luck. \$\endgroup\$
    – AturSams
    Jan 26, 2014 at 9:28
  • \$\begingroup\$ Thanks. But how can I know which cell every object is in, without iterating through all of the objects and checking their location? I mean, if I know that cell 0,1 has certain boundaries, and I know that going out of these boundaries means entering another cell, than I need to iterate through all of the objects in that cell and check if they came out of it. Is there a way to avoid this? \$\endgroup\$
    – user3150201
    Jan 26, 2014 at 10:50
  • \$\begingroup\$ I think I understand. You could simply have a list of cells that were not empty in the last round. Free their contents. Iterate over all objects and re-add them to the relevant grid cells. Then check for collisions over each cell that contains collideables. \$\endgroup\$
    – AturSams
    Jan 26, 2014 at 14:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .