Keeping track of objects in a tilemap

It is easy to keep track of what tile of a tilemap tiny game objects are in. What is not as straight forward is how to sort larger objects objects into a tilemap such that each tile that contains part of them has a reference to the object – especially when the objects are moving and the tilemap has to be kept up to date.

Keeping object references in tiles

Tilemaps are one of the must useful spacial acceleration data structures in game development to the point where many classic and modern games rely partly or entirely on tilemaps for their game logic.

In some games, objects are always contained in exactly one tile. However, what if our objects can move freely and we simply use the tilemap as a quick-access structure?

Free moving objects that are not of zero width and height are always able to intersect multiple tiles, and will do so frequently while moving. If an object is in fact so large that it does not fit into a single tile, it will always intersect multiple.

To accelerate finding objects in a certain area, each tile intersecting the object needs to have a reference to it.

Let us develop an efficient algorithm for doing just that.

Naive implementation

Our first implementation is relatively easy:

Every time our object moves, we can remove it from all tiles that it was contained in, and then add it to all tiles it intersects after the movement.

For example, using pseudo code:

field position

updatePosition(newPosition)
{
    foreach(tile in this.intersectingTiles())
        tile.Remove(this)
    this.position = newPosition
    foreach(tile in this.intersectingTiles())
        tile.Add(this)
}

Simple enough.

But how do we determine the intersecting tiles? This is not very difficult either. We can simply determine the tiles that contain the top-left and bottom-right corners of our objects.

The rectangle of tiles spanned by those two points contains all the tiles our object intersects with (we are assuming our objects to be axis aligned rectangles here).

field position
field width
field height

intersectingTiles()
{
    topLeft = position - (width, height) / 2
    bottomRight = position + (width, height) / 2

    tileTL = coordinates of tile at topLeft
    tileBR = coordinates of tile at bottomRight

    for(y = tileTL.y to tileBR.y (inclusive))
        for(x = tileTL.x to tileBR.x (inclusive))
            yield tile at x, y
}

Optimising 1 – only update when we have to

The above algorithm works well. However, it does a lot of unnecessary work. Note how we have to find the list of intersecting tiles twice every time we run the algorithm, even though we could store the list of tiles – or to save space the rectangle of tiles after the movement for the next frame.

Once we keep track of that already, we can optimise further and only run the entire algorithm if the tile rectangle actually changed. For slow moving objects this will not be the case very often. They might only change their tile-intersection every few dozen frames. Skipping all the list manipulation for the majority of frames will give us significant performance improvements.

field position
field width
field height

field currentTileRectangle

updatePosition(newPosition)
{
    this.position = newPosition

    newRectangle = calculateCurrentTileRectangle()
    if(newRectangle == currentTileRectangle)
        return // nothing changed. done here.

    foreach(tile in this.intersectingTiles(this.currentTileRectangle))
        tile.Remove(this)
    foreach(tile in this.intersectingTiles(newRectangle))
        tile.Add(this)

    this.currentTileRectangle = newRectangle
}

calculateCurrentTileRectangle()
{
    topLeft = position - (width, height) / 2
    bottomRight = position + (width, height) / 2

    tileTL = coordinates of tile at topLeft
    tileBR = coordinates of tile at bottomRight

    return (tileTL, tileBR)
}

intersectingTiles(rectangle)
{
    (tileTL, tilleBR) = rectangle

    for(y = tileTL.y to tileBR.y (inclusive))
        for(x = tileTL.x to tileBR.x (inclusive))
            yield tile at x, y
}

Our code has gotten significantly longer with these improvements, however if we are dealing with many objects, the performance impact will justify this many-fold.

Optimising 2 – implementation details

When implementing the above algorithm, it is not unlikely that we may use linked lists to store the objects. If we keep track of the list nodes the object is using, it will allow us add and remove the object from tile-lists in constant time.

Further, it also allows us to make another optimisation: Since we are now keeping track of the linked list nodes, we no longer have to enumerate the old rectangle of intersecting tiles. Our nodes will know the list they belong to, so that we can simply remove the nodes from all their lists in a tight loop.

Since we are trying to be efficient, let us also reuse the linked-list nodes to not create unnecessary garbage collection pressure. As an object enters a tile from intersecting multiple, this may cause some of the nodes to remain unused, and in the opposite case we will have to ensure that we have enough nodes for all the intersecting tiles.

Those checks can be added easily however.

field position
field width
field height

field currentTileRectangle

field linkedListNodes

updatePosition(newPosition)
{
    this.position = newPosition

    newRectangle = calculateCurrentTileRectangle()
    if(newRectangle == currentTileRectangle)
        return // nothing changed. done here.

    this.currentTileRectangle = newRectangle

    removeFromAllTiles()
    ensureNodeCount(newRectangle.TileCount)
    addToAllTiles()
}

removeFromAllTiles()
{
    foreach(node in this.linkedListNodes)
        node.List.Remove(node)
}

addToAllTiles()
{
    i = 0;
    foreach(tile in this.currentTileRectangle)
        tile.Add(this.linkedListNodes[i])
        i++
}

Optimisation 3? – using a DIFF algorithm

There is one last optimisation that I can think off, however I am not convinced it is really worth it, since it is both difficult to implement, and uses more complicated logic that may offset other performance gains.

The idea here is to compare the old and new tile rectangles not only for equality, but for their overlap as well. All tiles that are contained in both the rectangles are tiles that the object was and will remain intersecting.

That means that we would not have to remove and re-add the object to that tile.

In principle this might speed up the algorithm significantly, especially for large objects that are contained in many tiles.

And while the pseudo code for this algorithm is relatively easy, the enumeration of all tiles contained in one, but not the other rectangle will be a mess of special cases that I am not willing to tackle here today.

Conclusion

I hope this has been an interesting overview of how to keep track of large objects in a tilemap.

If you think this post is useful, please share it on your favourite social media.

Next week we will flip things around and instead of putting objects into tilemaps, we will discuss how to efficiently retrieve those objects again.

Enjoy the pixels!

Leave a Reply