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