• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Advanced collision detection - lots of objects

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1Counciler  Members

Posted 20 April 2013 - 09:56 AM

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?

### #2Ludus  Members

Posted 20 April 2013 - 11:35 AM

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.

### #3LJ_1102  Members

Posted 20 April 2013 - 11:47 AM

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, 20 April 2013 - 11:47 AM.

Jan F. Scheurer - CEO @ Xe-Development

### #4Edvinas Kilbauskas  Members

Posted 20 April 2013 - 11:59 AM

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();
}

}



“There are thousands and thousands of people out there leading lives of quiet, screaming desperation, where they work long, hard hours at jobs they hate to enable them to buy things they don't need to impress people they don't like.”― Nigel Marsh

### #5AllEightUp  Moderators

Posted 20 April 2013 - 12:16 PM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

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, 20 April 2013 - 12:18 PM.

### #6serumas  Members

Posted 21 April 2013 - 09:09 AM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

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, 22 April 2013 - 03:27 AM.

### #7Edvinas Kilbauskas  Members

Posted 22 April 2013 - 06:55 AM

Sveiks,

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

I still need to learn many things

“There are thousands and thousands of people out there leading lives of quiet, screaming desperation, where they work long, hard hours at jobs they hate to enable them to buy things they don't need to impress people they don't like.”― Nigel Marsh

### #8serumas  Members

Posted 23 April 2013 - 03:51 AM

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, 23 April 2013 - 04:03 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.