Tag Archives for collisions

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!

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 →

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.

Continue reading →

Animation based collision volumes

There is hardly a single game that does not need some form of collision between game objects. In many cases it is enough to approximate the shape of an object by a simpler one to simplify and speed up collision detection. It is for example very common – especially in 2D games – to use circles or boxes as colliding shapes.

Today I want to talk about how we can make use of collision code written for simple shapes like circles, and still end up with much more complex collision behaviour.

Continue reading →