Physical Queries for the Math Challenged: Ray Casting

Hopefully, you’ve read my previous article on setting up the basic grid data structure and performing collision detection. If not quickly go read the section on the grid since we’ll be leveraging that data structure to perform ray casting. Ray casting is a powerful and reasonably simple technique which can be used to answer several questions about the environment.

Last time we covered collision detection, but collision detection is only one type of physical query. For Forte I needed to answer additional questions such as: “Can I fire and hit the target?”, “Is there a wall in front of me?”, and “How far can I go in this direction?”. Answering these questions was the basis for the tanks AI. As luck would have it all of these questions can be answered with ray casting, and if we fudge things a little no complex math is needed.

High Level Overview

The basic idea of ray casting is simple. To answer the above questions you’re going to draw a line from the subject to the target. Then return whether or what the line intersects with. As you can probably imagine there are a number of ways to do this programmatically. My approach was to create a line object between the two bodies and then check each cell the line occupies for intersections. The heart of the algorithm, then, becomes figuring out how to traverse the correct set of cells. Fortunately, that’s what ray casting is all about. There are a lot of resources out there which cover ray casting. Unfortunately most of them are very confusing and hard to follow. I’ve singled out this one as being the best of the bunch, though it’s also confusing at times. Hopefully between that and this everything will be pie.

Ray Casting Algorithm

I think the easiest way to explain this algorithm is to step through the code with you, so here goes:

/* Return true if there are no walls between one and two. */
public boolean ray(Body one, Body two) {
    Collider collider = ColliderFactory.construct();
    Matcher walls = new RoleMatcher(Role.WALL, Role.TANK);
    Ray ray = new Ray(one, two);
    ...

Start off by creating some necessary objects. The collider is responsible for determining when two objects intersect. The matcher simply checks a flag on a body to determine whether a body has a certain role; in this case the algorithm will stop if a wall or tank is intersected. Finally, the ray object is a line object which extends from body One to body Two.

/* Current cell we're in on the grid. */
int currentX = (int) Math.floor(one.getCenterX() / cellWidth);
int currentY = (int) Math.floor(one.getCenterY() / cellHeight);
/* Target cell we're aiming for. */
int targetX = (int) Math.floor(two.getCenterX() / cellWidth);
int targetY = (int) Math.floor(two.getCenterY() / cellHeight);
...

Here we simply initialize some variables about where we are and where we’re heading in the grid.

Vector2f direction = ray.getDirection();
/* Distance from current position to next x, y side. */
float sideDistX, sideDistY;
/* Length of ray necessary to go from one cell to the next. */
float deltaDistX = (float) Math.sqrt(1 + (direction.y * direction.y)
        / (direction.x * direction.x));
float deltaDistY = (float) Math.sqrt(1 + (direction.x * direction.x)
        / (direction.y * direction.y));
...

Next we retrieve the direction vector from the ray. This is going to be a normalized vector which represents the dx/dy components of the ray. The first thing to do with this information is determine how far the ray extends in a given direction until it crosses into the next cell. I encourage you to check out first diagram in this section to see a fairly clear visual explanation of the above.

/* Direction to step in: 1 or -1. */
int stepX, stepY;
/* Calculate step and initial distance. */
if (direction.x < 0) {
    stepX = -1;
    sideDistX = (one.getCenterX() - (currentX * cellWidth)) * deltaDistX;
} else {
    stepX = 1;
    sideDistX = ((currentX + 1) * cellWidth - one.getCenterX()) * deltaDistX;
}
if (direction.y < 0) {
    stepY = -1;
    sideDistY = (one.getCenterY() - (currentY * cellHeight)) * deltaDistY;
} else {
    stepY = 1;
    sideDistY = ((currentY + 1) * cellHeight - one.getCenterY()) * deltaDistY;
}
...

After we calculate the direction and side distance we need to calculate which direction to step in. This is straightforward. The only gotcha is that you need to make sure that you adjust the side distance in proportion to the size of your cells. In my case that means multiplying the current cell by cell width or height. Many examples I’ve seen use unit cells in which case this step is hidden!

    boolean obstructed = false;
    while (!obstructed && !(currentX == targetX && currentY == targetY)) {
        if (sideDistX < sideDistY) {
            sideDistX += deltaDistX * 50;
            currentX += stepX;
        } else {
            sideDistY += deltaDistY * 50;
            currentY += stepY;
        }
            obstructed = collider.testForMatches(ray, 
                    cells[currentX][currentY].bodies, walls);
        }
    return !obstructed;
}

Finally, we have the main loop of the algorithm; Simply, we step through each cell adjusting our current position and distance to the next cell along the way. If the ray intersects with any bodies in the current cell then we exit. You’ll notice that I negate the result, this is simply cosmetic and all depends on how you want to use the ray method. That’s it!

Other Uses

In some cases you will not have a second body to construct a ray with. I’ve found that I can approximate things well enough by simply checking whether the cells are empty. Let’s take a look at another method to calculate the open distance in a given direction.

public float distance(Body one, float angle) {
    Vector2f direction = Geom.calculateVector(angle, cellWidth);

In this case I can’t construct a ray object so I calculate the direction vector based on the position of the first body and an angle. From here the algorithm follows the one outlined above with two exceptions. First, the loop exits if an examined cell is occupied (by anything). Second, I step once before entering the while loop. Since I know that there is a body in that cell I don’t want to confirm that and exit.

if (cells[currentX][currentY].size() > 0) {
    break;
}

After exiting the loop I calculate how far I’ve traversed and return the result. In this case I keep return the result squared to avoid the expensive square root operation.

float x = currentX - startX;
x = x * x;
float y = currentY - startY;
y = y * y;
return (x + y);

Simple right? Another modification I used in Forte was to return the first body in contact with the ray. This algorithm starts with the last one and then returns the first body in the cell instead of the distance traversed. This is useful if you want to determine whether to move towards, say, an ally tank or away from a wall.

Conclusion

At this point we have looked at three different algorithms. I hope it’s clearer now how ray casting can be implemented in your next game. There are some obvious limitations to our algorithms at the moment, but if you’re creative it should be possible to implement enemy AI which can navigate and respond to changes in your game environment! Of course, if you find any errors or have any suggestions please let me know below.

Further Work

Well we have a very simple system for querying physical space in place. This is enough if you want to create basic path finding and AI. Of course a developer’s work is never done so here are a few suggestions:

Add A* pathfinding on top of the grid.
Improve the collision detection to return additional information such as collision normal.
Improve ray casting by adding width to the ray — better for testing for projectiles.
Improve collision detection so that first contact and distance algorithms don’t have to be fudged.
Obviously performance could be improved throughout.

Found this post interesting? Consider sharing it: