How to choose cell to put entity in in an uniform grid used for broad phase collision detection?

I'm trying to implement the broad phase of my collision detection algorithm. My game is an arcade game with lot of moving entities in an open space with relatively equivalent sizes.

Regarding the above specifications, i decided to use an uniform grid for space partitioning. The problem i have right know is how to efficiently choose in which cells an entity should be added. ATM i'm doing something like this:

``````for (int x = 0; x < gridSize; x++) {
for (int y = 0; y < gridSize; y++) {
GridCell cell = grid[x][y];
cell.clear(); //remove the previously added entities
for (int i = 0; i < entities.size(); i++) {
Entity e = entities.get(i);
if (cell.isEntityOverlap(e)) {
}
}
}
}
``````

The `isEntityOverlap` is a simple method i added my `GridCell` class.

``````public boolean isEntityOverlap(Shape s) {
return cellArea.intersects(s);
}
``````

Where `cellArea` is a Rectangle.

``````cellArea = new Rectangle(x, y, CollisionGrid.CELL_SIZE, CollisionGrid.CELL_SIZE);
``````

It works but it's damn slow. What would be a fast way to know all the cells an entity overlaps?

Note: by "it works" i mean, the entities are contained in the good cells over the time after movements etc.

-
Much better than my other answer would be to use an [octree][1] [1]: gamedev.stackexchange.com/questions/31448/… – Ken Nov 3 '12 at 0:34
As this question appears to be assuming only two dimensions, a quadtree would probably be more appropriate than an octree. But since the question does specify "uniform grid", I'm assuming that tree-based solutions are outside of scope anyway. :) – Trevor Powell Nov 3 '12 at 1:10
I decided to choose an uniform grid for space partitioning instead of quad tree due to the fact that the world the entities are acting is relatively open and the entities have very similar sizes. – nathan Nov 3 '12 at 9:25

pseudo-code:

``````ClearAllCells();
foreach(entity)
int minXCoord = floor(entity->GetPosition().x-entity->GetRadius()) / CollisionGrid.CELL_SIZE;
int minYCoord = floor(entity->GetPosition().y-entity->GetRadius()) / CollisionGrid.CELL_SIZE;
int maxXCoord = ceil(entity->GetPosition().x+entity->GetRadius()) / CollisionGrid.CELL_SIZE;
int maxYCoord = ceil(entity->GetPosition().y+entity->GetRadius()) / CollisionGrid.CELL_SIZE;
for ( int x = minXCoord; x <= maxXCoord; x++ )
for ( int y = minYCoord; y <= maxYCoord; y++ )
``````

Basically, instead of iterating over every entity for every grid square, checking if the entity is in that grid square, just iterate over every entity once, calculating what grid indices it intersects.

This approach works effectively for any size entity and any size cells.

-
@MarkusvonBroady why? An entity can move and be in the same cell, in this case, a collision test is needed. – nathan Nov 3 '12 at 22:28
@nathan hmm, yea, I don't know why I missed that. – Markus von Broady Nov 3 '12 at 22:54

Use cell coherence. Don't throw away all that good data from the previous frame.

Basically, most of the time, an entity will be in the same cell (or neighbor) as in the previous update.

Unless it moves really fast.

Some pseudocode... [EDIT] flaws in comments fixed

``````//assuming the cells have been pre-populated from the previous update
//pass one
for each cell
for each entity in the cell
if(cell fully overlaps entity){
do nothing
else{
if(cell does not intersect the entity){
remove entity from cell
}
foreach neighbor_cell//8 neighbor cells
// this method will add entity to the cell if they overlap
}
``````

The effectiveness of this approach is highly dependent on the relative sizes of cells and entities.

E.G. If you have 1000 cells and 1000 entities, your algorithm will require 1,000,000 rectangle overlap checks.

If you have 1000 cells and 1000 entities, then you have on average 1 entity per cell, so the first pass of my algoritm will require 1000 overlap checks. [not counting entities on boundaries].

-
-1 This algorithm isn't very fast, especially because you replaced simple maths of translating entity boundaries to cell coordinates to two groups of conditional checks, because you iterate over all cells, and because you assume an entity doesn't often change it's cell (while a good cell size is only a little larger than median entity size from my experience). 101 000 overlap checks for 1000 cells (50x20) is not impressive at all. – Markus von Broady Nov 3 '12 at 10:18
yes the my original had some flaws. I've tidied it up now, should be much faster. – Ken Nov 3 '12 at 10:43

The approach with the intersection check is right, however the way you are iterating over the entities/cells is very inefficient. Also you won't need to do the check every frame for every entity as only a few will move fast enough to cross multiple.

If you have a regular grid you can calculate the position in this grid by a simple division, then you just need to check that tile and the tiles around it, not every tile:

``````foreach(entity in entities)
{
tileX = entity.x/gridWidth;
tileY = entity.y/gridHeight;

entity.currentGrid.removeObject(entity);
entity.currentGrid = grid[tileX][tileY];
[etc ...]
}
``````

For calculating things less often while catching most errors from this you'll need to predict if the object will change the grid cell it is in soonly.

``````[... calculate distance object needs to go into the next cell ...]
if(speed > distance)
watchedObjects.pushBack(entity);
``````

The loop in which this is then processed in could look like this:

``````// Game loop
while(true)
{
[... do other game loop stuff ...]
foreach(entity in watchedObjects)
[... check if they have changed their position in the grid...]
if([... 0.25 seconds have passed since last time ...])
{
grid.clear();
watchedObjects.clear();
foreach(entity in entities)
{
[... recalculate the position of every object in the grid...]
[... check whether it is likely that the object will go over the border in the next 0.25 seconds ...]
}
}
[... do the actual collision detection ...]
[... do other game loop stuff ...]
}
``````
-
Were do the 0.25 and 0.1 seconds come from? :) – nathan Nov 3 '12 at 9:28
Also you check the cells located in x-1:y-1, x:y-1 and x+1:y+1, i don't get it. Assuming entity.x and entity.y represents the top left position of the entity, i would check the neighbor cells on the direct right, on the bottom and on the diagonal bottom right. e.g x+1:y, x+1:y+1 and x:y+1. – nathan Nov 3 '12 at 9:45
Oh sorry, of course both were meant to be 0.25, though either way you have to decide yourself how often you'll need to update the grid. That what I meant with etc., check all the surrounding tiles, I just didn't write all of them down. – API-Beast Nov 3 '12 at 12:45