Tag Archives for physics

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!

Angular type-safe physical units

Recently we have seen how we can create our own types to encapsulate physical concepts such as position, velocity, timespan and more. We developed all the types needed for movement in one and two dimensions, however so far we have not talked about rotation.

Today we will look at how to implement the types necessary to also gain the advantages of type-safety when it comes to the rotation and orientation of an object.

We will consider only the two dimensional case, since it is relatively straight forward. However, a similar approach could be taken in three dimensions as well, though it would significantly complicate the mathematics.

Continue reading →

Extending type-safe physical values to multiple dimensions

In this recent post we saw how we can represent the physical units of length, speed, acceleration, and time using our own types to only allow for type-safe operations between them, and find errors and bugs at compile time.

Today we will expand these ideas to more than one dimension, with the example of two dimensional types.

Continue reading →

Implementing type-safe position, velocity and acceleration types

As discussed in this post there are some potential advantages in representing physical quantities like position, velocity, and similar in a type-safe way.

Instead of using simple floating point types, we can write our own wrapper types that have semantic meanings like ‘length’, ‘speed’, or ‘time’ and only allow physically correct operations between them.

That is exactly what we will look into here. We will implement the basic types for such a system, and show what operations between them are relevant and well defined.

Continue reading →

Basic game physics – from Newton to code

While we my not often think about it, movement of objects is one of the key aspects of most video games. In any game that has any sort of characters, enemies or items interacting in a fictional – or real – world, these agents and objects have to move in order for anything to happen.

In most cases, we want these movements to appear natural, or at least believable and consistent. This allows the player to better put themselves in the feet of the protagonist, or avatar, as they can control their movements in an intuitive way – not having to think about each key press individually, but merely willing to move in a certain direction and letting muscle memory take over from there.

Continue reading →