Avoid O(n^2) complexity for collision detection

Question

I am developing a simple tile-based 2D game. I have a level, populated with objects that can interact with the tiles and with each other. Checking collision with the tilemap is rather easy and it can be done for all objects with a linear complexity. But now I have to detect collision between the objects and now I have to check every object against every other object, which results in square complexity.

I would like to avoid square complexity. Is there any well-known methods to reduce collision detection calls between objects. Are there any data-structures (like BSP tree maybe), which are easily maintained and allow to reject many collisions at a time.

For example, the total number of objects in the level is around 500, about 50 of them are seen on screen at a time...

Thanks!

Answer 1

Why don't you let the tiles store information about what objects occupy them. Then collisions can be detected whenever an object is moved to a new tile, by seeing if that tile already contains another object.

This would cost virtually nothing.