Introduction to programming: a simple 3D shooter from scratch over the weekend, part 1
This text is intended for those who only master programming. The basic idea is to show stage by stage how you can make a game à la Wolfenstein 3D on your own. Attention, I'm not going to compete with Carmack at all, he is a genius and his code is beautiful. I am aiming for a completely different place: I use the tremendous computing power of modern computers so that students can create fun projects in a few days, not wallowing in the wilds of optimization. I specifically write slow code, as it is significantly shorter and more simply understood. Carmack writes 0x5f3759df , but I write 1 / sqrt (x). We have different goals.
I am convinced that a good programmer is obtained only from someone who kitsit at home for his own pleasure, and not only sits his pants on pairs at the university. In our university, programmers are taught on an endless succession of library catalogs and other things that are boring. Brr My goal is to show examples of projects that are fun to program. This is a vicious circle: if it is interesting to do a project, then a person spends a lot of time on it, gains experience, and sees even more interesting things around (it has become more accessible!), And again plunges into a new project. This is called project training, around solid profit.
The sheet was long, so I broke the text into two parts:
Running code from my repository looks like this:
This is not a complete game, but only a blank for students. An example of a complete game written by two freshmen, see the second part .
So, I’ve been completely deceived by you, I’m not going to tell you how to make a full game in one weekend. I made only 3D engine. Monsters do not run, and the main character does not shoot. But at least I wrote this engine for one Saturday, you can check the commit history. In principle, Sunday is quite enough to make something playable, that is, one weekend you can meet.
At the time of this writing, the repository contains 486 lines of code:
The project depends on SDL2, but in general the window interface and keyboard event handling appear rather late, at midnight Saturday :), when all the rendering code has already been done.
So, I break all code into stages, starting with the bare C ++ compiler. As in my previous articles on the schedule ( tyts , tyts , tyts ), I adhere to the rule “one stage = one commit”, since github makes it very convenient to view the history of code changes.
So let's go. We are still very far from the window interface, for a start we will simply save the pictures to disk. So, we need to be able to store a picture in the computer’s memory and save it to a disk in a format that any third-party program will understand. I want to get this file:
Here is the full C ++ code that draws what we need:
If you do not have a compiler at hand, then it does not matter, if you have an account on a githaba, you can view this code, edit it and run (sic!) In one click directly from the browser.
Using this link, gitpod will create a virtual machine for you, launch VS Code, and open a terminal on a remote machine. In the history of terminal commands (poke into the console and click the up arrow) there is already a full set of commands that allow you to compile the code, run it and open the resulting image.
So what you need to understand from this code. First, the colors I store in the four-byte uint32_t integer type. Each byte is an R, G, B, or A component. The pack_color () and unpack_color () functions allow you to get to the individual components of each color.
The second, two-dimensional image I store in the usual one-dimensional array. To get to the pixel with coordinates (x, y) I do not write image [x] [y], but I write image [x + y * width]. If this method of packaging two-dimensional information in a one-dimensional array for you is new, then right now take a pen and sort it out. For me personally, this stage does not even reach the brain, it is processed directly in the spinal cord. Three- and more-dimensional arrays can be packaged in the same way, but we will not go above the two components.
Then I simply run through my picture with a simple double cycle, fill it with a gradient, and save it to a disk in the .ppm format.
We need a map of our world. At this stage, I just want to define the data structure and draw a map on the screen. It should look like this:
Changes you can see here . Everything is simple there: I zahardkodil map into a one-dimensional array of characters, defined the function of drawing a rectangle, but walked around the map, drawing each cell.
I remind you that this button will let you run the code right at this stage:
What do we need to be able to draw a player on the map? GPS coordinates are enough :)
Add two variables x and y, and draw the player in the appropriate place:
Changes you can see here . I won't remind you more about the guitar pod :)
In addition to the coordinates of the player, it would be nice for us to also know in which direction he is looking. Therefore, add another variable player_a, which gives the direction of the player’s gaze (the angle between the direction of the gaze and the x-axis):
And now I want to be able to glide along the orange beam. How to do it? Extremely simple. Let's look at the green right triangle. We know that cos (player_a) = a / c, and that sin (player_a) = b / c.
What happens if I arbitrarily take the value c (positive) and count x = player_x + c * cos (player_a) and y = player_y + c * sin (player_a)? We will be in the purple point; By varying the parameter c from zero to infinity, we can make this purple point slide along our orange ray, and c is the distance from (x, y) to (player_x, player_y)!
The heart of our graphics engine is such a cycle:
We move point (x, y) along the ray, if it hits an obstacle on the map, then we interrupt the cycle, and the variable c gives the distance to the obstacle! What is not a laser rangefinder?
Changes you can see here .
One beam is fine, but still our eyes see a whole sector. Let's call the angle of view fov (field of view):
And we will release 512 rays (by the way, why 512?), Smoothly sweeping the whole sector of the review:
Changes you can see here .
And now the key point. For each of the 512 rays, we got the distance to the nearest obstacle, right? And now let's make the second picture width (spoiler) 512 pixels; in which we will draw one vertical segment for each ray, and the height of the segment is inversely proportional to the distance to the obstacle:
Once again, this is the key moment in creating the illusion of 3D, make sure that you understand what is being said. When drawing vertical segments, in fact, we draw a palisade, where the height of each stake is the smaller, the further it is from us:
Changes you can see here .
At this stage, we draw something dynamic for the first time (I just throw 360 pictures onto the disk). Everything is trivial: I change player_a, draw the picture, save, change player_a, draw, save. To make it a bit more fun, I assigned a random color value to each cell type in our map.
Changes you can see here .
Did you notice what a great “fish eye” effect we get when we look at the wall up close? Something like this:
Why? Yes, very simple. Here we are looking at the wall:
To draw our wall we sweep our blue viewing area with a violet ray. Take the specific value of the direction of the beam, as in this picture. The length of the orange segment is clearly less than the length of purple. Since to determine the height of each vertical segment that we draw on the screen, we divide by the distance to the barrier, the fisheye is quite natural.
Correcting this distortion is not difficult; see how it is done . Please make sure you understand where the cosine came from. Draw a scheme on a piece of paper helps a lot.
It is time to deal with textures. I am lazy to write an image uploader myself, so I took a great stb library . I prepared a file with textures for the walls, all the textures are square and packed into an image horizontally:
At this stage, I just load the textures into memory. To check the performance of the written code, I just draw the texture with index 5 in the upper left corner of the screen:
Changes you can see here .
Now I throw out randomly generated colors and tint my walls, taking the upper left pixel from the corresponding texture:
Changes you can see here .
And now the long-awaited moment has come when we will finally see the brick walls:
The basic idea is very simple: here we glide along the current beam and stop at the point x, y. Let's suppose that we stopped on a “horizontal” wall, then y is almost integer (not quite, because our way of moving along the beam introduces a small error). Let's take the fractional part of x and call it hitx. The fractional part is less than one, therefore, if we multiply hitx by the texture size (I have 64), then this will give us the texture column to be drawn in this place. It remains to stretch it to the desired size and the trick is:
In general, the idea is extremely primitive, but it requires careful execution, since we also have “vertical” walls (those with hitx will be close to zero [x is integer]). For them, the texture column is determined by hity, the fractional part of y. Changes you can see here .
At this stage I didn’t do anything new, I just started general cleaning. Until now, I had one giant (185 lines!) File, and it became difficult to work in it. Therefore, I broke it into a small cloud, unfortunately, at the same time almost doubling the size of the code (319 lines), without adding any functionality. But it has become much more convenient to use, for example, in order to generate an animation, it is enough to do such a cycle:
Well, here's the result:
Changes you can see here .
On this optimistic note, I finish the current half of my sheet, the second half is available here . In it, we add monsters and link up with SDL2 so that we can walk in our virtual world.
I am convinced that a good programmer is obtained only from someone who kitsit at home for his own pleasure, and not only sits his pants on pairs at the university. In our university, programmers are taught on an endless succession of library catalogs and other things that are boring. Brr My goal is to show examples of projects that are fun to program. This is a vicious circle: if it is interesting to do a project, then a person spends a lot of time on it, gains experience, and sees even more interesting things around (it has become more accessible!), And again plunges into a new project. This is called project training, around solid profit.
The sheet was long, so I broke the text into two parts:
- Part one: drawing the walls
- Part two: we inhabit our world + window interface
Running code from my repository looks like this:
This is not a complete game, but only a blank for students. An example of a complete game written by two freshmen, see the second part .
So, I’ve been completely deceived by you, I’m not going to tell you how to make a full game in one weekend. I made only 3D engine. Monsters do not run, and the main character does not shoot. But at least I wrote this engine for one Saturday, you can check the commit history. In principle, Sunday is quite enough to make something playable, that is, one weekend you can meet.
At the time of this writing, the repository contains 486 lines of code:
haqreu@daffodil:~/tinyraycaster$ cat *.cpp *.h | wc -l 486 The project depends on SDL2, but in general the window interface and keyboard event handling appear rather late, at midnight Saturday :), when all the rendering code has already been done.
So, I break all code into stages, starting with the bare C ++ compiler. As in my previous articles on the schedule ( tyts , tyts , tyts ), I adhere to the rule “one stage = one commit”, since github makes it very convenient to view the history of code changes.
Stage 1: save the image to disk
So let's go. We are still very far from the window interface, for a start we will simply save the pictures to disk. So, we need to be able to store a picture in the computer’s memory and save it to a disk in a format that any third-party program will understand. I want to get this file:
Here is the full C ++ code that draws what we need:
#include <iostream> #include <fstream> #include <vector> #include <cstdint> #include <cassert> uint32_t pack_color(const uint8_t r, const uint8_t g, const uint8_t b, const uint8_t a=255) { return (a<<24) + (b<<16) + (g<<8) + r; } void unpack_color(const uint32_t &color, uint8_t &r, uint8_t &g, uint8_t &b, uint8_t &a) { r = (color >> 0) & 255; g = (color >> 8) & 255; b = (color >> 16) & 255; a = (color >> 24) & 255; } void drop_ppm_image(const std::string filename, const std::vector<uint32_t> &image, const size_t w, const size_t h) { assert(image.size() == w*h); std::ofstream ofs(filename); ofs << "P6\n" << w << " " << h << "\n255\n"; for (size_t i = 0; i < h*w; ++i) { uint8_t r, g, b, a; unpack_color(image[i], r, g, b, a); ofs << static_cast<char>(r) << static_cast<char>(g) << static_cast<char>(b); } ofs.close(); } int main() { const size_t win_w = 512; // image width const size_t win_h = 512; // image height std::vector<uint32_t> framebuffer(win_w*win_h, 255); // the image itself, initialized to red for (size_t j = 0; j<win_h; j++) { // fill the screen with color gradients for (size_t i = 0; i<win_w; i++) { uint8_t r = 255*j/float(win_h); // varies between 0 and 255 as j sweeps the vertical uint8_t g = 255*i/float(win_w); // varies between 0 and 255 as i sweeps the horizontal uint8_t b = 0; framebuffer[i+j*win_w] = pack_color(r, g, b); } } drop_ppm_image("./out.ppm", framebuffer, win_w, win_h); return 0; } If you do not have a compiler at hand, then it does not matter, if you have an account on a githaba, you can view this code, edit it and run (sic!) In one click directly from the browser.
Using this link, gitpod will create a virtual machine for you, launch VS Code, and open a terminal on a remote machine. In the history of terminal commands (poke into the console and click the up arrow) there is already a full set of commands that allow you to compile the code, run it and open the resulting image.
So what you need to understand from this code. First, the colors I store in the four-byte uint32_t integer type. Each byte is an R, G, B, or A component. The pack_color () and unpack_color () functions allow you to get to the individual components of each color.
The second, two-dimensional image I store in the usual one-dimensional array. To get to the pixel with coordinates (x, y) I do not write image [x] [y], but I write image [x + y * width]. If this method of packaging two-dimensional information in a one-dimensional array for you is new, then right now take a pen and sort it out. For me personally, this stage does not even reach the brain, it is processed directly in the spinal cord. Three- and more-dimensional arrays can be packaged in the same way, but we will not go above the two components.
Then I simply run through my picture with a simple double cycle, fill it with a gradient, and save it to a disk in the .ppm format.
Stage 2: draw a level map
We need a map of our world. At this stage, I just want to define the data structure and draw a map on the screen. It should look like this:
Changes you can see here . Everything is simple there: I zahardkodil map into a one-dimensional array of characters, defined the function of drawing a rectangle, but walked around the map, drawing each cell.
I remind you that this button will let you run the code right at this stage:
Stage 3: add a player
What do we need to be able to draw a player on the map? GPS coordinates are enough :)
Add two variables x and y, and draw the player in the appropriate place:
Changes you can see here . I won't remind you more about the guitar pod :)
Stage 4: virtual rangefinder aka first ray tracing
In addition to the coordinates of the player, it would be nice for us to also know in which direction he is looking. Therefore, add another variable player_a, which gives the direction of the player’s gaze (the angle between the direction of the gaze and the x-axis):
And now I want to be able to glide along the orange beam. How to do it? Extremely simple. Let's look at the green right triangle. We know that cos (player_a) = a / c, and that sin (player_a) = b / c.
What happens if I arbitrarily take the value c (positive) and count x = player_x + c * cos (player_a) and y = player_y + c * sin (player_a)? We will be in the purple point; By varying the parameter c from zero to infinity, we can make this purple point slide along our orange ray, and c is the distance from (x, y) to (player_x, player_y)!
The heart of our graphics engine is such a cycle:
float c = 0; for (; c<20; c+=.05) { float x = player_x + c*cos(player_a); float y = player_y + c*sin(player_a); if (map[int(x)+int(y)*map_w]!=' ') break; } We move point (x, y) along the ray, if it hits an obstacle on the map, then we interrupt the cycle, and the variable c gives the distance to the obstacle! What is not a laser rangefinder?
Changes you can see here .
Stage 5: Sector Overview
One beam is fine, but still our eyes see a whole sector. Let's call the angle of view fov (field of view):
And we will release 512 rays (by the way, why 512?), Smoothly sweeping the whole sector of the review:
Changes you can see here .
Stage 6: 3D!
And now the key point. For each of the 512 rays, we got the distance to the nearest obstacle, right? And now let's make the second picture width (spoiler) 512 pixels; in which we will draw one vertical segment for each ray, and the height of the segment is inversely proportional to the distance to the obstacle:
Once again, this is the key moment in creating the illusion of 3D, make sure that you understand what is being said. When drawing vertical segments, in fact, we draw a palisade, where the height of each stake is the smaller, the further it is from us:
Changes you can see here .
Stage 7: First Animation
At this stage, we draw something dynamic for the first time (I just throw 360 pictures onto the disk). Everything is trivial: I change player_a, draw the picture, save, change player_a, draw, save. To make it a bit more fun, I assigned a random color value to each cell type in our map.
Changes you can see here .
Stage 8: Fish Eye Correction
Did you notice what a great “fish eye” effect we get when we look at the wall up close? Something like this:
Why? Yes, very simple. Here we are looking at the wall:
To draw our wall we sweep our blue viewing area with a violet ray. Take the specific value of the direction of the beam, as in this picture. The length of the orange segment is clearly less than the length of purple. Since to determine the height of each vertical segment that we draw on the screen, we divide by the distance to the barrier, the fisheye is quite natural.
Correcting this distortion is not difficult; see how it is done . Please make sure you understand where the cosine came from. Draw a scheme on a piece of paper helps a lot.
Stage 9: loading the texture file
It is time to deal with textures. I am lazy to write an image uploader myself, so I took a great stb library . I prepared a file with textures for the walls, all the textures are square and packed into an image horizontally:
At this stage, I just load the textures into memory. To check the performance of the written code, I just draw the texture with index 5 in the upper left corner of the screen:
Changes you can see here .
Stage 10: rudimentary use of textures
Now I throw out randomly generated colors and tint my walls, taking the upper left pixel from the corresponding texture:
Changes you can see here .
Stage 11: Textured Walls for Real
And now the long-awaited moment has come when we will finally see the brick walls:
The basic idea is very simple: here we glide along the current beam and stop at the point x, y. Let's suppose that we stopped on a “horizontal” wall, then y is almost integer (not quite, because our way of moving along the beam introduces a small error). Let's take the fractional part of x and call it hitx. The fractional part is less than one, therefore, if we multiply hitx by the texture size (I have 64), then this will give us the texture column to be drawn in this place. It remains to stretch it to the desired size and the trick is:
In general, the idea is extremely primitive, but it requires careful execution, since we also have “vertical” walls (those with hitx will be close to zero [x is integer]). For them, the texture column is determined by hity, the fractional part of y. Changes you can see here .
Stage 12: time to refactor!
At this stage I didn’t do anything new, I just started general cleaning. Until now, I had one giant (185 lines!) File, and it became difficult to work in it. Therefore, I broke it into a small cloud, unfortunately, at the same time almost doubling the size of the code (319 lines), without adding any functionality. But it has become much more convenient to use, for example, in order to generate an animation, it is enough to do such a cycle:
for (size_t frame=0; frame<360; frame++) { std::stringstream ss; ss << std::setfill('0') << std::setw(5) << frame << ".ppm"; player.a += 2*M_PI/360; render(fb, map, player, tex_walls); drop_ppm_image(ss.str(), fb.img, fb.w, fb.h); } Well, here's the result:
Changes you can see here .
To be continued ... immediately
On this optimistic note, I finish the current half of my sheet, the second half is available here . In it, we add monsters and link up with SDL2 so that we can walk in our virtual world.
Source: https://habr.com/ru/post/439698/