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

Question

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)) {
                cell.add(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.

Answer 1

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++ )
      grid[x][y].add(entity);

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.

Answer 2

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
               check_add entity to neighbor cell 
               // 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].

Answer 3

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);
  grid[tileX][tileY].addObject(entity);
  entity.currentGrid = grid[tileX][tileY];
  if(entity.intersect(grid[tileX-1][tileY-1].shape)) grid[tileX][tileY].addOverlappingObject(entity);
  if(entity.intersect(grid[tileX][tileY-1].shape)) grid[tileX][tileY].addOverlappingObject(entity);
  [etc ...]
  if(entity.intersect(grid[tileX+1][tileY+1].shape)) grid[tileX][tileY].addOverlappingObject(entity);
}

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 ...]
}