10

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!

SadSido
  • 2,511
  • 22
  • 36

3 Answers3

9

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.

Sam Holder
  • 32,535
  • 13
  • 101
  • 181
Peladao
  • 4,036
  • 1
  • 23
  • 43
  • This is not bad, you can also run a A* on such maps. But notice that it can lead to bugs and other limitations, e.g. if you want more than one object on a tile or such things. It leads also to the restriction that all Objects must fit into a tile, otherwise it will becom complex to handle 2x1 tile obj. and such. – InsertNickHere Feb 04 '11 at 09:48
  • I'm unfamiliar with tilemaps, but if the tile can be larger than the area of intersection of two objects, wouldn't this be inaccurate? – atp Feb 04 '11 at 10:00
  • sounds good... anyway, object can occupy many tiles at one time, also it can occupy only part of a tile (objects, smaller than tile) – SadSido Feb 04 '11 at 10:26
  • btw, I should iterate over all tiles? To see if they share some objects? Objects move simultaneously, so one object is entering the tile and the other one is leaving this tile, how should I handle this? – SadSido Feb 04 '11 at 10:29
  • @SadSido Just handle it with the movement of objects. When an object wants to occupy a new tile, it should lock the tile object and then see if it is occupied by another object already. If yes, collission, if not, then add itself to tile and unlock tile, so other objects can try to occupy it. (When an object leaves a tile, it should of course remove itself from the tile object) – Peladao Feb 04 '11 at 10:33
  • I was thinking of splitting my level into areas (so called "rooms") and check collisions for objects inside rooms only. That will still be n^2, but n will be reduced, because there will be not so much objects in one room. And, only player will be allowed to move from one room to another, all the NPC will patrol in one room only... – SadSido Feb 04 '11 at 10:38
  • If you do it the way I suggest, nothing needs to be done O(n^2) and it wouldn't matter if there are separate rooms or not. Also it would just check colissions off screen without any extra cost. – Peladao Feb 04 '11 at 10:46
4

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

Matěj Zábský
  • 16,909
  • 15
  • 69
  • 114
  • 1
    Also note that the actual runtime overhead is fairly small until you get to many, many objects. The real issue is that it adds a lot of code complexity. If the objects are consistently sized near the size of the tiles, it's possible that Peladao's solution would work better for this case. – Walter Mundt Feb 04 '11 at 09:25
0

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.

tylerl
  • 30,197
  • 13
  • 80
  • 113