# Advanced collision detection - lots of objects

## Recommended Posts

Counciler    105
Okay, so right now, I have a character, and he just simply checks against everything that is on the screen. It works fine, but I'm reading a book on collision detection and it talks about a way to handle many more objects on the screen. It suggests creating sectors and only checking against objects that are in the same sectors. The book then proceeds to give a working example of collision detection, but doesn't seem to follow it's own method of creating the sectors. So my problem is with creating these sectors. The book says that doing this method can decrease the checks by half or more, depending on how many objects are being checked against however many objects. It gives numbers as an example of how many checks you can save. But what confuses me is the book counts putting an object into a sector as only one check. The only way I can think of to create these sectors is to create an array of rects to keep track of where each sector is, then checking each index of the array until it finds the appropriate sector that each object is in. But assuming there's 24 sectors, and 12 objects on the screen, that would mean 12 objects will check up to 24 times each, and therefore it would be more efficient to just check against the 12 objects directly. So how does a person put an object into a sector with only one check?

##### Share on other sites
Ludus    1020

The only way I can think of to create these sectors is to create an array of rects to keep track of where each sector is, then checking each index of the array until it finds the appropriate sector that each object is in.

The sectors would be stored in a static array corresponding to its position on the map. By having all of the sectors the same size, you can calculate which sector an object is in simply by knowing the position of the object and the fixed size of a sector.

##### Share on other sites
LJ_1102    1233

Actually you'll have multiple objects inside one "sector" so when you can discard a sector you can already discard all objects inside it without checking them.

Typically you create some kind of tree hierarchy like a quadtree, octree, kdtree to do these things.

Edited by LJ_1102

##### Share on other sites
Pufixas    1167

I don't know if it will help you, but this is my class for hash grid which I use in my game.

public class HashGrid {

/*
* allGameObjects variable is used to store same objects as an gridObjects arraylist, execpt it is all in one place,
* and it is faster to return it, than adding all lists from gridObjects, and then returning them.
*/
private ArrayList<GameObject> allGameObjects;
private ArrayList<GameObject> nearObjects;

private ArrayList< ArrayList< ArrayList< GameObject> > > gridObjects; // two-dimentional ArrayList of ArrayList<GameObject>

private ArrayList<Id> currentIds;
private Rectangle [][] gridBounds;
private int gridSizeX, gridSizeY;

class Id{
public int x;
public int y;

public Id(int x, int y){
this.x = x;
this.y = y;
}
}

public HashGrid(float worldWidth, float worldHeight, float squareWidth, float squareHeight){
this.gridSizeX = (int) Math.ceil(worldWidth/squareWidth);
this.gridSizeY = (int) Math.ceil(worldHeight/squareHeight);

gridObjects = new ArrayList< ArrayList< ArrayList<GameObject> > >();

for(int x = 0; x < gridSizeX; x++){
for(int y = 0; y < gridSizeY; y++){
}
}

currentIds = new ArrayList<Id>();
gridBounds = new Rectangle[gridSizeX][gridSizeY];
allGameObjects = new ArrayList<GameObject>();
nearObjects = new ArrayList<GameObject>();

for(int i = 0; i < gridSizeX; i++){
for(int j = 0; j < gridSizeY; j++){
gridBounds[i][j] = new Rectangle(i*squareWidth,j*squareHeight,squareWidth,squareHeight);
}
}
}

public ArrayList<GameObject> getNearObjects(Rectangle bounds){
nearObjects.clear();

setTouchedSquaresIds(bounds);
int size = currentIds.size();

for(int i = 0; i < size; i++){
Id id = currentIds.get(i);
}

return nearObjects;
}

/**
*
* @param obj Game object to test with
*
* @return which grid squares the object is touching
*/
private void setTouchedSquaresIds(Rectangle bounds){
currentIds.clear();

for(int x = 0; x < gridSizeX; x++){
for(int y = 0; y < gridSizeY; y++){
if(CollisionTester.rectsCollided(gridBounds[x][y], bounds)){
}
}
}
}

public ArrayList<GameObject> getAllObjects(){
return allGameObjects;
}

/**
* Adds game object to hashgrid
*
* @param obj
*/
for(int x = 0; x < gridSizeX; x++){
for(int y = 0; y < gridSizeY; y++){
if(CollisionTester.rectsCollided(gridBounds[x][y], obj.bounds)){
}
}
}

}

/**
* Removes all instances of speicifed object
*
* @param obj
*/
public void remove(GameObject obj){

for(int x = 0; x < gridSizeX; x++){
for(int y = 0; y < gridSizeY; y++){
gridObjects.get(x).get(y).remove(obj);
}
}

allGameObjects.remove(obj);
}

/**
* Only clears GameObjects.
*
*/
public void clear(){
for(int x = 0; x < gridSizeX; x++){
for(int y = 0; y < gridSizeY; y++){
gridObjects.get(x).get(y).clear();
}
}
allGameObjects.clear();
}

}



##### Share on other sites
Hiwas    5807

Not a bad reduction for a simple method of regrouping the data.  (NOTE: May have messed up the general descriptions, but it should be fairly close to correct I believe.)

More complicated solutions exist and can get better gains. But, as said, they are more complicated.  I did a system which sat on top of my sweep and prune implementation which did a very nice job (used for something not directly related to reducing interactions since I already had that in the sweep and prune).  But it was a considerable bugger to write and debug.  You probably want to stick to the simple suggestions.

Edited by AllEightUp

##### Share on other sites
serumas    796

Something wrong with your calculations  bruteforce of n objects will be n*(n-1)/2  12*11/2=66. ==  11+10+...+1=66

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

And if you want even to speedup your grid , you can use sweap and prune inside each cell.

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function

Edited by serumas

##### Share on other sites
Pufixas    1167

Sveiks,

I think its a simle grid implementation becouse there is no hash function

I still need to learn many things :)

##### Share on other sites
serumas    796

All found grid implementations I found, even in book are damw far away from perfectness

After lots of optimizations and experiments I found routine that works finiest and its stil on optimizations

but main loop would look like this:

loop
{

//objects update
for(all objects)  //dead,alive, and waiting to be inserted in game world
{
if(obj.mut_insert())obj.set_acative();
if(obj.active)
{
obj.move_object();
obj.find_bounding_box();
bool update = obj.find_out_does_it_needs_to_be_updated_in_grid(); //not accessing grid data, maybe tricky or very easy, it depends
if(update)
{
obj.update_id++;
}
}
}
//grid update and collisions
for(all cells in grid)
{
for(all objects in cell)
{
if(cell_obj->obj->update_id!=cell_obj->update_id)delete cell_obj; //delete all elements with old id's

}
sort_cell_objects_by_box_left_up_corner_x(cell);
do_collision_like_sweep_and_prune(cell);//with some tricks its easy to avoid dublicate checks so we dont need to check neighbur cells so even object size differences do not mater
}

}


So its main simple main loop.

Some of optimization could be done for example:

do cell objects delete sort and check for collision in one loop  (possible allmost done)

find bounding box without resuming all object vectors (done with only 2 vectors)

object insertation could be done in grid.collision routine() becouse on insert you must check if it lands on free space

Edited by serumas