This week, I decided to take a little breather from my current project, GameLad, and hack on something that I've been interested in for a long time now: raycasting.

I'll start with some history. Raycasting is not, by any means, a new technology. It's been around for a while, and was, perhaps most notably, used for the 1992 game Wolfenstein 3D.

Wolfenstein3D

In the days of early gaming, computers were too slow to render 3D graphics in realtime, and developers needed an alternative rendering technique. Thus, raycasting was born. The whole concept behind raycasting is the usage of screen rays to transform a 2D map into a pseudo 3D projection, with a few restrictions. These restrictions, however, result in a blazingly fast (and fun) rendering system.

It isn't exactly a simple technique, as it requires some knowledge of trigonometry, but compared to writing a full 3D renderer, implementing a raycaster is a piece of cake. I was able to get a basic prototype up and running in a couple of hours. For this reason, be aware that the following code could probably be optimized quite a bit. This is just a writeup on a prototype. I am a visual learner, so don't be scared off by all my diagrams: they are here to help.


The Map

The game world is represented in an array of integers. Certain numbers correspond to certain tile types.

const int MAP_WIDTH = 30;
const int MAP_HEIGHT = 30;

int map[MAP_WIDTH * MAP_HEIGHT] =
{
    2,2,2,2,2,2,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,3,1,1,1,1,1,3,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,
    5,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,3,1,1,0,1,1,3,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,
    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
};


The Player

There are only a few variables needed for the player: the position, the direction, and the camera plane.

Vector2D position(14.5, 20);
Vector2D direction(0, -1);
Vector2D cameraPlane(1, 0);

The diagram below shows the visual representation of these three variables, in the context of the raycaster.

Figure 1

As you can see, our player's projection triangle, or view, is constructed from two triangles. If we add two lines to the diagram, we can see these triangles clearly.

Figure 2

In this example, the cameraPlane and the direction both have the same length, which means that the projection triangle created is a right triangle, which gives us a field of view of 90 degrees. If you wanted a higher or lower field of view, you could mess with the cameraPlane. A larger value will give you a wider field of view, and a smaller value will give you a narrower field of view.

Now that we have all the information we need for our camera, we can actually start raycasting.


The Raycasting

This is where things can start to get a little bit complicated. Basically, for every vertical stripe (or x value) of the screen, we need to cast a ray, in the correct direction, originating from the player. As the ray is being cast, we check every tile boundary that we pass for a wall. If we hit a wall, we can calculate the height of the wall, and then render a vertical stripe for that part of the wall. This process gets repeated once for every ray we cast. The larger your horizontal resolution, the more rays will get cast, and the more detailed your view will be. However, large resolutions will slow down the renderer.

Let's look at a diagram that illustrates one ray being cast.

Figure 3

In this diagram, I've surrounded the player with wall tiles. The orange line you see is a ray being cast from the player. This ray is being cast at about 3/4ths of the screen width, so let's assume that we are currently on x = 480, if our screen has a width of 640.

First, we need to calculate the x coordinate of that vertical stripe. Easy, it's 480 right? Wrong! That's the screen space coordinate. In order to calculate our ray direction, we need the camera space coordinate of the vertical stripe. That can easily be retrieved through the following calculation:

double cameraX = 2 * (x / (double)width) - 1;

You can check this by substituting our values: 2 * (480 / 640) - 1 = 0.5. Since our total camera plane ranges from -1 to 1, this is the correct value, as it is 3/4ths of our screen.

Now that we have the correct, camera space, x coordinate, we can get the necessary vectors for our ray:

Vector2D rayPosition = position;
Vector2D rayDirection = direction + (cameraPlane * cameraX);

The rayPosition is simply our player position, and the direction is the players direction (the blue vector in the above diagrams) plus (cameraPlane * cameraX), which just gives us the offset we need. To continue our example above, this would calculate as ((1, 0) * 0.5) = (0.5, 0), which, if you check the diagrams, is the correct coordinate on the cameraPlane.

Now that we have the origin and direction of the ray, we can actually cast it. This is the most complicated part of the entire raycaster, as we have to employ an algorithm known as DDA (Digital Differential Analysis), which is an algorithm mostly used for drawing lines. Since our rays are just 2D lines, this will suit us nicely. If you are crafty, you can also try out different algorithm such as Brensenhams Line Algorithm. I might give that a try at some point.

In our case, we are using the DDA algorithm to "step" along our ray, through the map tiles. While the ray hasn't hit a tile, we "step" onto the next one, and check it. When we do hit a tile, we can render what that ray has seen, and move to the next ray.

We start by preparing the DDA algorithm. First, we need the distances between each X and Y side, along the current ray. This sounds complicated, but it is actually just a simple usage of the Pythagorean Theorem, a^2 + b^2 = c^2. In our case, a is the size of the tile, 1, b is the x direction of the ray divided by the y direction of the ray, and b2 is the y direction of the ray divided by the x direction of the ray. The diagram below illustrates this calculation.

Figure 4

In code, the above looks like the following:

double sideDistanceX = sqrt(1.0 + (rayDirection.GetY() * rayDirection.GetY() / (rayDirection.GetX() * rayDirection.GetX())));
double sideDistanceY = sqrt(1.0 + (rayDirection.GetX() * rayDirection.GetX() / (rayDirection.GetY() * rayDirection.GetY())));

Now we need to determine which direction to step, which is simple. If our ray is moving to the right, we step right, and if it is moving left, we step left. Similarly, if our ray is moving up, we step up, and if it is moving down, we step down. This is also where we calculate our nextSideDistance, which is illustrated in the diagram below.

Figure 5

The nextSideDistanceX and nextSideDistanceY variables are simply the distances from the current ray position to the next X side and the next Y side.

double nextSideDistanceX;
double nextSideDistanceY;

Vector2D stepDirection;

if (rayDirection.GetX() < 0)
{
    stepDirection.SetX(-1);
    nextSideDistanceX = (rayPosition.GetX() - mapPos.GetX()) * sideDistanceX;
}
else
{
    stepDirection.SetX(1);
    nextSideDistanceX = (mapPos.GetX() + 1.0 - rayPosition.GetX()) * sideDistanceX;
}

if (rayDirection.GetY() < 0)
{
    stepDirection.SetY(-1);
    nextSideDistanceY = (rayPosition.GetY() - mapPos.GetY()) * sideDistanceY;
}
else
{
    stepDirection.SetY(1);
    nextSideDistanceY = (mapPos.GetY() + 1.0 - rayPosition.GetY()) * sideDistanceY;
}

Now that everything is set up, we can actually perform the DDA. While we haven't hit any tiles yet, we continue to step through our map, following the ray. The diagram below illustrates this. The pink tiles represent map tiles that we have stepped through.

Figure 6

In order to figure out which direction to step, we just check which side is closer by comparing the nextSideDistance variables. Remember how we calculated the sideDistance not too long ago? Well, we use that here. Adding sideDistance to nextSideDistance will essentially move us onto the next side, so that we can check it for a tile. When we do hit a tile, we store the side that we hit in the side variable (0 for x, 1 for y), and set hit to true.

bool hit = false;
int side;

while (!hit)
{
    if (nextSideDistanceX < nextSideDistanceY)
    {
        nextSideDistanceX += sideDistanceX;
        mapPos.SetX(mapPos.GetX() + stepDirection.GetX());
        side = 0;
    }
    else
    {
        nextSideDistanceY += sideDistanceY;
        mapPos.SetY(mapPos.GetY() + stepDirection.GetY());
        side = 1;
    }

    int tile = GetTile(mapPos);
    if (tile > 0)
    {
        hit = true;
    }
}

Almost done. Now we calculate the distance to the hit point. However, instead of just calculating the distance from the ray origin, we have to calculate the distance perpendicular to the camera plane. This eliminates the fish-eye effect.

If an x side has been hit, mapPosition.GetX() - rayPosition.GetX() + (1 - stepDirection.GetX() / 2) is the number of squares that the ray has passed through in the x direction. Once we divide that through rayDirection.GetX(), then we will have the real, perpendicular distance, from the rays origin to the hit point. We do the same thing if a y side is hit.

double perpWallDistance;
if (side == 0)
{
    perpWallDistance = abs((mapPos.GetX() - position.GetX() + (1 - stepDirection.GetX()) / 2) / rayDirection.GetX());
}
else
{
    perpWallDistance = abs((mapPos.GetY() - position.GetY() + (1 - stepDirection.GetY()) / 2) / rayDirection.GetY());
}

Using the calculated distance, we can calculate the height of the line that has to be drawn on screen, simply by dividing it against the window height.

int lineHeight = abs((int)(height / perpWallDistance));

We want the walls to be drawn starting from the center of the screen, so we just calculate a start and an end point for the line.

int drawStart = (-lineHeight / 2) + (height / 2);
int drawEnd = (lineHeight / 2) + (height / 2); 

And, finally, the last step: Render! We just check here for the type of tile that we hit, in order to set the color. Also, if a y tile was hit, we make it a little bit darker, for a 3D effect. After drawing the line for this ray, this loop is over, and we can move to the next ray.

Color color;
int tile = GetTile(mapPos);
switch (tile)
{
    case 1:
        color = RED;
        break;
    case 2:
        color = GREEN;
        break;
    case 3:
        color = BLUE;
        break;
    case 4:
        color = WHITE;
        break;
    default:
        color = MAGENTA;
        break;
}

if (side == 1)
{
    color = Color(color.GetR() / 2, color.GetG() / 2, color.GetB() / 2);
}

DrawLine(Vector2D(x, drawStart), Vector2D(x, drawEnd), color);

As a finishing touch, I draw a "floor" under the scene by placing this at the very top of the ray loop:

DrawLine(Vector2D(x, height / 2), Vector2D(x, height), GRAY);

That is pretty much all these is too it. There is lots of room for improvement, and I am planning on implementing textures in the near future. Overall, it was a pretty fun experiment. I'm excited to see how much further I can take it.

Final

Also, it would seem that the raycasting post on lodev.org deserves a special mention. Without it, this project probably wouldn't have happened.

The full source code of the project is available on GitHub.