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
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).
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.