Tag Archives for data structures

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,
    Vector2 circleCenter, float circleRadiusSquared)
{
    // 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
    return closestPositive.LengthSquared <= circleRadiusSquared;
}

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.

If this has been interesting or useful to you, please share this post on your favourite social media.

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.

Continue reading →

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.

Continue reading →

LINQ: merging collections with Concat, Zip, and Join

Continuing my series of posts on LINQ, today I want to write about a few of the LINQ extension methods that take multiple input collections and return a single one.

Specifically, I want to take a look at the following methods: Concat(), Zip() and Join(). These all take two input collections, and combine their elements into a single resulting collection in different ways.

Continue reading →

LINQ: from IEnumerable to concrete collections

I my recent posts introducing LINQ from a game developers point of view, I mentioned several times how the many LINQ methods returning sequences of the IEnumerable<T> type do not actually return an actual collection.

Instead they return a query that can be executed any number of time on the given input collection.

Of course, there comes a point at which we need to store the results of such queries as regular collections. Today we will talk about how LINQ supports this almost trivially.

Continue reading →

Sorting and Grouping – organizing data with LINQ

Last week I introduced LINQ from the perspective of a C# game developer completely unfamiliar with the framework. Today I would like to continue exploration of LINQ by focussing on a particular set of its functionality: methods to arrange and organize data.

In particular we will look into how we can sort and group our collections of items.

Continue reading →

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.

Continue reading →

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.

Continue reading →