2
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Can there be more than one object in a cell? \$\endgroup\$ – d3dave May 6 '15 at 13:51
  • \$\begingroup\$ Yes there can, I'll edit that into the question \$\endgroup\$ – Liam May 6 '15 at 13:52
  • 2
    \$\begingroup\$ Then instead of checking neighboring cells, you should check all cells occupied by current object. Make sure an object occupies all cells needed to cover it's bounds \$\endgroup\$ – d3dave May 6 '15 at 13:54
  • \$\begingroup\$ Ah right right, that makes a lot of sense. I'll give that a go, thanks for the help! \$\endgroup\$ – Liam May 6 '15 at 13:58
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Thanks for such a thorough answer! Has given me a much better idea on how to implement objects being in more than one cell. \$\endgroup\$ – Liam May 8 '15 at 9:43
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for listing multiple approaches, I'm going to try the object's being in multiple cells. \$\endgroup\$ – Liam May 8 '15 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.