Efficient Collision detection

Newbie & Debugging Questions
#1

For about 2 years, I have been making small stupid games. Each game taught me a lot and I’m really enjoying the fact that I can make games. However, I’m bumping a lot of times into the best way to check collision with in game entities. The most simplistic approach would be:


for (Entity e: level.getEntities()) {
    if (e.collidesWith(this)) {
        // Do stuff
    }
}

Now, if we would have a system where every entity is checking collision with other entities, the amount of loops will explode exponentially and performance would crash. Someone told me the best solution to this is by having a binary search tree to only list entities that CAN collide with the current entity. I’ve been studying this thing, but can’t really get the hang of it.

  • What’s the best way to take care of this?
  • Could a binary search tree fix this?
#2

This only solves the e.collidesWith, and is probably what tdegroot is already doing.

Technically it’s only quadratic, but yes.

A BSP tree/kdtree/quadtree etc. can work, although a simple Bin/Cell structure is much simpler and usually plenty effective.
It’s also more performant than many trees when entities are often moving.
Note: The wiki page says each bin has a linked list, but just use an array list.

#3

If a search term would be helpful, ‘broad-phase collision detection’ is what you’re looking for. But, I’d try a simple grid system first, as BurntPizza suggested, and see if that meets your needs.

Also, maybe you’re already doing this, but you can improve the brute-force approach significantly by only checking each unique pair once, e.g. (pseudocode, may or may not get this right):


for (i = 0; i < numEntities - 1; ++i) {
    for (j = i + 1; j < numEntities; ++j) {
        test(entities[i], entities[j]);
    }
}

Depending on the number of entities involved, you might be able to get away with the above approach.

#4

Maybe you could maintain an ordered list of object low and high positions while moving them (well two lists - one each for x and y). Then simply read off the collisions afterwards. E.g. for 3 objects A, B and C, the horizontal list would read Alow,Ahigh,Blow,Bhigh,Clow,Chigh if there were no collisions.

Seems like making that list could be pretty cheap (OlogN or something, and even much less than that if the same list was modified rather than rebuilt with each quantum). Just an idea - don’t know how that would compare in complexity and/or speed to dividing the plane into bins?

#5

As soon as you say ‘maintain an ordered list’ it sounds more expensive. :stuck_out_tongue:
Sounds like a completely flattened interval tree.
The binning method pretty much already achieves this, just simply where all intervals are the same size and can be empty.
And I’m pretty sure you can’t populate a list with N elements in less than O(N) time, unless I’m not understanding something.

#6

This is a solved problem. Like BurntPizza mentioned, the go-to solution is to use a quadtree.

The basic idea is that you should only check for collision between objects that you know are close together. No sense checking for collision between an obstacle in China and a player in Brazil.

If a quadtree sounds complicated, then you can use the same idea but in a simpler implementation. A 2D grid system, for example.

Or you can stop reinventing the wheel and use something like JBox2D, which does physics and collision for you. It also comes as a part of libGDX.

#7

Heh sloppy typing - meant NlogN. But really i meant that it might not in practice be much more than constant if the list was reused since list positions might not often change and if they did then only by a position or two.

Nope, sorry. I refuse to believe the best solution’s been found to any problem let alone stuff that mankind’s only been mulling over 10 or 20 years!

The world always needs new wheel designs :smiley:

#8

This is also true of the binning method.

#9

I didn’t say we found the best solution. I said we’ve found a solution.

The first step to coming up with a better solution is to understand how existing solutions work.

#10

Lol - you say that as if what was suggested was rocket science :smiley: The OP asked about finding collisions so I suggested something simple which effectively eliminated the cost of that, of course trading off against extra cost when moving objects around. Other ways are just balancing that trade-off at different points and, i imagine, the “best” in any given situation will depend on more characteristics of the specific application than we know here.

To simply state it’s a “solved problem” because there’s a broadly suitable algorithm with a fancy name and a wikipedia page seems like closing down a potentially useful discussion.

#11

Bwah? You seem to be attributing an argument to me that I am not putting forth. OP asked about collision detection. I told them to check out quadtrees or existing libraries. That’s about it.

[quote=“richierich,post:10,topic:54623”]
At no point did I say your solution was incorrect or even inefficient. I’m leaving that to other people. :stuck_out_tongue:

[quote=“richierich,post:10,topic:54623”]
My only point was that other people have come up with solutions that are worth checking out before the OP tries to optimize a nested for loop. I’m not sure what your argument against that is, since all I’m saying is that quadtrees are worth googling.

You seem to be taking my statements as a personal argument against your idea, when in fact I don’t have any strong opinions about your idea at all.

#12

For what it’s worth, what you’re describing sounds like sweep and prune. This method does have some nice properties, but it’s considerably more complex than a grid-based system. For someone wanting to introduce a broad-phase step into their collision detection system, it seems like a grid is probably a good place to start, largely because it’s simple to implement. If that proves to be unsuitable for some reason (e.g. the space is too large to be comfortably represented by a grid), then other methods can of course be considered.

#13

Does your game in hand actually have performance problem with collision detection right now?

#14

+1 for simple cell grid, especially if the kinds things in your game don’t vary hugely in size, and the universe in which they live is of reasonably bounded size.

Variation:

I actually use two cell grids at different resolutions, one high-res one for ordinary collision detection, and another low-res one, which I use for “large collision detections” eg. dragging a circle over the world UI to select units: with the hi-res grid the number of cells that need to be checked for large circles was far too high.

Cas :slight_smile: