Better collision detection method

Newbie & Debugging Questions
#1

Hi I am making a game with towers which fall down and land on top of eachother, and the only way to think of checking if one collided with another was:


for int i = 0; i < towers.size; i++)
{
    for int j = 0; j < towers.size; j++)
   {
       if (i == j) continue;
       if (tower[i] collides with tower[j])
       {
             DoSomeThing;
       }
   }
}

the collision works fine but I start to see the lag after only about 20-30 towers. I would like to have at least 150 towers being able to be on the screen at once without any significant slowdown as I have lots of other stuff in my game thats going to drain the cpu. Is there a much better way to do it? eg so that the tower doesnt check all the towers in the vector/array and only checks towers below it or something. Thanks

#2

This saves you half of the checks, but more importantly, is better:

for int i = 0; i < towers.size; i++) { for int j = 0; j < towers.size; j++) { if (i >= j) continue; // !!

To really reduce the amount of checks, use some spatial algortihm like a quadtree for 2D and a octtree for 3D

#3

or even:


for (int i = 0; i < numTowers; i ++) {
	for (int j = i + 1; j < numTowers; j ++) {
		// check here
	}
}

Cas :slight_smile:

#4

Doh :persecutioncomplex: :-X

I wrote it like that, because I sometimes have non-equal (subsets) ‘inner/outer loop’-collections, where I do:

for(Object a: ...) for(Object b: ...) if(a.hashCode() > b.hashCode()) // collide

Which is almost like comparing the pointer in C, as long as the hashCode is the identity hashcode

#5

System.identityHashCode( Object o ), for when your objects have overridden hashCode().

#6

I always wondered how System.identityHashCode worked… I can see that it could easily be intrinsified to just use the actual pointer to the object on the heap, except that all the modern garbage collection stuff since Hotspot has involved moving objects around, so that number would change. Or maybe it uses a pointer to the VM’s internal structure that points to the object? (Does such a structure even exist?)

Cas :slight_smile:

#7

Yes.

Split up your screen into a grid, for example a grid consisting of 32x32 tiles.

Each tile in the grid can contain references to multiple towers.

So if you’re dropping a tower on tile 12x14 (and maybe adjacent tiles) then you simply look up this tile in the grid and check if the tower collides with any other towers there.

This requires some modification to the datastructure of your game.

#8

I use a grid bast collision detection routine and it will be much faster. I have a 2D array of Sets of game objects (or of Towers in your case). It should be a set because a tower should only be stored in an array location once. You need to calculate the towers minimum and maximum x and y locations. Typically the minimum is their bottom left corner, and the maximum is the Towers top right corner.

You then divide the x values of these corners by the width of the array, and the y value by the height of the array. Then you iterate from the new minimum x and y through to the maximum x and y, adding the tower into the Set in each location in the array.

This is untested psudo code for adding a tower…


final int TOWER_GRID_WIDTH  = 20;
final int TOWER_GRID_HEIGHT = 20;
Set<Tower>[][] towerGrid = new Set<Tower>[TOWER_GRID_WIDTH][TOWER_GRID_HEIGHT];
    /* grid setup code here */

Tower tower = // get tower
int minX = Math.floor( (tower.getX()-tower.getWidth()/2) / TOWER_GRID_WIDTH );
int minY = Math.floor( (tower.getY()-tower.getHeight()/2) / TOWER_GRID_HEIGHT );
int maxX = Math.ceil( (tower.getX()+tower.getWidth()/2) / TOWER_GRID_WIDTH );
int maxY = Math.ceil( (tower.getY()+tower.getHeight()/2) / TOWER_GRID_HEIGHT );

for (int x = minX; i <= maxX; x++) {
    for (int y = minY; i <= maxY; y++) {
        towerGrid[x][y].put( tower );
    }
}

When a Tower’s size or location changes (i.e. moved or resized) then you need to remove it from all of it’s locations and then re-add it. There are then a range of optimizations you can run to make this more efficient (like checking if a Tower has moved from one grid space to another before removing/re-adding, and only updating when you check for collisions).

When you want to perform a collision check you just work out what array elements the Tower is in (like above) and then iterate over all the towers in each of those sets. Those are the towers to check against.

You should also try different grid sizes as they will yield different amounts of performance.

#9

WOW! thankyou everyone for all your comments!
I think I will look into doing a grid type thing as that seems the fastest.
thanks ;D

#10

Actually no, it isn’t. I’ve seen various benchmarks on collision detection routines and 2D grids are never at the top. For example oct-trees are faster. There is also a Wikipedia page on spatial partitioning that you can look at. But it is significantly faster then your original brute-force approach.

A 2D grid is also relatively easy and straight forward to implement.

A few more remarks; unless you build in some sort of system to deal with this then you can’t have Towers outside of the grid (i.e. offscreen). I also highly advise building an interface for your collision detection routine so you can easily implement a new algorithm. Also make sure you benchmark your algorithm (and it’s optimizations) with real data. Otherwise you don’t know if the optimizations help, or not. Also how will you deal with inheritance? Even if you choose not to you need to decide about what to do with this (i.e. everything is stored as a Tower).

A big issue for my own grid collision system was the high number of nodes and iterators used by the sets. I found when I had a thousand objects all constantly moving and intersecting against each other, it would be creating millions of objects per-second just to detect collisions. This caused the garbage collector to run ALOT and so I’ve since optimized it to remove this.

Finally there is a bug in my code above, dividing by the grid width and height is incorrect. It should be dividing by the width and height of each cell in the array in pixels, not the number of elements in the array. You can see my full grid collision code here. It’s not perfect, but for now it’s good enough.

#11

@Cas: A common method is to (maybe mix) the raw address and set a tag bit when an identity hash has been called on an object. When moved by GC, the object is again marked and the hash value is stored in an extra memory slot.

#12

thanks for the info, JL235.

I’m not worried about this really - I already thought about it. If the towers are above the grid then they are not going to collide with anything, just fall. And if they are left or right or below the grid they are off the map so I will delete them.

I will not iterate through anything except the towers. Check which grid piece it is in by it’s position and move it down one if there is no tower in the grid below. Otherwise if there is perform a collision detection between the two towers.

#13

Seriously, it depends. If you’re simulating liquids, then the particles are more or less evenly spread, and the grid approach will be running circles around any tree implementation.