Tag Archives for tilemap

Shooting rays through tilemaps

Casting/shooting rays is something needed in almost any game, be it to simulate bullets and other projectiles, particles, or to calculate whether two objects can see each other. Instead of testing all world objects against the ray, we can use a tilemap to only test against objects that are close to the ray in the first place.

For this we need to know all the tiles the ray travels through, and ideally in the order it travels through them, so that we can abort early in case of a collision.

This is exactly the algorithm we will implement here.

Note that this algorithm is by no means original. For example James MCNeill posted about it back in 2007. I hope that my spin on it will still be useful to people.

Determining the first and last tiles

The idea behind the algorithm is easy: we start with the tile that the ray starts in. From there we calculate the next horizontal and the next vertical intersection of the ray with the grid of the tilemap.

Depending on which is closer we know what step to take: a vertical intersection means we take a horizontal step, and vice versa.

Let us start with pseudo code and get some boiler plate code out of the way before we look at the heart of the algorithm.

First we will convert the coordinates of the ray to the coordinates of the tilemap, and get the locations of the starting and ending tile.

start = positionToTileSpace(ray.Start)
end = positionToTileSpace(ray.Start + ray.Vector)
diff = end - start; // we will need this later

startTile = tileAt(start)
endTile = tileAt(end)

By taking the Manhattan distance between these two, we know how many tiles we will have to iterate.

tileDifference = endTile - StartTile
tileCount = abs(tileDifference.X) + abs(tileDifferenceY) + 1

Knowing the total number of tiles, we can make an easy optimisation: If the tile count is 1, we simply return the starting tile, because the ray does not leave it. If it is 2, we can return the starting and end tile, and are done for the same reason. In fact, we can return the first tile in any case, since we will have to return it first no matter what.

yield return startTile

if (tileCount <= 2)
    if (tileCount == 2)
        yield return endTile
    yield break

I use the C# yield return/yield break syntax to indicate enumerating elements and stopping enumeration respectively.

The algorithm’s main loop

We are almost ready to look at the actual algorithm. One more thing we need to prepare is the sign/direction of the horizontal and vertical steps. We can do this easily by taking the sign of the tileDifference components we calculated above.

tileStepX = sign(tileDifference.X)
tileStepY = sign(tileDifference.Y)

Let us now jump around the code a bit. Since we know the number of tiles we are going to enumerate already, we can iterate them in a simple for loop. In fact, we iterate two less items in our loop, since we already returned the starting element and can return the end element in the end without having to calculate it.

// some more preparation here in a bit

for (i = 2 to count (exclusive))
    step to next tile
    yield return that tile

yield return end tile

// end of function

Taking steps

To be able to know which step to take with every iteration of our loop, we have to keep track of them. Instead of doing any math with actually calculating the intersection points and comparing distances, we can make use of the following facts to simplify the algorithm:

  • consecutive intersections of the ray with grid lines of the same direction are all at the same distance to each other, and
  • this is still true if we deal not with coordinates along the x and y axis, but instead work in a single dimensional space aligned to the ray.

Given this, we can calculate the intersections along the actual ray, where we define the starting point as 0, and the end point as 1 on our imaginary axis.

What we now need is to calculate the the step size for both kinds of grid-line intersections along that axis, and since we allow the ray to start with an arbitrary position, we have to also calculate the first intersection.

Calculating the step size is easy, since we merely have to transform each component of the difference vector to the new coordinate system. Since in that system, the vector is of length 1, we perform this transformation by dividing 1 by the difference vector components.

To calculate the first intersection, we can determine the position of the starting point within the starting tile on a scale from 0 to 1, which in the tile coordinate system is equivalent to taking the modulus of the starting coordinates with 1.

Note that the exact calculation is slightly different depending on whether the difference vector component is positive or negative (i.e. if the ray is shooting left or right, up or down).

Otherwise the calculation is the same for both x and y, so we can abstract it into its own function.

To make clear what values represent x or y coordinates, here is that functions written for the x case.

getIntersectParameters(startX, diffX)
    if (diffX == 0)
        intersectXStep = float.NaN
        nextIntersectX = float.PositiveInfinity
        return (intersectXStep, nextIntersectX)

    startXFraction = startX - floor(startX)
    if (diffX > 0)
        intersectXStep = 1 / diffX
        nextIntersectX = (1 - startXFraction) * intersectXStep
    else
        intersectXStep = -1 / diffX
        nextIntersectX = startXFraction * intersectXStep

    return (intersectXStep, nextIntersectX)

Note how I handle the case where the difference along this component is 0. While possibly rare, we have to make sure that we do not end up in some sort of infinite loop. By setting the next step intersection to infinity, the other step component will always have a smaller step, so that the loop always steps into the correct direction.

Putting it all together

With the method above in place, we can fully implemented the algorithm we indicated above.

tileX = startTile.X
tileY = startTile.Y

intersectXStep, nextIntersectX = getIntersectParameters(start.X, diff.X)
intersectYStep, nextIntersectY = getIntersectParameters(start.Y, diff.Y)

for (i = 2 to count (exclusive))
    if (nextIntersectX < nextIntersectY)
        tileX += tileStepX
        nextIntersectX += intersectXStep
    else
        tileY += tileStepY
        nextIntersectY += intersectYStep
    yield return (tileX, tileY)

yield return end tile

// end of function

And that is all!

If you are interested, feel free to take a look at my full implementation of this algorithm as part of my game Centipede, which is entirely open source on GitHub

Conclusion

In this post we developed an algorithm to efficiently determine all tiles intersecting a ray, iterating them in the correct order, and one at a time, which allows for early determination, if for example a collision is detected.

If this has been interesting or useful for you, make sure to share the post on your favourite social media.

And of course feel free to ask any questions or give any feedback in the comments below.

Enjoy the pixels!

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 →

Taking steps and other useful tilemap helpers

Tilemaps can be a great way to keep track of our game world. While a simple array of tile data at their core, they can be much more than that. Today I will look into the concept of directions in a tilemap, how we can perform local steps between tiles easily, and what more we can do once we are that far.

Continue reading →