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!

Leave a Reply