Using tilemaps as accelerating data structure

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

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);
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!

1. Petr says:

Hello, great article. Could you give me some hint, would you implement map in tree? I, currently, can’t (lack of knowledge) imagine how should I store array[x,y] in tree.

Also if I understand it correctly – if I want to built e.g. something like Transport Tycoon, then I should use tilemap (x,y) for map itself, but for keeping record of other objects (trains, cities, cars, factories) i should put a reference to tiles. So a tile has a list of references to objects on that current tile? And also vice versa all objects should have a reference to current tile where they are placed on?

• Paul Scharf says:

Glad you liked the article! I’m not quire sure what you mean with your first question though. What kind of tree are you talking about, and what exactly do you want to do with it?

Regarding your second paragraph: That is pretty much what I would do (and have done), yes. :)
It usually makes sense and is useful for an object to know where it is on the tilemap, so it should keep track of it’s current tile somehow. Inversely, it can be really useful to know what objects are in a certain tile (or in a range of tiles, for example, if an explosion has to affect all objects in a small area, you only have to loop over the objects in the affected tiles, not all objects in the world).

Hope that helps!

• Petr says:

First question was about transformation from an array of arrays into a tree data structure. If that is even possible. I can’t imagine how would I do that. But there is no need to answer this question (I am just curious) since I am going to try tile maps with references. It looks really good and makes sense.

I am also thinking about splitting references from tile map into two – dynamic objects and static objects. Since I want only dynamic (moving) objects being computed more often.

• Paul Scharf says:

The split into two lists, dynamic and static objects can make a lot of sense, yeah. It really depends on the game of course, but if you often are only interested in one of the two types of objects, that can definitely be worth the slight overhead of maintaining multiple collections.

About the tree: It’s certainly possible, though might take some work. Trees can be great data structures if the density of objects is highly variable. In an array you then get lots of empty cells, but in a tree you can just stop adding layers to it, if there are only very few objects in one of the tree-nodes.

Having a static (not-changing) tree is relatively easy. You can simply use a quad-tree, or kd-tree, splitting up the world more and more, each time checking how many objects are contained in each tree-node, and you stop the splitting when that number is small enough.

What is more difficult (though of course doable) is a tree that changes as objects move around in it. This requires constant recalculation, and splitting/merging of tree cells. It can be worth it, especially when dealing with objects that don’t move much/fast, but in general, I prefer the simplicity of a simple grid/array. For most games that is more than enough complexity.

But, I’m curious: What are you making that you need a tilemap for?
Just a small project for fun, or something bigger?
I’m always curious to see what other people are up to. :)

• Petr says:

Thanks. For now it is just for fun and for learning. I am trying to build Transport Tycoon by myself. It is nothing new. Just transportation.

Last two days I was thinking about how to implement railways and trains. I can say that it is not so simple as I thought.

My idea so far is using Graph for railway where vertexes are all stations and railway switches. Edges will be tracks represented by linked lists.

But the question I need to solve now is how to implement railway signals. I am thinking of some method in edges (linked list).