Using tilemaps as accelerating data structure

Datetime:2016-08-23 01:20:02          Topic: Data Structure           Share

While Tilemaps are a great way of storing level data for a variety of games, we can use them for much more than storing level geometry.

We can use tilemaps as an accelerating data structure for many other systems like physics and AI, by keeping track of what objects are contained within each tile of the tilemap.

Today, we will look into the different options for doing just that.

Accelerating data structures

When developing a game or simulation many different algorithms require access to lists of objects to interact with. Often, objects only want to interact with a small subset of objects, based on some sort of criteria.

Accelerating data structures allow us to get easier access to these sub-sets, without having to iterate all existing objects and filter them by our given criteria.

In many cases, especially for the simulation of physics, the filtering criterion is based on proximity: We are interested in all objects close to a certain point, since these are the only objects that have a chance of interacting with our primary object through collisions for example.

Note that everything below applies to non-physics algorithms as well. We will use physics merely as a convenient example that requires us to retrieve all objects within a certain area.

Data structure retrieval runtime

To make large scale physics simulations possible, a spacial acceleration data structure is critical . Without it, we have to test each physical object against each other one which results in O(n 2 ) simulation time.

However, if we are using an accelerating data structure, we can reduce that runtime to O(n * k * r) where k is the number of objects that our data structure returns (i.e. the objects close by) and r is the time it takes to retrieve each single of the k potential objects.

So, for example, in the case of our simple list of all objects, k = n since we have to enumerate all objects, and r = 1 since each enumeration step is constant work. So, as expected the formula returns O(n * n * 1) = O(n 2 ) .

Trees as accelerating data structures

Of course there are a number of different data structures we could use to accelerate our retrieval algorithm . Each of these tends to come with different trade-offs in terms of memory usage, lookup time ( r ) and possible accuracy (bounds on k ).

For example, a common data structure is the quad-tree, or oct-tree in three dimensions. Quad-trees split a large starting square into four smaller squares, and then recurse, splitting each square into smaller ones, until each square only contains a small number of objects. Oct-trees are similar, but split larger cubes into eight smaller ones.

Since each consecutive square is only half the size of the previous one, they decrease in size exponentially, and the lookup time r tends to be logarithmic in n: r = O(log n) .

There are also other structures based on trees, like the popular KD-tree, that behave similarly.

A great advantage of trees like this is that they take relatively little memory, scale well even for large numbers of objects, and provide very accurate results for queries . In terms of our runtime formula above, they are very good at keeping k as low as possible with the minor trade-off of a slightly higher r .

Overall, such trees will result in a runtime of O(n * k * log n) as per our formula above.

The cost of keeping data structures up to date

There is one problem with relatively complex data structures like trees however that we have not yet discussed: In a game environment we have to not only be able to access our subsets of objects quickly, but we also have to keep our accelerating data structures up to date to make this possible in the first place.

Many of our relevant objects may be moving around the game world, potentially at high speeds, so that we have to make sure our data structure is accurate every single frame .

While updating especially predictable data structures like quad-trees is not overly complex, each position update may result in up to O(log n) work – the amount of work it needs to remove and insert an object. That means that we we need to do an additional O(n * log n) work each frame. While this will not affect our overall runtime, it may still be significant when we are dealing with thousands of objects that we want to simulate in real time.

Direct access tables/tilemaps

This is what brings us to tilemaps. Their common implementation as a two dimensional array means that they are a direct access table. In other words, we can access any tile in constant time .

Thus, if we store the list of all contained objects for each tile, this means that in our runtime formula, r = 1 , since both the initial access of the tile, as well as each enumeration step takes constant time.

This seems like a clear advantage over trees as accelerating data structures.

However, the great disadvantage of direct access tables are collisions – unlike trees they can not adapt to many objects being very close to each other.

If we get a very tight grouping of objects, a tilemap will be forced to store these in just a few tiles, each of which will contain a possibly long list of objects. Trees on the other hand would simply split a few more times to make sure their leaf nodes only contain a few or a even a single element.

In terms of runtime this means that k will be larger when dealing with tilemaps.

However, in most games, objects will only be grouped together to a limited extend . By choosing a good size for the tilemap, we can put a very tight limit on k in most cases.

Further, updating the tilemap when an object moves can be done in constant time, as we will see below.

Tilemap as accelerating data structure

After this discussion of the advantages and disadvantages of different data structures, how do we actually keep track of what objects are in what tile?

Turns out we can go with a fairly straight forward approach: We simple keep a list inside each tile, and every time an object moves to a different tile, we remove it from one list and add it to the other .

Here is some pseudo code:

class Tile
{
    List Objects;
}

class Object
{
    Tile currentTile;

    OnUpdatePosition()
    {
        Tile newTile = Level.GetTileAt(this.position);
        if (newTile != this.currentTile)
        {
            this.currentTile.Objects.Remove(this);
            newTile.Objects.Add(this);
            this.cirrentTile = newTile;
        }
    }
}

The GetTileAt() call which returns the tile containing a specific point is a very simple method which only has to transform our world coordinates into tile coordinates and return the appropriate tile – logic like this should come with any tilemap implementation or can easily be implemented on top of it .

Choosing an object collection type

They key points we have to look at closer are the calls to Remove() and Add() . If we indeed keep a C#-List, backed by an array, inside each tile, then the removing call has to both look for our object inside that list, and then move all objects after it by one to fill the gap inside the list.

That means that moving from one tile to another is not constant time, but actually linear in the number of objects in the tile that we left.

However, there is a solution: Instead, we can use a linked list and keep around the node used to keep our object in the list. If we have both the list and the node, removing it comes down to updating a few references, which is constant time.

Note: While the theoretical runtime of using a linked list is better than that of an array backed one, in practice and with small numbers of objects, it might actually be significantly more efficient to use an array backed list. Enumerating linked lists can be significantly slower, and might easily overpower what we gain by not having to search through compress our lists on removal.

In both cases iteration will be linear in the number of objects in the list , which is as good as it gets, resulting in our overall query runtime of O(n * k * r) = O(n * k * 1) = O(n * k) which is as good as we could hope for. This will result in great performance as long as we are able to limit our k by choosing an appropriate tilemap size.

Limitations

Unfortunately, there are some caveats with the proposed solution. So far we have not actually looked at how to return objects inside a given range or area.

Further, all our objects currently can only be inside a single tile which is rather limiting and unrealistic when it comes to actual physical objects that take up space and could easily be intersecting multiple tiles.

These are important concerns which I will make sure to address in future posts.

If you have found this interesting and would like to see the follow up posts expanding on how to use tilemaps as accelerating data structure, make sure to share this post on your favourite social media.

Enjoy the pixels!





About List