Wolf3D raycasting engine – The Implementation

Here we are! After a one-day full-immersion, here is the first version of what I called Dog3D: a pseudo-3D raycasting engine inspired by Wolfenstein 3D’s engine.

Dog3D is based on the same principles I described in the previous article. I’m not gonna repeat myself, so if you haven’t read the theory, go read it and then come back here.

In this article I’m gonna explain how you can implement the raycasting theory we saw previously to build a real world raycasting engine.

Since there is a lot of code to show, I will just show you the most important, so I can explain it to you. To see the complete work, just check out my github.

The basic idea and data structures

Design, in software development, is probably the most important thing. It allows you to program faster and better and a good design makes possible to optimize your work with less effort.

So, let’s decide what we want to make!

We said we can represent our levels with a 2D matrix, so we want our engine to read levels from external files (no one likes to create integer matrices manually) in a form like this:

The numbers defines different types of objects, the white spaces represent walkable area and the P character is the player.
The player will move in the walkable area and the engine will render every block in his field of view respecting the proportions based on the distance from the player.

This matrix is obviously a 2D characters matrix, so we can implement it as a pointer to string:

std::string *level;

It’s useful to store also matrix’s width and height, so we can work more easily, in case we need those informations. It’s probably a good idea to store those informations in the same structure… and now that we are on this, it would be nice to save also player’s position in it, since we can only have one player in the level and the player is an object of the level.

So, let’s define some useful structures:

struct CoordUint32
{
    uint32_t x;
    uint32_t y;
};

struct Player
{
    CoordUint32 pos;
};

struct Level
{
    uint32_t width;
    uint32_t height;
    std::string *level;
    Player player;
};

CoordUint32 is a 2×1 vector that stores two unsigned int variables. I made a couple other structures like that in the final source code, just because it’s useful to have them (for example CoordDouble and CoordInt). It’s trivial to make them, once you saw CoordUint32.

Player represents our player’s position with a couple of unsigned int coordinates.

Level stores the level itself as an array of strings, the level’s dimensions and the player position.

Now we have everything we need to write down the function to read levels from a txt file.
The function will take as parameters the filename of the level and a pointer the Level structure (so we can store informations).

bool loadLevel(std::string filename, Level *l)
{
    std::ifstream ifs(filename);
    std::string content( (std::istreambuf_iterator<char>(ifs) ), (std::istreambuf_iterator<char>() ) );
    auto k = explode(content, '\n');

    if(k.empty())
    {
        return false;
    }

    l->height = k.size();
    l->width = k.front().size();
    l->level = new std::string[k.size()];

    for(int i = 0; i < k.size(); i++)
    {
        l->level[i] = k.at(i);
    }

    substituteSpacesWithZeros(l);

    return (setPlayerPosition(l));
}

This is pretty straight-forward, if you have some C++ background. If you haven’t , sorry it’s too long to explain here… you can find a lot of good tutorials on string manipulation in C++ online, though! So just google it!

The substituteSpacesWithZeros function just loops in the level map and substitutes all the spaces with zeroes (to avoid problems with the later parsing of the level map). Since it’s pretty identical to setPlayerPosition, I’ll write here just the latter so you can easily implement the former.

That explode function is a custom function that acts like the homonym PHP function and it returns an array of strings that are the substrings of the content string divided by the ‘\n’ character:

std::vector<std::string> explode(std::string const & s, char delim)
{
    std::vector<std::string> result;
    std::istringstream iss(s);

    for (std::string token; std::getline(iss, token, delim); )
    {
        result.push_back(std::move(token));
    }

    return result;
}

Elegant, innit? 😛
You can use it for any fast-parsing job. Really helpful!

So now we have our Level.level filled with an array of strings each of which is a line of our level txt file.
We just need to set player’s coordinates:

bool setPlayerPosition(Level *l)
{
    for(int i = 0; i < l->height; i++)
    {
        for(int j = 0; j < l->width; j++)
        {
            if(l->level[i].at(j) == 'P')
            {
                l->player.pos.x = j;
                l->player.pos.y = i;
                l->level[i].at(j) = '0';
                return true;
            }
        }
    }
    return false;
}

The setPlayerPosition function loops into the Level.level array and checks if there is a character that equals ‘P’. P is our placeholder for the player inside the text map. So, when the function finds P, it saves the coordinates into player.pos and substitutes P with a zero in the level map, to avoid problems with the later parsing of the level map.

We can check if everything is okay with a fast test in the main function:

Level level;
bool loaded = loadLevel("data/1.txt", &level);

if(!loaded)
{
    return -1;
}

for(uint8_t i = 0; i < level.height; i++)
{
    for(uint8_t j = 0; j < level.width; j++)
    {
        std::cout << level.level[i].at(j);
    }
    std::cout << std::endl;
}

std::cout << std::endl << "Map of size: " << level.height << "x" << level.width << std::endl;
std::cout << "Player starting position: " << level.player.pos.x << ", " << level.player.pos.y << std::endl;

This code will print the converted map (zeroed), its dimensions and the player position in the map.

The main algorithm

I’m not gonna explain SDL2 principles, so you better check out some tutorial, if you’re green with it. It’s very straight forward, nothing hard.

We need some variables to represent the camera, that is what we will use to see inside our level:

CoordDouble pos = { level.player.pos.x, level.player.pos.y }; // camera position
CoordDouble dir = { -1, 0 }; // camera direction vector
CoordDouble plane = { 0, 0.66 }; // camera plane

Raycasting is based on the concept of casting a series of rays from the camera point-of-view and render whichever object we find on our way. We will cast a ray for every pixel in our screen X-axis from our POV and draw a vertical line of the right size (based on distance and angle) if the ray hits an object.

So, inside our game loop, we need to loop for all the x in our X-axis and calculate the ray for that x. We calculate the ray step by step increasing its length one block at a time until we hit a non-zero block (zero blocks are walkable area, while non-zero blocks are solid and non-walkable):

for(int x = 0; x < SCREEN_WIDTH; x++) // for all x on the screen resolution
{
    double cameraX = 2*x / double(SCREEN_WIDTH) - 1;
    CoordDouble rayPos = { pos.x, pos.y };
    CoordDouble rayDir = { dir.x + plane.x * cameraX, dir.y + plane.y * cameraX };
    CoordInt mapc = { int(rayPos.x), int(rayPos.y) };
    CoordDouble sideDist;
    CoordDouble deltaDist = { sqrt(1 + (rayDir.y * rayDir.y)/(rayDir.x * rayDir.x)), sqrt(1 + (rayDir.x * rayDir.x)/(rayDir.y * rayDir.y)) };
    double perpWallDist;
    CoordInt step;
    int hit = 0;
    int side;
    
    // setting step and sideDist based on rayDir values
    if(rayDir.x < 0)
    {
        step.x = -1;
        sideDist.x = (rayPos.x - mapc.x) * deltaDist.x;
    }
    else
    {
        step.x = 1;
        sideDist.x = (mapc.x + 1.0 - rayPos.x) * deltaDist.x;
    }

    if(rayDir.y < 0)
    {
        step.y = -1;
        sideDist.y = (rayPos.y - mapc.y) * deltaDist.y;
    }
    else
    {
        step.y = 1;
        sideDist.y = (mapc.y + 1.0 - rayPos.y) * deltaDist.y;
    }

    // check if the casted ray has hit an object
    while(hit == 0) // calculate ray until it hits an object
    {
        if(sideDist.x < sideDist.y)
        {
            sideDist.x += deltaDist.x;
            mapc.x += step.x;
            side = 0;
        }
        else
        {
            sideDist.y += deltaDist.y;
            mapc.y += step.y;
            side = 1;
        }

        if(level.level[mapc.x][mapc.y]>'0') // the ray has hit a non-zero block at position mapc.x, mapc.y
        {
            hit = 1;
        }
    }

 

Now that we found an object, we need to calculate the distance from that object to our camera direction vector:

// distance based on camera direction
if (side == 0)
{
    perpWallDist = fabs((mapc.x - rayPos.x + (1 - step.x) / 2) / rayDir.x);
}
else
{
    perpWallDist = fabs((mapc.y - rayPos.y + (1 - step.y) / 2) / rayDir.y);
}

After that, we can define the line to draw: its coordinates and its height. Plus, we’re gonna chose the right color for the type of object that we hit and finally draw the line with a custom function:

    // the line to draw...
    int lineHeight = abs(int(SCREEN_HEIGHT / perpWallDist)); // height
    int drawStart = -lineHeight / 2 + SCREEN_HEIGHT / 2; // y1
    if (drawStart < 0) drawStart = 0;
    int drawEnd = lineHeight / 2 + SCREEN_HEIGHT / 2; // y2
    if (drawEnd >= SCREEN_HEIGHT) drawEnd = SCREEN_HEIGHT - 1;
    
    
    su::RGBA color;
    switch(level.level[mapc.x][mapc.y])
    {
        case '1': // RED
            color.r = 255;
            color.g = 0;
            color.b = 0;
            color.a = 255;
            break;
        case '2': // GREEN
            color.r = 0;
            color.g = 255;
            color.b = 0;
            color.a = 255;
            break;
        case '3': // BLUE
            color.r = 0;
            color.g = 0;
            color.b = 255;
            color.a = 255;
            break;
        case '4': // BROWN
            color.r = 140;
            color.g = 70;
            color.b = 20;
            color.a = 255;
            break;
        default:
            color.r = 0;
            color.g = 100;
            color.b = 100;
            color.a = 255;
            break;
    }
    
    if(side == 1)
    {
        color = { color.r/2, color.g/2, color.b/2, color.a };
    }
    
    drawVerticalLine(renderer, x, drawStart, drawEnd, color); // draw the line!
}

The custom function to draw the line, is really straight forward and it uses the new features of SDL2:

// draws a vertical line of 1 pixel at coordinates (x,startY) of length endY and color rgba
void drawVerticalLine(SDL_Renderer* r, int x, int startY, int endY, su::RGBA rgba)
{
    SDL_SetRenderDrawColor(r, rgba.r, rgba.g, rgba.b, rgba.a);
    SDL_RenderDrawLine(r, x, startY, x, endY);
}

Now we need to clear the screen and we’re pretty much done.

SDL_RenderPresent(renderer); // update screen
SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255); // set color
SDL_RenderClear(renderer); // clear screen

 

Controls

The only thing left is the controls. We should be able to go forward, backward, turn left and turn right. Those are the basic movements expected and as we stated in the previous article, it’s only a matter of linear algebra and trigonometry.

First of all, we have to define the framerate at which we’re gonna move.

prevTick = curTick; // this is a double
curTick = SDL_GetTicks(); // this is a double too
double frameRate = (curTick - prevTick)/1000.0; // calculate framerate
printf("FPS: %f\n", 1.0/frameRate); // print framerate

double moveSpeed = frameRate * 5.0; // movement speed
double rotationSpeed = frameRate * 3.0; // rotation speed

Now we just have to read the keyboard state and do the right calculations for every key the player hits.

In SDL2 we can read the keyboard state by just calling SDL_GetKeyboardState(NULL) that returns an array of Uint8. So we just need to check if in that array there is an element with true as value and our keyboard code as key.

state = SDL_GetKeyboardState(NULL);

if (state[SDL_SCANCODE_W]) // forward movement with 'W' key
{
    if(level.level[int(pos.x + dir.x * moveSpeed)][int(pos.y)] == '0') pos.x += dir.x * moveSpeed;
    if(level.level[int(pos.x)][int(pos.y + dir.y * moveSpeed)] == '0') pos.y += dir.y * moveSpeed;
}

if (state[SDL_SCANCODE_S]) // backward movement with 'S' key
{
    if(level.level[int(pos.x - dir.x * moveSpeed)][int(pos.y)] == '0') pos.x -= dir.x * moveSpeed;
    if(level.level[int(pos.x)][int(pos.y - dir.y * moveSpeed)] == '0') pos.y -= dir.y * moveSpeed;
}

if (state[SDL_SCANCODE_D]) // rotate to the right with 'D' key
{
    double oldDirX = dir.x;
    dir.x = dir.x * cos(-rotationSpeed) - dir.y * sin(-rotationSpeed);
    dir.y = oldDirX * sin(-rotationSpeed) + dir.y * cos(-rotationSpeed);

    double oldPlaneX = plane.x;
    plane.x = plane.x * cos(-rotationSpeed) - plane.y * sin(-rotationSpeed);
    plane.y = oldPlaneX * sin(-rotationSpeed) + plane.y * cos(-rotationSpeed);
}

if (state[SDL_SCANCODE_A]) // rotate to the left with 'A' key
{
    double oldDirX = dir.x;
    dir.x = dir.x * cos(rotationSpeed) - dir.y * sin(rotationSpeed);
    dir.y = oldDirX * sin(rotationSpeed) + dir.y * cos(rotationSpeed);

    double oldPlaneX = plane.x;
    plane.x = plane.x * cos(rotationSpeed) - plane.y * sin(rotationSpeed);
    plane.y = oldPlaneX * sin(rotationSpeed) + plane.y * cos(rotationSpeed);
}

There is really nothing to explain, since this is just the same thing we saw in the theory article. It’s just a matter of applying a formula.

If you find it hard to understand, just take your time, reread the theory and try to see that what I did here, is the same identical thing.

When you press W or S, the camera move forward or backward in the map.

When you press A or D, the camera position rotates left or right using the rotation matrix calculated on the value of rotationSpeed (that represents also the angle for the rotation matrix). The value of rotationSpeed is positive for counterclockwise and negative for clockwise rotations.

This is what you’re gonna get, when you put everything together:

Conclusions

Done! The engine is ready!
This is really all you have to know to build your own raycasting engine. The funny thing of this project is that you can work on it to make it better and more powerful! You can make out of it, real games and learn a lot!
And by the way, built a complete/polished version of the Dog3D engine, if you want to check it out.

I hope you enjoyed the tutorial and hope it was useful to learn new things and have some fun programming old school games! 🙂

Good hacking and See you next time!

Leave a Reply

Your email address will not be published. Required fields are marked *

Navigation