Raycaster Game Engine

Introduction

3D graphics are hard and resource intensive, at least they were back in the 90s. While playing the 1993 Doom one day, I got curious about the history of first-person shooters.

The first first-person shooter is said to be Wolfenstein 3D by id Software. The game is not really 3D, as the name suggests; the world is 2D. By raycasting, the game engine is able to render a 3D-looking scene.

Screenshot from Wolfenstein 3D

Raycasting is closely related to ray-tracing. In fact, both work on the same fundamental principle: rays of “light” are shot inside of the player’s field of view and the image is created based on what they hit. In raycasting, we cast in a 2D plane and use the distance of the hit to render rectangles of varying heights.

In this blog post, we will build our very own software-rendered raycasting game engine using C, OpenGL and GLFW.

Project Setup

First, install the GLFW library and ensure you can link to it.

Add Math, OpenGL, OpenGL Utilties, and GLFW to your linker command.

-lm -lGL -lGLU -lglfw

New Window

We need to create a window for our game. GLFW does the heavy lifting. All we need to do is to call its functions.

#include <GLFW/glfw3.h>

#define SCREEN_WIDTH 800.0f
#define SCREEN_HEIGHT 600.0f

int main() {
    glfwInit();

    // Create a new window: width, height, window title
    GLFWwindow *win = glfwCreateWindow(SCREEN_WIDTH, SCREEN_HEIGHT, "rc", NULL, NULL);
    glfwMakeContextCurrent(win);

    // Exit program
    glfwDestroyWindow(win);
    glfwTerminate();
    return 0;
}

A window should pop up but instantly close. To fix that, we need to add a loop. Inside the loop, we’ll tell GLFW to draw our frame to the screen by swapping buffers and poll events to handle user input.

    GLFWwindow *win = glfwCreateWindow(SCREEN_WIDTH, SCREEN_HEIGHT, "rc", NULL, NULL);
    glfwMakeContextCurrent(win);

+   // GLFW loop
+   while (!glfwWindowShouldClose(win)) {
+       glfwSwapBuffers(win);
+       glfwPollEvents();
+   }
+
    // Exit program
    glfwDestroyWindow(win);
    glfwTerminate();
    return 0;

Now our window is open until we manually close out of it.

Our GLFW Window

2D

Before drawing a 3D perspective, we will need to create a 2D game. In this section, we will define our game world and add a controllable player, that we can see at a bird’s eye view.

Game World

Let’s add a 2D array of 1s and 0s in the global scope. The world will consist of square cells, occupied by either a wall or not. I will add walls on each side as a world boundary and a small triangle shape in the middle.

#define WORLD_X 10
#define WORLD_Y 10

int world[WORLD_X][WORLD_Y] = {
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
};

To draw anything, we need to setup OpenGL to draw in 2D. While at it, I’m also going to change the background color to a more pleasant gray color.

    glfwMakeContextCurrent(win);

+   // Setup screen
+   glClearColor(0.3, 0.3, 0.3, 0);
+   gluOrtho2D(0, SCREEN_WIDTH, SCREEN_HEIGHT, 0);
+
    // GLFW loop
    while (!glfwWindowShouldClose(win)) {

Include the OpenGL libraries to get rid of errors.

#include <GL/gl.h>
#include <GL/glu.h>

We are ready to draw the world now. Make a function draw_2d. Each cell will be 32 by 32 pixels. Also, we need to pick colors for the cells - let walls be yellow and blank spaces be green.

void draw_2d() {
    for (int x = 0; x < WORLD_X; x++) {
        // Make each edge 32 pixels long 
        int screen_x = x * 32;

        for (int y = 0; y < WORLD_Y; y++) {
            int screen_y = y * 32;

            // Set color to draw with
            if (world[x][y] == 1) {
                // Yellow for walls
                glColor3f(0.7f, 0.7f, 0.0f);
            } else {
                // Green for air
                glColor3f(0.0f, 0.7f, 0.0f);
            }

            // Draw a rectangle
            glBegin(GL_QUADS);
            glVertex2i(screen_x, screen_y);
            glVertex2i(screen_x, screen_y + 32);
            glVertex2i(screen_x + 32, screen_y + 32);
            glVertex2i(screen_x + 32, screen_y);
            glEnd();
        }
    }
}

Finally, add the function to the render loop, and we should see the world get rendered to screen. The background did not change, because we also need to clear the screen before drawing again. Add a call to glClear at the start of the loop.

    while (!glfwWindowShouldClose(win)) {
+       glClear(GL_COLOR_BUFFER_BIT);
+       draw_2d();

        glfwSwapBuffers(win);
        glfwPollEvents();
    }

2D Representation

Adding a Player

The player will double as a camera for raycasting, so we need to a define coordinates, as well as an view angle. (5.0, 5.0) should be the center of the map, which is a reasonable spawn point.

    gluOrtho2D(0, 800, 600, 0);

+   // Player
+   float player_x = 5.0f;
+   float player_y = 5.0f;
+   float view_angle = 0.0f;
+
    // GLFW loop

We will define a draw_player function to show ourselves on our 2D world represented by a 1 cell wide square.

void draw_player(float x, float y, float angle) {
    // Set diameter for player circle
    glPointSize(16);

    // Draw player
    glColor3f(1.0f, 0.0f, 0.0f);
    glBegin(GL_POINTS);
    glVertex2f(x  * 32, y * 32);
    glEnd();
}

It would also be useful to know where the player is facing. Let’s draw a ray in the direction of the view angle. Make sure to add this before the player is drawn, so that the ray does not draw over the player square. To calculate the ray coordinate we will need trigonometic functions, so make sure to #include <math.h>.

void draw_player(float x, float y, float angle) {
+   // Set line width
+   glLineWidth(4);
+
+   // Draw direction ray
+   glColor3f(1.0f, 1.0f, 1.0f);
+   glBegin(GL_LINES);
+   glVertex2f(x * 32, y * 32);
+   glVertex2f((x + cosf(angle)) * 32, (y + sinf(angle)) * 32);
+   glEnd();
+
    // Set diameter for player circle
    glPointSize(16);

Player with a Direction Ray

Finally, we need to be able to control our player. GLFW’s documentation has a good article on user input, so I won’t spend much time going over it here. Here’s a simple implementation of WASD movement which respects view direciton.

void handle_movement(GLFWwindow *win, float *x, float *y, float angle) {
    int w = glfwGetKey(win, GLFW_KEY_W);
    int a = glfwGetKey(win, GLFW_KEY_A);
    int s = glfwGetKey(win, GLFW_KEY_S);
    int d = glfwGetKey(win, GLFW_KEY_D);

    // Forwards, 0 degrees
    if (w && !s) {
        *x += MOVE_SPEED * cosf(angle);
        *y += MOVE_SPEED * sinf(angle);
    }

    // Backwards, 180 degrees
    if (!w && s) {
        *x += MOVE_SPEED * cosf(angle + M_PI);
        *y += MOVE_SPEED * sinf(angle + M_PI);
    }

    // 'y' coordinates are flipped from what you would expect them to be
    // Left, 270 degrees
    if (a && !d) {
        *x += MOVE_SPEED * cosf(angle + 3.0f * M_PI / 2.0f);
        *y += MOVE_SPEED * sinf(angle + 3.0f * M_PI / 2.0f);
    }

    // Right, 90 degrees
    if (!a && d) {
        *x += MOVE_SPEED * cosf(angle + M_PI / 2.0f);
        *y += MOVE_SPEED * sinf(angle + M_PI / 2.0f);
    }
}

Changing the view angle is similar. I will use Q and E for turning the camera. OpenGL’s coordinate system starts in the top right, so the y-axis is flipped to what is conventionally used. A side effect of this is that clockwise and counter-clockwise are flipped, so we have to be careful.

void handle_turning(GLFWwindow *win, float *angle) {
    int q = glfwGetKey(win, GLFW_KEY_Q);
    int e = glfwGetKey(win, GLFW_KEY_E);

    // Turn left (counter-clockwise)
    if (q && !e) {
        *angle -= TURN_SPEED;
    }

    // Turn right (clockwise)
    if (!q && e) {
        *angle += TURN_SPEED;
    }
    
    // Fix angle to be in range
    *angle = wrap_angle(*angle);
}

One issue with working with angles is that things get weird when the angle is outside the standard [0, 2π] range. Normally we would use the modulo operator for this, but since we can have negative inputs we have to implement it ourselves:

float wrap_angle(float in) {
    return in - 2 * M_PI * floorf(in / (2 * M_PI));
}

Add the macros for move and turn speed at the top and call the handle functions from the loop. And that’s about it for the 2D! We have a world and a controllable player, meaning we can now start raycasting.

Raycasting

It’s time to add raycasting. In this part, we will implement a raycasting algorithm and use it to draw the screen.

Wrapper Function

When we cast a ray, we want to trace its path until it hits a solid object. This means we need to every time the ray crosses a cell boundary, we must check whether the ray hit a solid cell.

Raycast Theory

In practice, it’s easier to split this logic into a horizontal and a vertical trace. We can increase the ray’s position in one direction to the next whole number, while calculating the change in the other direction using trigonometry. Once we do a horizontal and a vertical trace, we will choose the one which has a shorter length.

This approach makes it easy to track if a hit is horizontal or vertical, which will come in handy later, when we draw to screen. Let’s define a struct for storing the result of a raycast trace.

typedef enum {
    HRZ,
    VRT
} cast_dir;

typedef struct {
    int success;
    float distance;
    cast_dir direction;
} ray_result;

We can define a helper function which hides the horizontal and vertical traces.

ray_result raycast(float x, float y, float angle) {
    ray_result hres = hcast(x, y, angle);
    ray_result vres = vcast(x, y, angle);

    // Success on both - choose shortest
    if (hres.success && vres.success) {
        return hres.distance < vres.distance
            ? hres
            : vres;
    }

    // Only vcast succeded
    if (vres.success) {
        return vres;
    }

    // Either hcast succeded or both failed
    return hres;
}

Algorithm

The horizontal cast algorithm outline is something like this:

Reach first horizontal boundary
Check distance and type of cell hit
If out of range, give up
If hit a wall, return the distance
Otherwise, reach the next boundary and go back to step 2

The following diagram shows how one horizontal trace would be done.

Horizontal Raycast Diagram

ray_result hcast(float x, float y, float angle) {
    ray_result res = {
        .success = 0,
        .distance = 0,
        .direction = HRZ
    };

    // Ray is horizontal - will never reach a horizontal line
    if (near(angle, 0) || near(angle, M_PI)) {
        return res;
    }

    // Before 180 degrees, we cast downwards
    // After 180 degrees, we cast upwards
    int trace_dir = angle > M_PI ? -1 : 1;

    // Reach first boundary
    float ry = trace_dir == 1 ? ceilf(y) : floorf(y);
    float rx = x + (ry - y) / tanf(angle);
    int celly = trace_dir == 1 ? ry : ry - 1;
    int cellx = rx;

    if (is_oob(cellx, celly)) {
        return res;
    }
    int solid = world[cellx][celly];
    float dist = distance(rx, ry, x, y);

    // Already too far
    if (dist > MAX_DIST) {
        return res;
    }

    // Continue until out of range or solid hit
    while (!solid && dist < MAX_DIST) {
        ry += trace_dir;
        rx += trace_dir / tanf(angle);
        celly = trace_dir == 1 ? ry : ry - 1;
        cellx = rx;

        if (is_oob(cellx, celly)) {
            return res;
        }
        solid = world[cellx][celly];
        dist = distance(rx, ry, x, y);
    }

    // If in range, populate result
    if (solid && dist < MAX_DIST) {
        res.success = 1;
        res.distance = dist;
    }

    return res;
}

The vertical cast is very similar but with x and y swapped. The significant differences are the angles checked at the top are rotated, and we are now multiplying by tanf(angle) instead of dividing.

ray_result vcast(float x, float y, float angle) {
    ray_result res = {
        .success = 0,
        .distance = 0,
        .direction = VRT
    };

    // Ray is vertical - will never reach a vertical line
    if (near(angle, M_PI / 2) || near(angle, 3 * M_PI / 2)) {
        return res;
    }

    // Between 90 and 270 degrees cast to the left
    int trace_dir = angle > M_PI / 2 && angle < 3 * M_PI / 2 ? -1 : 1;

    // Reach first boundary
    float rx = trace_dir == 1 ? ceilf(x) : floorf(x);
    float ry = y + (rx - x) * tanf(angle);
    int cellx = trace_dir == 1 ? rx : rx - 1;
    int celly = ry;

    if (is_oob(cellx, celly)) {
        return res;
    }
    int solid = world[cellx][celly];
    float dist = distance(rx, ry, x, y);

    // Already too far
    if (dist > MAX_DIST) {
        return res;
    }

    // Continue until out of range or solid hit
    while (!solid && dist < MAX_DIST) {
        rx += trace_dir;
        ry += trace_dir * tanf(angle);
        cellx = trace_dir == 1 ? rx : rx - 1;
        celly = ry;

        if (is_oob(cellx, celly)) {
            return res;
        }
        solid = world[cellx][celly];
        dist = distance(rx, ry, x, y);
    }

    // If in range, populate result
    if (solid && dist < MAX_DIST) {
        res.success = 1;
        res.distance = dist;
    }

    return res;
}

And here’s the extra definitions required for the functions above. distance finds the distance between two points, near is used for floating point number equality (== will not suffice), and is_oob checks if the target coordinate is out of bounds and should not be read.

#define MAX_DIST 100.0f

float distance(float x1, float y1, float x2, float y2) {
    return sqrtf(powf(x2 - x1, 2) + powf(y2 - y1, 2));
}

int near(float x1, float x2) {
    return fabs(x1 - x2) < 0.001f;
}

int is_oob(int x, int y) {
    if (x < 0 || y < 0) {
        return 1;
    }

    if (x >= WORLD_X || y >= WORLD_Y) {
        return 1;
    }

    return 0;
}

Draw to Screen

Using Raycast Results to Render a View

When rendering the 3D view, we’ll need to partion the screen into rectangular strips. The width of each rectangle depends on how many rays we cast. The count of rays can be expressed as a product of the field of view and rays per degree cast.

#define FOV_DEG 80.0f
#define RAYS_PER_DEG 2

Since the C library expects angles in radians, we’ll also add a convertion factor for degrees to radians.

#define DEG_TO_RAD (M_PI / 180)

Let’s start working on the render function. First, we need to calculate the width of each rectangle. Second, we find the starting ray angle (left most rectangle on the screen), as well as the change in angle with each next ray.

void draw_3d(float x, float y, float angle) {
    // Calculate line count and width
    int rays = FOV_DEG * RAYS_PER_DEG;
    float line_width = SCREEN_WIDTH / rays;

    // Get starting angle
    float start_angle = angle - (FOV_DEG * DEG_TO_RAD / 2.0f);
    
    // Change angle by this much each time
    float angle_delta = DEG_TO_RAD / RAYS_PER_DEG;
}

Then we will have a loop to cast all of our rays and render the results to screen.

    // Change angle by this much each time
    float angle_delta = DEG_TO_RAD / RAYS_PER_DEG;
+
+   // Cast rays and draw to screen
+   for (int i = 0; i < rays; i++) {
+       float current_angle = wrap_angle(start_angle + i * angle_delta);
+       ray_result result = raycast(x, y, current_angle);
+       if (!result.success) {
+           continue;
+       }
+
+       // Set color
+       glColor3f(0.5f, 0.0f, 0.0f);
+
+       // The height is inversly proportional to distance
+       float height = SCREEN_HEIGHT / result.distance;
+       // Draw a vertically centered rectangle
+       float start = line_width * i;
+       glBegin(GL_QUADS);
+       glVertex2f(start, (SCREEN_HEIGHT - height) / 2.0f);
+       glVertex2f(start + line_width, (SCREEN_HEIGHT - height) / 2.0f);
+       glVertex2f(start + line_width, (SCREEN_HEIGHT + height) / 2.0f);
+       glVertex2f(start, (SCREEN_HEIGHT + height) / 2.0f);
+       glEnd();
+   }

Change out the old render functions in the loop for draw_3d and you should see a raycasted representation of the world!

Hello Raycasting

Fixing Distortion

In the above image the walls that we draw aren’t quite straight as they should be. What we are experiencing is called barrel distortion or more commonly referred to as fisheye lens effect. This happens because the rays cast at an angle are longer, thus the rectangle rendered has a smaller height.

Barrel Distortion

Instead of using the actual ray distance, we want to use the scalar projection of the ray onto the view direction.

A Ray’s Scalar Projection

Now to add the correction to our code:

-   float height = SCREEN_HEIGHT / result.distance;
+   float adj_distance = result.distance * cosf(angle - current_angle);
+   float height = SCREEN_HEIGHT / adj_distance;

And the distortion is now fixed!

No Distortion

Final Touches

We’ve completed our goal of making a raycasting engine, but let’s add some minor changes to make the output look nicer.

First, we can add a floor, by just drawing a rectangle of another color in the bottom half of the screen. Call draw_floor before draw_3d in the loop.

void draw_floor() {
    glColor3f(0.0f, 0.0f, 0.4f);

    glBegin(GL_QUADS);
    glVertex2i(0, SCREEN_HEIGHT / 2);
    glVertex2i(SCREEN_WIDTH, SCREEN_HEIGHT / 2);
    glVertex2i(SCREEN_WIDTH, SCREEN_HEIGHT);
    glVertex2i(0, SCREEN_HEIGHT);
    glEnd();
}

And second, we’ll change the color of the wall based on whether it’s a vertical hit or a horizontal hit. In draw_3d, check the cast result and use a slightly lighter shade of red for one of them:

    // Set color
-   glColor3f(0.5f, 0.0f, 0.0f);
+   if (result.direction == HRZ) {
+       glColor3f(0.5f, 0.0f, 0.0f);
+   } else {
+       glColor3f(0.7f, 0.0f, 0.0f);
+   }

Final Look

Notes

Full code for this example can be found here.
Two years ago, I made this and now decided to try to rewrite it.
The code for Wolfenstein 3D is publicly available on Github. The code responsible for rendering seems to be in this assembly file.
Cool video showing the evolution of first-person shooters - YouTube