5
\$\begingroup\$

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 statements:

if (object overlaps area 1) put it in cell 1;

if (object overlaps area 2) put it in cell 2;

... // until 40

My question: Using 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.

Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
4
\$\begingroup\$

The simple approach is just this: Each entity remembers what cells it is in.

Each time the entity moves (or rotates or changes size or etc), check whether the cells it is in post-moving are the same as the cells it was in before moving. If the pre-move cells are the same as the post-move cells, do nothing. If there are any differences, update the grid by removing this particular entity from the old cells, and then adding it to the new ones. For bonus points, only remove the entity from the cells which it used to be in but isn't now, and only add it to the cells which it wasn't in before, but is now.

In most games, many entities will tend to remain stationary, and so doing the processing only when an entity moves (rather than always for every entity at the end of every update) will automatically avoid performing this unnecessary logic for stationary entities.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ I think this approach is only simple for humans (not devices), since it requires to first, update the data structures of both the grid(X1) and its collidable entities(X2) and then run a check for collisions(X3). So you are doing three times the work for the same result. It would work alright in practice for most use cases but I think that if you profile it with a lot of objects, you"ll see it takes longer because of memory access. \$\endgroup\$
    – AturSams
    Mar 18, 2014 at 8:08
  • 1
    \$\begingroup\$ @ArthurWulfWhite If it's going to work in most use cases (as you say it will), then the approach that is simple for humans to understand and implement and debug is without a doubt the best approach, except in those few cases where profiling shows it to need further domain-specific optimisation. \$\endgroup\$
    – Trevor Powell
    Mar 18, 2014 at 8:31
  • \$\begingroup\$ I tend to agree +1. Debug time is an often ignored subject which is neglected when people either feel they have an unlimited amount of time (working solo as a hobby) or are more concerned with finishing as fast as possible (writing hard to read and maintain code). \$\endgroup\$
    – AturSams
    Mar 18, 2014 at 8:38
  • \$\begingroup\$ @ArthurWulfWhite With that said, I think it's unlikely that any "recalculate every entity every frame and remove and re-add all the grid cell contents every frame no matter what" solution will be faster than an approach which attempts to only recalculate the objects that actually move and only touch the grid cell contents that actually change. Especially when there are a lot of objects in the scene. (Although that's certainly only a benefit when many objects are stationary) \$\endgroup\$
    – Trevor Powell
    Mar 18, 2014 at 8:39
  • \$\begingroup\$ If objects are stationary, they ought to be in another category with a different stamp. It depends on various factors but I tend to think it's the least of the concerns if the game is swarmed with entities that are colliding with one anther, the real computation challenge would be what is done with them once you realize they've collided, physics(?), path adjustment(?) or something else. So it is probably not going to be main resource hog in the implementation. \$\endgroup\$
    – AturSams
    Mar 18, 2014 at 8:50
4
\$\begingroup\$

Each cell is a data structure such as a List, or an object containing such a data structure.

AFAIK this is not the way how it is usually implemented. This way you will waste lot of memory for arrays or lists, and lot of CPU cycles for manipulating them. For example, 32x32 grid will result in 1024 arrays/lists, and this will be especially bad with non-contigious memory layout (like with linked lists).

Instead, on every physics step every moved entity gets new spatial mask (I am assuming all still entities already have it). Every row and every column of grid are representing one bit of spatial mask. If object's bounds are lying in given row or given cell, then corresponding bit in object's spatial mask is 1, otherwise it is 0.

Then simply binary and of their spatial masks used to check whether objects are either surely-not colliding or may-be-colliding. On latter, you need then check collision with precise algorythm.

Algoriths example:

  • Prepare spatial mask. For each entity:

    • Erase spatial mask.
    • Calculate AABB.
    • Detect span of rows and columns in which object's bounds are lying.
    • Enable respective bits of spatial mask.

  • Find collisions. For each pair of entities:

    • Skip, if their spatial masks are not "intersecting" (and them).
    • Skip, if they are not colliding.
    • Gotcha.

You can pack both axes into one integer value, this way you will get 16x16 or 32x32 grid (on 32-bit and 64-bit systems respectively), I think it is precise enough for most situations and fast.

Also, if you have massive amounts of static geometry in your levels, I'd recommend building BSP-tree for it, and then using spatial masks only for dynamic objects.

See also: separating axis theorem.

Improve this answer
\$\endgroup\$
9
  • \$\begingroup\$ You could have more than 32X32 using this obviously but I don't see how the cost would not skyrocket if there are 1024 objects. Instead of costing roughly 1024(entities) * 4(overlapping cells) * 1(other object per cell) it will still cost 1024 * 1024, you are checking each object against every other object. Unless you mean that you are sorting the objects by their spatial mask which you did not mention and is exactly what a 1D grid is (which is not as good as a 2d grid). \$\endgroup\$
    – AturSams
    Mar 18, 2014 at 8:15
  • \$\begingroup\$ @TrevorPowell, thanx, my mistake, fixed now. Just messed my train of thoughts. \$\endgroup\$
    – Shadows In Rain
    Mar 18, 2014 at 8:33
  • \$\begingroup\$ @ArthurWulfWhite Binary and is quite faster than actually checking collision (even if it is as simple as AABB or radius), and most of checks will end here because most objects pairs are not colliding. \$\endgroup\$
    – Shadows In Rain
    Mar 18, 2014 at 8:44
  • \$\begingroup\$ It is superior to using bounding boxes directly but it doesn't scale too well. If you have 2^10, you get 2^20 operations. I see what you mean about linked lists and access time. You could resolve that by using an array for the first X (lets say 10 objects). That way you have more control over memory.It would only be about 40KB of pointers in memory and will probably remain in cache. \$\endgroup\$
    – AturSams
    Mar 18, 2014 at 9:15
  • \$\begingroup\$ @ArthurWulfWhite Well, if you want to handle 1k of dynamic entities, I think you should be serious and use another BSP. It does not imposes awkward limits. With carefull design BSP-tree may be laid into contigious array. Also I believe it will use much less memory (1024 * 12 * 2 or less). Not sure about actual search speed, pure opinion. \$\endgroup\$
    – Shadows In Rain
    Mar 18, 2014 at 10:37
1
\$\begingroup\$

There are some subtle implementation tips and tricks to resolve this:

  1. We aren't talking about regular lists. These lists's node elements each contain a time record of the last (discrete) time it was changed. This is normally the frames index. We'll call it a time stamp.

  2. When you add an object to a cell's list, you first look at the list's items. If the first node has has an outdated time record, you can discard it or overwrite it at this time.

  3. If the existing nodes time stamp is current then you need to check for collision against that node's object and then move to the next node on the list.

  4. If the next node is current, go to (3), else go to (2).

Feel welcome to comment if you have questions.

If an object isn't moving often (or not at all), it should be handled differently. If it's not moving at all, the time stamp should be unique to identify that (for instance -1). If it's moving rarely it would be easier to handle like @Trevor Powell suggested in his answer. By keeping a collection of pointers to the cells it's currently inhabiting, and updating these cells when it actually moves.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

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