Avoid O(n^2) complexity for collision detection

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 c开发者_StackOverflowollision 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!

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.

You can use quadtree to divide the space and reduce the number of objects you need to check for collision.

See this article - Quadtree demonstration.

And perhaps this - Collision Detection in Two Dimensions.

Or this - Quadtree (source included)

It may seem - at first glance - that it takes a lot of CPU power to maintain the tree, but it also reduces the number of checks significantly (see the demonstration in th first link).

Your game already has the concept of a gameplay-related tilemap. You can either co-opt this tilemap for collision detection, or overlay a secondary grid over your playing field used specifically for sprite tracking and collision detection.

Within your grid, each sprite occupies one or more tiles. The sprite knows which tiles it occupies, and the tiles know which sprites occupy it. When a sprite moves, you only need to check for collisions within the tiles that the sprite occupies. This means no collision detection is necessary at all unless sprites are close enought to occupy the same tiles, and even then, you only need to check for collisions between the sprites that are close together.

If your gameplay is such that sprites will frequently clump together, you may want to implement your grid as a quadtree to allow each tile to be subdivided and prevent too many sprites from occupying the same grid tile.

Also, depending on your implementation, you may need to use a slightly larger bounding box to determine tile occupancy than you use to determine collisions. That way you'll be guaranteed that the sprites will overlap and occupy the same tile before their collision boundaries touch.