So… this is it. I’m getting old.
id Software is one of the most important software house for both videogames history and me… and 5 days ago (1st Feb 2018) was its 27th birthday!
1st Feb 1991, 5 guys (not the fast food) registered the name “id Software” for their newborn game development studio and gave birth to one of the most important games ever: Wolfenstein 3D, the first FPS ever.
Apart from defining a genre, the most important thing that Wolf3D did was to introduce a new technique to render a 3D scene in plain 2D without calculating a single 3D object. This technique is called raycasting and is based on geometrical interpretation of a 2D map using some linear algebra trick. Then, in 1993, id created Doom that used the same principle, but with a more optimized engine that permitted to render levels of incredible detail, the possibility to make mods, and a lot more texture. Then, one year after, it came Doom 2, with more mods, big spaces and the illusion to have more than one floor.
In this article I’m gonna try and explain how you can implement a Raycasting engine to create from scratch a pseudo-3D fps like Wolfenstein (or Doom) in C++ with SDL. Yes, I know, nowadays you can create actual 3D fps way more easily with Unity or Unreal Engine, but creating a raycasting engine from scratch in pure C++/SDL is not only a very good exercise for your programming skills, but it teaches you an important lesson: when you don’t have enough resources and you have to optimize a lot, maths skills kicks asses! This is not just a graphical engine to make a Wolf3D/Doom clone, but it’s a project that shows you how it was possible to revolutionize the world of videogames with just a good idea.
For this project you can use whatever graphical library you want: SDL, SFML, PixelToast… they’re all good. I’m gonna use SDL2 because it’s the lib I know best and it’s pretty common in the game dev (mostly in indie and linux game-dev).
We’re gonna use C++ as programming language and of course you can choose whatever IDE/compiler you want… it’s not gonna break anything, don’t worry. The only thing you have to check is how to configure SDL2 (or the library you chose) for that IDE/compiler.
If you need a tutorial to setup SDL2 or to know how to use it, you can try the amazing tutorial series by Lazy Foo.
Theory and planning
So, how this raycasting thing works?
If you ever played Wolfenstein 3D, you probably noticed that the whole game take place in a labirinth without stairs. All the game take place on the same floor. This is because raycasting is not real 3D, but the projection of a 2D map. The principle under this technique is the same that lies behind the axonometry.
The 2D map can be implemented in various ways… you can create a matrix MxN of various symbols each of which represent a different object in the room. This is the way they did it in id Software and we’re gonna copy them! 😛
This is what the first level of Wolfenstein 3D map looked like in the original map editor. Every character means something for the map parser that tells the engine what to render and where.
A super interesting thing about this system is that you can actually implement endless type of object because you can use every ASCII/Unicode character, and if that’s not enough, with a little more effort, you can create a more advanced parser that can process more sophisticated maps… but that’s not the case. We’re gonna keep things simple and by the way, even just using non-extended ASCII is more than enough for a lot of games.
Do you see that red G in the bootom of the map? Well, that is the player. But how it works camera, movement and player’s pov? Well, the player is represented as a matrix 2×3 made of three 2×1 vectors.
- Position Vector (P)
- Direction Vector (D)
- Camera Vector (C)
This is a (very raw) representation of the player and his components.
The black sphere is of course the player that is represented by a point P(x,y), the position vector.
The blue line is the Camera vector that represents the field of view’s width.
The red line is the Direction vector and has two roles: it tells us the direction we are facing and its length used in pair with the Camera vector’s width gives us the FOV (field of view) of the player, that is represented with the green cone.
Of course we can represent all those points with 2×1 vectors [x,y], as we stated before.
With this representation of the player, the only remaining mistery is… how can we see the level in a 3D way if it’s represented in a 2D map and we only have 2 coordinates?
Here comes maths! We know the direction the player is looking at, and we know the width of his FOV, so we can draw a family of intersecting straight lines for the point P(a,b) (the position of our player) with the formula y-a = m*(x-b) where a and b are the coordinates of our vector P and m is the slope that is valid only between the range defined by our FOV. If you don’t know what a family of intersecting straight line is, well, it’s just the set of all the straight lines that passes for a certain point P.
While we draw those lines, we can check if they collide with one of the elements on our map. When a line collide with an object O, we calculate the distance between O and the position of our player P. That is the distance between the player and the object, so the object should be drawn in a size according to that distance. If the distance is long, the object will be small, if the distance is short, the object will be big.
For simplicity, let’s consider a squared object of size KxK. We can represent that object with a 2×2 matrix: W=.
If the player is at distance d from the object, its size will be d*W. Little remainder: you can do dot-product on a matrix/vector with linear algebra and it’s done by multiplying every element of the matrix/vector by the multiplier.
So now we have a very nice and smart way of drawing objects, but how we can move according to this new drawing law? Well, this is actually the simplest thing. As it was in Wolfenstein 3D, the player is allowed to go forward, backward and to rotate right and left. Going forward and backward is just a matter of sum to the coordinates of our vectors. To rotate, we’re gonna use the classic rotating matrix of linear algebra:
If you don’t know linear algebra, to rotate the D vector by a coefficient k, you have to multiply by the rotation matrix like that:
D.x = D.x * cos(k) – D.y * sin(k)
D.y = D.x * sin(k) + D.y * cos(k)
where D.x and D.y are the x and y coordinates of the direction vector D.
Now we have everything we need to get started. So, in the next article, we will build the engine and I will explain the source code as we go though it. In the meantime you can try to absorbe the theory, give a read to some linear algebra and C++ or read some SDL tutorial to prepare yourself for the coding session.
See you next time!