Faster 2D Collision detection

Recently I've been working on a fast-paced 2d shooter and I came across a mighty problem. Collision detection. Sure, it is working, but it is very slow. My goal is: Have lots of enemies on screen and have them to not touch each other. All of the enemies are chasing the player entity. Most of them have the same speed so sooner or later they all end up taking the same space while chasing the player. This really drops the fun factor since, for the player, it looks like you are being chased by one enemy only. To prevent them to take the same space I added a collision detection (a very basic 2D detection, the only method I know of) which is.

Enemy class update method
Loop through all enemies (continue; if the loop points at this object)
If enemy object intersects with this object
Push enemy object away from this enemy object


This works fine. As long as I only have <200 enemy entities that is. When I get closer to 300-350 enemy entities my frame rate begins to drop heavily. First I thought it was bad rendering so I removed their draw call. This did not help at all so of course I realised it was the update method. The only heavy part in their update method is this each-enemy-loops-through-every-enemy part. When I get closer to 300 enemies the game does a 90000 (300x300) step itteration. My my~

I'm sure there must be another way to aproach this collision detection. Though I have no idea how. The pages I find is about how to actually do the collision between two objects or how to check collision between an object and a tile. I already know those two things.

tl;dr? How do I aproach collision detection between LOTS of entities?

Quick edit: If it is to any help, I'm using C# XNA.

• I'm wondering how you got it to go to 90K in the first place. mine chokes at 20K (i'm doing full SAT MTV detection though). But i looping through all enemies is the only thing that seems possible. What you need to do however is check if they have been checked already, because if you do like you say, then everyone is getting tested with everyone twice. – Delusional Logic Oct 31 '12 at 23:32
• This is a possible duplicate of gamedev.stackexchange.com/questions/39931/… – Markus von Broady Nov 1 '12 at 15:27
• There is a very good answer in the question that @MarkusvonBroady has linked. – Cypher Nov 1 '12 at 18:32
• possible duplicate of Quad trees/grid based collision - putting logic into action – Stephen Sep 5 '13 at 20:56

4 Answers

You already hit your problem right on the head, you are having every entity check against every other entity. What you will want is some type of 'Level of Detail' system (its pretty much a very simple scene graph, you are just using it for things other than rendering :)) where possible collision candidates are better selected.

I generally do three collections for systems like this. And when you are talking about the number of entities you are aiming to have you might even need to go with a full blown scene graph for this as the tracking data (3 lists per entity with an entry for every other entity) can quickly get out of control.

Basically though you have three lists. The first one should be a very small list of entities that you are going to check with interactions every frame. You determine this because they are within X range of the entity in question. As mentioned the point of this list is to contain every entity that can reasonably collide with another this frame.

The next list are ones that would be in a buffer range that Could move into range of the entity with out too much effort.. We will call this range X * 1.5 just for sake of argument. This is a time sliced list where you will only update a handful of them per frame but ensure that you are going through them fast enough to keep up appearances of things working smoothly.

The third list is the 'everything else' list and a way to avoid having this one might be worth while (Scanning the entire entity list and maybe checking to see if its in one of the other lists before progressing maybe? Depending on list sizes this might work, or it might make things a lot worse.) Objects in this list get checked least of all as it should definitely take more than a few frames to be placed into one of the other two lists.

What you will also need to do to maintain this is when you are doing the collision tests, make sure you update which list the entities are in. Ones that move out of range should be downgraded and likewise ones that move closer should be upgraded into a more actively checked list.

Assuming you are keeping things simple enough this should suit your needs. If you can tac in extra information to an existing rendering scene graph (assuming you have one) so you can query it to get a list of entities that are reasonably within range that would be even better as that is the entire point of a scene graph anyways (fast access to a list of relevant data based on a position). This would just potentially take more work to do and you should always consider what you need to do vs what you should practically do.

Hope this helps.

• This is a vague answer. And can we accept to miss some collisions ?? Much simpler, use a data structure that will do the surface partitionning for you, like the Quad Tree i talk about here. Even a Quad Tree needs a little fine tuning to avoid overhead, so i cannot imagine the complexity of the 'solution' you talk about. Basic programming rule : just use the right data structure. – GameAlchemist Nov 2 '12 at 0:46
• @VincentPiel A scene graph is no more complex than a quad tree. – Cypher Nov 2 '12 at 16:43
• @James : obviously it is more complex. If you don't mind grasping the full speed of the QuadTree, you can get a QuadTree lib on the net and have it working perfectly in a couple of hours. No question like : what do i put in the first list, the second, the third, how do i decide to put an entity in another list... and no collision missed. Why use a bike when you can have a car ? – GameAlchemist Nov 2 '12 at 16:51
• @VincentPiel I think you meant to @ your comment to Cypher instead of me here. Anywho a quad tree is just a type of scene graph and you have to remember you are running at X frames per second. If you are noticing missed collisions then you need to adjust your range thresholds to better balance things out. My solution is just a very simple approach of making sure you only check things every frame that have a chance of being collided with and then doing background/limited updates on the rest to see if they qualify for a higher priority yet. – James Nov 3 '12 at 2:59

You have to handle collisions with a sorted data structure, so you can have n*log(n) times instead of the terrible n^2. And n*log(n) is almost linear as you might know. One (classical) example is a quadtree, there's a quite simple and well written tutorial here, with graphics and code (Java) :

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Rq : it is quite easy to find an implementation for QuadTrees in any language. Still, you have to have to think about the right 'granularity' for the tree, and the bigger the tree size, the more we have entities that does not fit inside a node.
Rq 2 : since your space partitioning is done for collision detection only, you have perfect freedom to divide space as you like. For instance, i would not divide into four egal parts but rather i would use the baricenter of current level entities as a center for the new divide. 1) the algorithm is still n*log(n), 2) you loose the possibility to 'rebuild' the scene out of the tree -but you don't care- and 3) you have a much more balanced tree, less overhead.
Rq3 : Once you have your tree, a 'collision' between the screen and the entities give you... the visible entities !! in a time more like log(n), so why not if n is big ? (worst case is obviously a time in n for this approach.)

• Yeah, a quad tree is just a type of scene graph really. I just always assume that people who are here want to write things themselves, not use someone else's library in which case why stop at a quad tree, just find a complete collision library. – James Nov 3 '12 at 2:57

binary space partition tree, quadtree, octree(for 3D) are possible trees you can generate (or maintain, if you're ambitious) at every update call for every object you want collision to apply.

• This is more fitting to be a comment. Consider adding more to your answer. – user15805 Sep 5 '13 at 17:28

I am quite naive when talk comes about quad or oct tree. But I think that this method should do:

You will need to modify the player structure/class. Add an array/vector of pointers to other player structure.

Every second check distance between each two players. If it is so low that it is possible to reach within 1 sec then add that player's pointer to current player's collision array.

Now only check the collision between players in each others list.