Faster 2D Collision detection
- by eShredder
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.
