11
\$\begingroup\$

I'm well aware of how to detect if two or more 2D objects collide but I'm interested in how to decide whether to check for a collision. In previous projects, I just had every object check against every other object (I know, O(n^2) level of stupidity) and it created a less than fluid gameplay.

Various forums hail the greatness of Quadtrees, B-Trees, and any other kind of tree or structure you can think of.

What is the most efficient structure for determining whether a collision should be checked?

\$\endgroup\$
7
  • 1
    \$\begingroup\$ One thing you may want to consider is only checking collisions for objects that have moved, and the only the objects that are close to you. My current system works well (hundreds of thousands of objects)- and that's all I'm doing. \$\endgroup\$
    – ultifinitus
    Commented Oct 7, 2011 at 20:31
  • \$\begingroup\$ I think gamedev.stackexchange.com/questions/14369/… could help you alot. it was originally meant for and algorithm for parallel processing but I think the same algorithm could also improve single threaded applications. \$\endgroup\$
    – Ali1S232
    Commented Oct 7, 2011 at 20:57
  • 1
    \$\begingroup\$ @ultifinitus That's essentially what I'm asking about. How do I determine which objects are nearby without iterating through every object and checking it's position? \$\endgroup\$
    – Mike Cluck
    Commented Oct 7, 2011 at 22:24
  • \$\begingroup\$ Mike, you can email me for some specific code that I used, it's in c++- or I can give you the basic structure, though it may get rather ambiguous and complicated because of that. \$\endgroup\$
    – ultifinitus
    Commented Oct 8, 2011 at 6:38
  • 1
    \$\begingroup\$ It's not a duplicate because I was asking what kind of structure is best suited for determining whether we should bother checking for a collision. That other question was asking about transparent vs. non-transparent collisions. Not to mention, this question was asked about a year before the one you linked to. \$\endgroup\$
    – Mike Cluck
    Commented Jan 26, 2014 at 21:30

3 Answers 3

Reset to default
14
\$\begingroup\$

For a 2d game, unless the 2D objects have a very heavy distribution to one side of your map, a uniform grid is almost always the way to go. The memory complexity is straight forward, (proportional to the dimensions of your map), and with a reasonable distribution, has O(1) look-up time and an average of log(numberOfObjects / (rows * columns)) ^ 2 intersection tests done per cell. You might decide to only check cells which have had an object move in them, which makes static geometry much more efficient. It's easy to modify a uniform grid on the fly, (much less of a pain than in tree based solutions), and it is simpler to implement. The only time I would say not to use it in a 2D game is when the memory requirements of a uniform grid become too large, (say a space sim where the levels are sparse but enormous).

\$\endgroup\$
4
  • \$\begingroup\$ How does this solution deal with objects that border 2 or 4 grid cells? \$\endgroup\$
    – ashes999
    Commented Jan 10, 2012 at 23:18
  • 1
    \$\begingroup\$ Any cell the object overlaps, it is considered to be in, so an object can be in multiple cells. Most spatial data structures will deal with the issue of overlaps in a similar way. \$\endgroup\$
    – Darcy Rayner
    Commented Jan 10, 2012 at 23:27
  • \$\begingroup\$ Wow, that's preetty smart. +1 Cheers dude. \$\endgroup\$
    – ashes999
    Commented Jan 11, 2012 at 14:31
  • \$\begingroup\$ Just to complement the answer, if you assign a power of 2 (a bit) to each of the grid cells, you can do 2^(x/column_width+columns*y/row_width) (integer divisions) to easily find out which cell you're in (you'd calculate it for each object prior to starting the collision checks, and you can even combine the cells you get for each vertex of your shape by doing a bitwise OR with the obtained numbers). So this way, checking if two objects share a cell is as easy as if(bitwise AND) (and you only have to do the proper collision test if that bitwise AND is true). \$\endgroup\$
    – Rusca8
    Commented Jan 23, 2022 at 10:39
2
\$\begingroup\$

2D Physics engines such as Box2D and Chipmunk, make heavy use of a spatial Hash Map

see http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection for reference. The chipmunk demos include a really good spatial hash visualizer which makes it really clear how they technique works.

\$\endgroup\$
1
\$\begingroup\$

If your world has one very "long" dimension (call it X), compared to others, you can keep the objects in an ordered-list which you can re-sort as they move, and then collision detection means only checking for objects which overlap in the X axis.

Another possibilty is to keep active/passive lists of objects, and don't bother with the passive objects (which aren't moving at all).

If they are all medium-sized objects which are visible to the player on the screen, everything vs everything is probably not too bad.

Other than that, I'm with Darcy, a uniform grid is good.

\$\endgroup\$

You must log in to answer this question.

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