Introduction

3D Programming Demos and Tutorials

Raycasting
by Simon Brown

Introduction
Raycasting is a relatively simple pseudo 3D technique, most notably seen in the id Software game 'Wolfenstein 3D'.

This is my own interpretation of Raycasting. The book "Black Art of 3D Game Programming" by Andre Lamothe had a brief one-paragraph description of the idea behind Raycasting, and from that I worked out this technique, so it's quite possible there are other and/or better ways.

How it's done
Basically you have a 2D block based map, in other words just a 2D array and a size for each block. You also have a direction which the viewer is facing and a field-of-view angle.

Raycasting works by projecting rays out from the viewer, one for each pixel the screen is wide, so in 640*480 you'll be projecting 640 rays. You extend these rays until they hit a block in your map and then use the distance between the viewers position and the point of impact to determine the height of the vertical line to draw on the screen. This is shown in figure 1.1-

Figure 1.1 - Raycasting. The red line represents the direction the viewer is facing. The arc from one green line to the other is the field-of-view angle. The dark lines are the rays.

And the result would look something like figure 1.2.

Figure 1.2 - Raycasting screenshot.

The ray angles
To work out the angle to project each ray at, start by dividing the field-of-view by your screen width. Then multiply this by the x value of the ray (the screen x position, so 0-639 in 640*480) and then subtract half of the field-of-view. Finally, add this angle to the direction the viewer is facing. So in code that would look like-

angle [n] = player_facing + ( ( n * ( FOV / 640.0f ) ) - ( FOV / 2.0f ) );

where angle[] is an array of 640 floats, and FOV is the field-of-view. It also makes sense to keep your angles in the 0-360 degree range. So a complete function to calculate all 640 ray angles would look like this-

void CalculateAngles ( void )
{
   for ( int i = 0; i < 640; i++ )
   {
      angle [i] = player_facing + ( ( i * ( FOV / 640.0f ) ) - ( FOV / 2.0f ) );

      if ( angle[i] < 0.0f )
         angle[i] += 360.0f;

      if ( angle[i] >= 360.0f )
         angle[i] -= 360.0f;
   }
}

Extending the rays
Now you need to extend your rays one by one and see if they intersect any blocks in your map. No complicated geometry here, just a little trigonometry and a trick that exploits having a block based map. Basically, you don't extend your rays in small quantities, you extend them by the size of a block, then check the map array to see if you've hit anything. The exception to this is the first time you extend each ray, when you extend it just far enough to get into the next block. This has to be done before you start extending the rays by the height/width of a block.

Lets say your blocks are 100*100. You have a big 2D array which is your map, and you have the position of the player which we will call player_x and player_y (say 419, 280). You also have the angle of the current ray. To work out which block of your map the player is in, which we will call map_x and map_y, obviously just divide player_x and player_y by 100, so the player is in block 4,2. Also you do the same thing after extending a ray - divide the current x, y position of the ray both by 100 and reference your map using the values you get to see if you hit anything (if not then keep extending the ray).

Getting every intersection
You have to keep two current x,y positions for each ray as you extend it. One for extending the ray by the height of a block, and one for extending by the width of a block. To put that in simpler terms, we are going to track two pairs of x,y values. For one set of x,y's we will be moving to consecutive vertical grid lines (shown below) until we hit something and for the other we will be moving to consecutive horizontal grid lines. Obviously the grid lines represent the edge of the blocks. If you don't do both you'll miss a lot of intersections and your end image will be a mess. This is shown in figure 1.3.

Figure 1.3 - Extending the rays. On the left, we extend the ray by the width of a block in x (in this case 100) and use trigonometry to calculate how much to extend it by in y. On the right, we extend the the ray by the height of a block in y (again 100) and use trigonometry to calculate how much to extend it by in x.

As you can see, the ray intersects the grid lines 5 times in all, and neither of these two methods alone would catch all five intersections, so we need both.

So in one case, you will be always changing x by 100 (block width) and using trig to work out how much to change y by (depending on the angle of the ray). And in the other case you change y by 100 (block height), and use trig to work out how much to change x by. This means, if you refer back to figure 1.1, you will know the exact x,y position every time the ray passes through a grid line and enters a new block. Most of the time, you will find that both methods intersect different blocks, giving you two different x,y values, in which case you use the closer point to the viewer.

Moving to the first grid-line
As I mentioned earlier, before you start extending your rays as described above you need to get them to the first grid line they intersect. If you just started adding the width/height of a block straight away, then the position you would be checking against would mostly be in the middle of a block, not at it's edge, so the distance to this point would be irrelevant, and your end image would be a total mess.

In the left hand diagram above, we extend the ray until it crosses the first vertical grid line (also the very first intersection). On the right we extend the ray until it crosses the first horizontal grid line (which is the second intersection). Calculating these two points is relatively simple. Take the picture on the left. First we have to work out whether the line is going left (ray angle between 180 and 360) or right (ray angle between 0 and 180).

If the ray is going left then we just multiply map_x by 100 and subtract a small amount. This works because when we earlier converted player_x to map_x (dividing by 100), the value was rounded down because map_x is of type int (it has to be so we can reference our map array with it). If we don't subtract some small amount, then we are still in the same map block (although at the far left hand edge), whereas we need to be over the grid line just into the next block. Remember we are going to use the new values, divide them by 100 and check our map with them, so the difference between 399.99 and 400 is the difference between checking the right block and the wrong one.

If the ray is going right then we multiply 1 + map_x by 100. Again it works for the same reasons.

So if player_x = 419 and player_y = 280, then map_x = 4 and map_y = 2. If the ray is going left then our first x point is ( 4 * 100 ) - 0.1 = 399.9, and if the ray was going right the x point would be 1 + 4 * 100 = 500. When we eventually divide these by 100 to check against our map, this will give 3 and 5, the blocks either side of the players block.

Next we have to work out the y value associated with this x value, and this is where the angle of the ray comes into play. We know the position of the player (player_x, player_y), we know the ray angle and we know the x position of the new point. If the ray is going left we can subtract 270 degrees from the angle and form a right angled triangle as shown in figure 1.4.

Figure 1.4 - Using trigonometry to calculate the y value where the ray crosses the vertical grid line for a ray traveling left.

We can then use Tangent to find the opposite. The adjacent will be equal to player_x minus our new x value. The formula for Tangent is-

Tan (angle) = Opposite / Adjacent

so, rearranging we get-

Opposite = Tan (angle) * Adjacent

Once we have the opposite we subtract it from player_y to find our y value.

If the ray is going right, we subtract 90 degrees from the angle, perform the same procedure, but this time we add the opposite to player_y to find our y value

Lets take stock
So what did that achieve? Well, the point wasn't to show the implementation, but the theory. I've shown how to move a ray over the first vertical grid line. The procedure for moving a ray over the first horizontal grid line is much the same. After you've moved your ray over the first vertical and horizontal grid line (remember you need to do both) then you can check the new x,y position for your ray against your map by dividing by the block width/height to get a map x,y. If that map block is empty then you go into a loop of extending the ray by the width/height of a block and checking the map. Again you are tracking two sets of x,y values. With one set you change x by the block width and use trigonometry to calculate the value to change y by. With the other you change y by the block height and use trigonometry to calculate the value to change x by.

The trigonometry here is practically identical to what I showed you above, but instead of needing to do player_x - new x value, to work out the adjacent, we already know that it's just the block width.

What's next?
So, you extend your ray until it hits something, and you should get two x,y values for where the ray has made contact. Remember, to see if the ray has hit anything, divide the current ray x,y position by the blocks width and height and plug it back into your map. How you setup your map is of course entirely up to you. You might have 0 represent an empty square and any non-zero value an index to the texture used on that block. Anyway, one of these contacts will be on a vertical grid line and the other will be on a horizontal grid line. Quite simply, you use the closer of the two points, since a contact represents the ray hitting a wall, and rays don't travel through walls.

To work out which point is closer you'll need to work out the distance from the players position to the new points. You also need these values when drawing the vertical line on your screen. To work out the distance, just use pythagorus. So-

Distance = sqrt ( (player_x - new_x) * (player_x - new_x) + (player_y - new_y) * (player_y - new_y) );

And you use the lower of the two distances to work out the height to draw your vertical line. So basically-

line height = some_number / distance

since you want distant walls to appear smaller. I use 360 for some_number but you can experiment to find a suitable value. The last step is to work out where the top and bottom of the vertical line should be based on it's height but that's trivial. Simply-

top_point = half_screen_height - ( line_height / 2);
bottom_point = half_screen_height + ( line_height / 2);

Texture Mapping
There's two obvious ways of texture mapping a vertical line, one is to use DirectDraw stretch blitting, which is extremely quick and easy, but requires hardware support. The other way is simply to use linear interpolation, in the same way you would draw a texture-mapped line in a polygon texture mapper. I'm not going to explain this here since you'll probably already know it, and it can be found in plenty of online tutorials. Since the texture coordinates are linear in screen space you don't need to compensate for perspective or anything, it's just your basic affine texture mapped line, just vertical instead of horizontal.

I do need to explain texture coordinates though. The v coordinate is taken care of by your texture mapped line function, or by DirectDraw, but you need to work out the u value. The u value is basically just how far along the face the ray hits, divided by the length of the face. So you have an x,y value for the point which turned out to be the closer of the two intersections. If it was on a vertical grid line, then you are interested in the y value and if it fell on a horizontal grid line then you are interested in the x value. You already have the map x,y position for the block the ray made contact with. You multiply this x,y by block_width and block_height (both 100 in our example) and subtract this from either x or y, and then divide by block width or block height. So-

u = ( new_x - ( new_map_x * block_width ) ) / block_width; // ray hit a horizontal grid line

or-

u = (new_y - ( new_map_y * block_height) ) / block_height; // ray hit a vertical grid line

and that will give you a u value between 0 and 1.

Fisheye distortion
Lastly, one thing to realize is that because we work out the distance from the players position to the point of contact on a wall, this means we get a distorted view. A wall in the centre of the screen will be taller than a wall at the side of the screen, as shown in figure 1.5 below.

Figure 1.5 - Fisheye distortion.

The distance from the player to the wall at the far left of the screen is greater than the distance from the player to the wall in the centre of the screen, so the wall appears smaller. The reason you don't get this fisheye effect with a traditional 'divide by z' polygon engine is that these engines only consider the distance in the z axis, not the 3D distance. So a polygon engine uses screen_x = global_x / global_z and not screen_x = global_x / distance so it works out the distance to a plane (z = 0 plane) and not to a point.

You might be surprised to find out that our eyes give roughly the same view for the same reasons. If you stand close to a long wall, facing it, more or less as shown in the screenshot above, and without turning your head or moving your eyes, examine the path the top of the wall is following, you will see that far to your left the top of the wall is heading upwards from left to right. Then look at the wall straight in front of you and you'll see the top of the wall is flat. Now look at the top of the wall to your right, and you'll see that's it's heading back down, exactly as shown above.

Removing the distortion
Of course, since your eyes already do this, you don't want the images on your computer screen to do it as well, so it's a distortion you'll want to get rid of. You could work out the distance to a parallel point on a plane perpendicular to the direction the player is facing. This is probably the best mathematical way to fix the problem. Another way is to work out the magnitude of the distortion and compensate for it.

For instance, looking at the wall above, your could take the height of the middle line (x=319), which is the non distorted line, and then divide the heights of all the other lines by this value. You do this when your program starts and store all these values in an array of 640 floats. Then once your program is running you divide each line height by the value in this table and the distortion will be gone. Simple, and you've even used your own engine to fix it. It might not be completely accurate though, and you would have to set up the map as above, with the camera totally square on to a wall and render a frame 'off-camera' to complete your table of values.

Yet another, and perhaps my favorite way to remove the distortion is to use trigonometry. Again, as above you will have an array of 640 floats and you pre-calculate the magnitude of the distortion. The way you do this is to use Cosine to work out how much further each ray has to travel to reach a theoretical perpendicular wall, compared with the middle line on the screen. We can work out the angle, the adjacent is whatever you want to make it (it doesn't matter since the distances are all proportional) so just use 1 to make the math's easier. So just use Cos to calculate the hypotenuse and divide it by the adjacent. Store the value in your array, and then for each ray, once you've worked out the line height, divide it by the appropriate value in the array. So in code that would look like-

for ( int i = 0; i < 640; i++ )
fish_factor[i] = cos ( ( i * (FOV / 640.0f) ) - ( FOV / 2.0f ) );

The only thing to watch out for here is that the Win32 function cos() takes angles in radians, so to make it work with this function the code needs changing to-

fish_factor[i] = cos ( 0.01745329251994 * ( ( i * (FOV / 640.0f) ) - ( FOV / 2.0f ) ) );

This is the code I use myself and it works flawlessly. By using a theoretical adjacent value of 1.0 we have removed the need for complicated code and unnecessary divisions.

In conclusion
Hopefully I've provided enough information here about the general technique for you to write your own working Raycasting engine, after all if I managed to get it working from just reading one paragraph, then you shouldn't have a problem with this amount of information. If you want to see my code in action you can download the demo (DDRaycasting.zip) from the main page.