Spatial Partitioning - Objects larger than cell?

Question

I'm developing a top down 2D tile based game. Recently I started working on collision detection and have gone down the route of simply using spatial partitioning.

Each object belongs in a cell and checks the neighbouring cells for collisions like this.

However, I realise I'm absolutely going to need to have some collision boxes that are bigger than a single cell.

Are there better algorithms for what I need or is there a simple work around I'm not seeing?

EDIT: multiple objects can be in a single cell at the same time.

Answer 1

The way I handle this is each cell has a list of entities which inhabit it and each entity has a list of cells / tiles it inhabits.

This way a cell can contain multiple entities and an entity can inhabit many cells.

Whenever an entity moves it checks for collisions with other entities which inhabit the cells it is moving through.

Once it has finalised its position it removes itself from any cell lists, clears it own list of cells.

Then for every cell it currently inhaibts it adds itself to that cells list and the cell to its own list.

private void updateInhabitedTiles(){
    removeFromMap();

    MapTile bottomLeft = inhabitedTileMap.mapToTile(
            position.x,
            position.y
    );

    MapTile topRight = inhabitedTileMap.mapToTile(
            position.x + dimensions.x,
            position.y + dimensions.y
    );

    for(int x = bottomLeft.xPos; x <= topRight.xPos; x++){
        for(int y = bottomLeft.yPos; y <= topRight.yPos; y++){
            MapTile inhabitedTile = inhabitedTileMap.getTile(x, y);
            inhabitedTile.addEntity(this);
            inhabitedTiles.add(inhabitedTile);
        }
    }
}


private void removeFromMap(){
    for(MapTile mapTile : inhabitedTiles){
        mapTile.removeEntity(this);
    }
    inhabitedTiles.clear();
}

When stress testing this I had approximately 9000 colliders before I noticed any slowdown and the cell / tile resolution was 16 pixels.

I used a LinkedHashSet for my lists of Tile Inhabitants (for cells) and Inhabited tiles (for entities).

Answer 2

With the spatial-binning approach, there's a couple of ways to manage cell-size vs object-size.

• Make the cells big enough, so that cell edge >= half the biggest object, and always check adjacent cells.
• Check more than 1 cell away. Radius 1 checks 9 cells, radius 2 would check 25 nearby cells, and so on.
• Put objects "into" more than one cell. When moving, you have to remove from stern-side and add to the bow-side of the motion. Or just always remove them all and re-add them.
• For non-moving objects (big walls) break them up into smaller pieces (same as "put into more than one cell," but extra easy if not moving).

I've been leaning towards "make cells big enough" for my current project.