Collision detection with moving objects

Question

I searched a lot about this problem. I found many answers here in Stack Exchange but none of them really answers when positions for objects get updated.

For a game with fixed size map and that has all the time:

• 200+ moving objects with different sizes (bullets, players, NPCs, etc.)
• 100+ static objects with different sizes (obstacles, health packs, etc.)

I am looking for an efficient way to do collision detection. Here is the pseudo code:

in each game loop (15 ms):
   collect movement commands and apply force on objects of those commands
   loop with very small physics time steps (0.1 ms):
      for object in movingObjects:
         get objects that might collide with current object   // --> 1
         check if any collision occurs
      for object in movingObjects:
         update position of object (based on command collected) // --> 2

So:

1. I get the objects that might collide with given object. It is done using a data structure like quadtree or spatial hashing grid (or something else that makes more sense).

2. Object's position is updated. Now, how do I inform the data structure that this object's position is updated? I don't want to remove and insert. That is not efficient at all.

I feel like quad tree and spatial hash implementations all over the internet are avoiding this problem.

I would also appreciate if you tell me my pseudo code above is problematic. I have the feeling this uses too much CPU.

Answer 1

First, looking just at the code you might want consider the timings. Your main game loop is running every 15ms, fine (approx 60 fps). If you are actually running your inner physics at 0.1ms intervals inside that 15ms outer loop then thats 150 physics updates per frame - thats way to much.

I normally run my physics at 60fps but decoupled from the frame rate. Read this for more info. If your doing that to fix tunneling, there are other solutions.

Regarding the broad-phase algorithm there are many to choose from, but you need to pick a suitable one. As you point out, many have relatively high cost to maintain lots of dynamic objects. Other factors for choosing include:

• How big your world is
• How fast and clustered the game objects are
• How large the objects are

With the numbers you talk about above I'd either go for a regular grid or sweep and prune. They are both relatively simple to update each frame. For a regular grid, you mostly just need to clear each grid cell, and re-hash all the game objects each frame. Sweep and Prune can be even easier, you just need to maintain a sorted list in 1 dimension, its pretty good for long linear levels (2d Platformers etc).

If your really interested, I suggest you read this, a pretty detailed comparison of various algorithms in different use cases. http://0fps.net/category/programming/collision-detection/

Answer 2

If you need further optimisation, consider dynamic spatial hashing if you have heterogeneous spatial spaces, e.g. one grid has 30 objects and many others less than 5. Segregate overpopulated grid spaces into a new spatial hash grid.

Also, implement a probabilistic line collision detection. Mark the chage in distance between two frames. If distance is increasing, flag as "ignore". Only check again probabilistic collision detection if speed has changed.

Set speed vector to 0 and flag as static if object is moving minimalist, e.g. less than abs(0.0001). Don't check, of course, collision between two static objects. Don't update position of static flagged objects.

Use an preprocessed tables for squarerot distance calculations or use square distances instead of directly using square roots which can speed up your algorithm by up to 20%. You can do the same for trigonometric calculations.

That's all what I could think of. I get good performance of 20000 objects with my implementations. Surely you can squeeze out even more, e.g. line of flight probabilistic collision, update collision detection every 2nd frame for less relevant objects or objects that are not being rendered.