# Tilemaps: circular range queries

Tilemaps as an acceleration data structure are a great tool in game development, especially for 2D games or games with largely 2D logic. Today we will look at how to enumerate the list of tiles in a tilemap intersecting an arbitrary circle.

## Why do we care

To make the best use of tilemaps, we need query algorithms that allow us to return tiles in a given area of the tilemap, so we can deal with those tiles specifically, without having to look at other tiles.

These algorithms have to be efficient and correct, meaning that they should consider as few tiles as possible, and return exactly those we are interested in, all with the minimum amount of work.

If we store game objects in the tiles they are in, this will allow us to quickly access all objects in a certain area – and do so much more efficiently than having to loop over all game objects and check each.

## From square to circle

Recently, I wrote on how we can efficiently return all tiles intersecting an axis aligned rectangle.

The idea behind that algorithm was as follows:

1. Take opposite corners of the rectangle, and find the tiles they are in
2. Consider the rectangle of tiles, spanned by these two
3. Enumerate all those tiles in a simple nested for-loop

Baring some special cases and considerations, it was as simple as that.

We will take this as a starting point for our implementation today.

Given our circle that we want to intersect with our tilemap, we can trivially find the smallest axis aligned rectangle – and thus square – containing the circle.

We can use the algorithm from the other post to enumerate all tiles in that square.

The only thing left to do is check if each tile intersects with our circle, and if so, return it.

## Circle-Rectangle intersection

To check if a tile intersects our circle, we will check for intersection between the circle and the rectangle encompassing the tile.

I did some research and there are multiple approaches with different advantages and disadvantages for this check. The one I will explain here is the most efficient, but also the one giving us the least information. It will merely return whether the circle and rectangle intersect or not. Luckily that is all we care about here.

The idea behind this algorithm is to use the symmetry of the axis aligned rectangle. If we consider the center of the rectangle to be the center of the coordinate system, it is symmetrical along both axis.

That means that we can fold along both axis to map all quadrants onto a single one. If we also fold the circle into the same quadrant, we simplify the problem by only having to check for intersection in that single quadrant.

We can do this folding simply by taking the absolute value of our coordinates (after shifting our coordinate system to the center of the square).

Naturally, the coordinates of the center of the square will be (0, 0) after that shift, so we really only have to consider the vector between the centers of the two objects.

Another important fact is that the circle will intersect the rectangle if and only if the distance between the center of the circle and the closest point in the rectangle to it is smaller than the radius of the circle.

Due to taking the absolute value of that vector, we now only have to deal with a single quadrants, which allows us to determine this closest point in a relatively easy way.

We subtract the half-size of the rectangle (half its width and height) from the already positive absolute difference vector we determined earlier.

This is equivalent to another coordinate system shift, where we now align the origin with the closest of the rectangles corners to the circle.

If either of the coordinates of the circle’s center is now negative, that means that the circle’s center is on one of the four sides of the rectangle.

For example, if the circle’s center now has a negative x-coordinate, it’s x coordinate is between the left and right values of the rectangle. In that case, we only have to check the straight distance between the center and the top side of our rectangle. If that is less than the circle’s radius, they intersect. And the same check works of course for the y axis.

If the circle’s center coordinates are positive, the circle lies outside these areas where we can perform the simple distance check. However, this means that the closest point to the circle’s center on the rectangle is the rectangle’s corner, and testing those two for their distance can easily be done with Pythagoras’ theorem.

In fact, as it happens, we can combine both these checks into one by clipping the vector we just calculated to the positive range, and then calculating the length of that vector and comparing it against the radius of the circle.

This clearly works in the case where the vector was already positive, but it also works in the negative case, since we essentially throw out the affected coordinate by setting it to 0. The resulting check will simply check the remaining coordinate against the radius, which is exactly what we needed.

Throwing this all together, here is this method fully implemented:

``````private static bool rectIntersectsCircle(
Vector2 rectCenter, Vector2 rectHalfSize,
{
// shift coordinate system to rectangle center
var diff = rectCenter - circleCenter;
// fold circle into positive quadrant
var diffPositive = new Vector2(
Math.Abs(diff.X),
Math.Abs(diff.Y)
);
// shift coordinate system to rectangle corner
var closest = diffPositive - rectHalfSize;
// set negative coordinates to 0
// so they do not affect the check below
var closestPositive = new Vector2(
Math.Max(closest.X, 0),
Math.Max(closest.Y, 0)
);
// perform distance check
}
``````

Note that for simplicity – and efficiency – I already supply the parameters to their method in a preprocessed form. This allows us to re-use the squared radius, and half rectangle size when checking for intersections with multiple rectangles – or tiles in out case.

## Back to the tilemap

With this method, we can now check all our enumerated tiles, and return only those that actually intersect the circle.

Note however, that this is somewhat inefficient, since we will check a large number of tiles that are clearly inside the circle. We can do better.

Instead of checking all tiles, we can consider each row of the rectangle, and find the first and last tile that intersect the circle in each row. Once we know those, the tiles in between necessarily intersect the circle as well. This has to do with the convex nature of a circle. The proof is left to the reader.

Finding the first and last tile intersecting the circle is very easy as the following pseudo code shows.

``````foreach (row in tile rectangle)
{
xStart = row.firstIndex
xEnd = row.lastIndex

while(tile at (xStart, row.y) does not intersects circle)
xStart++;
while(tile at (xEnd, row.y) does not intersect circle)
xEnd--;

enumerate tiles from xStart to xEnd (including)
}
``````

An actual implementation is slightly more complicated, at least if it tries to be efficient and not constantly recalculate tile coordinates. You can see my final implementation on GitHub.

## Further possibilities for optimisation

The algorithm above is fairly efficient and checks only a few too many tiles for circles in the size ranges I am interested in (around 10-15 tiles across at most).

However, if we are dealing with much larger circles, or much smaller tiles, it may be a good idea to further optimise.

Note how the two loops finding the starting and ending tile of each row are linear search algorithms. As such, we can optimise them by using a more efficient one, like a binary search.

Additionally, we could start the search with a better estimate than the outside of the rectangle. For example the diagonal from the top most to the left most point of the circle would provide a much better approximation of the circle itself.

Or, we could even go as far and use trigonometric functions to calculate the actual intersection of the tilemap’s grid lines and the circle, and use these either as a starting point, or if we are careful as a complete solution.

These are all ideas for future posts however.

## Conclusion

In this post we saw how we can test circles and rectangles for intersection with each other, and used this to enumerate all tiles in a tilemap that intersect a given arbitrary circle.

Next time we will take a look at another kind of tilemap range query: finding all tiles intersecting an arbitrary ray.

Enjoy the pixels!

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

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

# Optimising animation based collision volumes

Last time we talked about how we can approximate objects with complex shapes using simpler ones for our game’s physics simulation.

Further, we saw how we can use an often already existing feature: a skeleton for animating sprites – or vertices of a 3d-mesh – to make our collision shapes change position, and even size, as our object deforms.

Today I want to look at how knowing about the behaviour of CPUs – and especially their caches and memory – we can use simple optimisations to implement collisions with such objects very efficiently.

# Roche Fusion Technical Recollection 3

In this third instalment of Twitter-powered reminiscence we will continue discussing more and more of the different systems I developed for Roche Fusion in the last few months of the game’s development.

We will focus mostly on their technical and graphical aspects, since that is my area of expertise, and the purpose of this series of posts.

# Roche Fusion Technical Recollection 2

Today we will continue our exploration of Roche Fusion’s development process that we started last week.

We will do so from a technical point of view, exploring some of the various systems I developed for the game. With my role as team-lead and graphics programmer, this mostly means that we will mostly be looking at graphical effects.

# Using arrays to speed up static tree traversal

Over the last two weeks I wrote about how to construct and query a string prefix-trie. We used the data structure to quickly find all strings with a given prefix, and to find the longest common prefix in that list.

Today we will take a look at how we can use arrays to improve performance even further. We will also take a closer look at the run-time of our algorithms from last week’s posts and show how our new approach is significantly better.

While we are looking at the example of a prefix-trie, the same method can be applied to any static tree.

# A discussion on matching string prefixes

Strings are an exceptionally flexible data type. They can be used to represent virtually any kind of data, or even behaviour – think of clear text script files.

With all this flexibility also come certain drawbacks however. Doing a lot of computations on or using strings can be very expensive – especially in languages like C#, where strings are immutable.

This is why especially in game development one has to find a balance between the use of strings, and more statically typed code. However, even if we optimise entirely for performance, there will always remain use cases for strings.

Today I want to look at one specific use case of strings: matching string prefixes.

# Converting between Structs and Byte Arrays

In object-oriented code bases, we tend to express most of not all of our data in highly semantic and contextual ways – that is, we use classes that contain both data and behaviour, and often even more information through inheritance, attributes, and more.

However, sometimes we need to extract the data contained in these types – for example for sending network messages, or saving to disk. In this post we will look into converting between structs and byte arrays, to make exactly this possible.

We will compare different ways of doing so, and analyse them for performance and easy of use.

# Accessing game objects by unique ids

Every game keeps its game object in one or more simple collections. These are used for enumerating the objects every frame to update and draw them.

If objects need to refer to each other, they can easily store a reference to another object, and access it directly. This becomes more difficult however, when we deal with a multiplayer environment. In that case, each game will have its own set of object references, which will never be the same.

That means that we need another way of identifying objects.

Further, we want this access to be fast. After all, a network server might send a client the message that a certain game object should be deleted. If we then need to iterate over all objects to find the correct one, we could easily bog down the performance of our game. Those CPU cycles could be spent much better on something else.

Lastly, whatever data structure we will design for this has to be able to respond appropriately to objects being deleted. See this post for a discussion of how this can be done for simple lists.