Algorithms
C++
Game development
Programming
Working with 3D-graphics
February 10

Введение в программирование: простой 3D-шутер с нуля за выходные, часть 1

Tutorial
Этот текст предназначен для тех, кто только осваивает программирование. Основная идея в том, чтобы показать этап за этапом, как можно самостоятельно сделать игру à la Wolfenstein 3D. Внимание, я совершенно не собираюсь соревноваться с Кармаком, он гений и его код прекрасен. Я же целюсь совсем в другое место: я использую огромную вычислительную мощность современных компьютеров для того, чтобы студенты могли создавать забавные проекты за несколько дней, не погрязая в дебрях оптимизации. Я специально пишу медленный код, так как он существенно короче и просто понятнее. Кармак пишет 0x5f3759df, я же пишу 1/sqrt(x). Мы преследуем разные цели.

Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.

Простыня получилась длинная, поэтому я разбил текст на две части:


Выполнение кода из моего репозитория выглядит вот так:


Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.

Получается, я совсем чуточку вас обманул, я не расскажу как сделать полную игру за одни выходные. Я сделал только 3Д движок. Монстры у меня не бегают, да и главный персонаж не стреляет. Но, по крайней мере, этот движок я написал за одну субботу, можете проверить историю коммитов. В принципе, воскресенья вполне достаточно, чтобы сделать нечто играбельное, то есть, в одни выходные можно уложиться.

На момент написания этого текста репозиторий содержит 486 строк кода:

haqreu@daffodil:~/tinyraycaster$ cat *.cpp *.h | wc -l
486

Проект зависит от SDL2, но вообще оконный интерфейс и обработка событий от клавиатуры появляются довольно поздно, в полночь субботы :), когда весь код рендеринга уже сделан.

Итак, я разбиваю весь код на этапы, стартуя с голого компилятора C++. Как и в предыдущих моих статьях по графике (тыц, тыц, тыц), я придерживаюсь правила «один этап = один коммит», так как github позволяет очень удобно просматривать историю изменений кода.

Этап 1: сохранение картинки на диск


Итак, поехали. До оконного интерфейса нам ещё очень далеко, для начала мы будем просто сохранять картинки на диск. Итого, нам нужно уметь хранить картинку в памяти компьютера и сохранять её на диск в формате, который поймёт какая-нибудь сторонняя программа. Я хочу получить вот такой файл:



Вот так выглядит полный C++ код, который рисует то, что нам нужно:

#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;
}

Если у вас под рукой нет компилятора, то это не беда, при наличии учётной записи на гитхабе этот код можно посмотреть, отредактировать и запустить (sic!) в один клик прямо из браузера.

Open in Gitpod

По этой ссылке gitpod создаст для вас виртуальную машину, запустит VS Code, и откроет терминал на удалённой машине. В истории команд терминала (ткните в консоль и нажмите стрелку вверх) уже полный набор команд, который позволяют скомпилировать код, его запустить и открыть результирующую картинку.

Итак, что нужно понять из этого кода. Первое, цвета я храню в четырёхбайтном целочисленном типе uint32_t. Каждый байт — это компонента R, G, B или A. функции pack_color() и unpack_color() позволяют добираться до индивидуальных компонент каждого цвета.

Второе, двумерную картинку я храню в обычном одномерном массиве. Чтобы добраться до пикселя с координатами (x,y) я не пишу image[x][y], но пишу image[x + y*width]. Если этот способ упаковки двумерной информации в одномерный массив для вас нов, то прямо сейчас возьмите ручку и разберитесь с ним. У меня лично этот этап даже не доходит до головного мозга, обрабатывается прямо в спинном. Трёх- и более -мерные массивы можно упаковать точно так же, но мы выше двух компонент не поднимемся.

Дальше я простым двойным циклом пробегаю мою картинку, заполняю её градиентом, и сохраняю на диск в формате .ppm.



Этап 2: рисуем карту уровня


Нам нужна карта нашего мира. На этом этапе я хочу всего лишь определить структуру данных и нарисовать карту на экране. Примерно так оно должно выглядеть:



Внесённые изменения можно посмотреть тут. Там всё просто: я захардкодил карту в одномерный массив символов, определил функцию отрисовки прямоугольника, да прошёлся по карте, отрисовав каждую клеточку.

Напоминаю, что вот эта кнопка даст запустить код прямо на этом этапе:

Open in Gitpod



Этап 3: добавляем игрока


Что нам нужно, чтобы уметь нарисовать игрока на карте? GPS координат достаточно :)



Добавляем две переменные x и y, и отрисовываем игрока в соответствующем месте:



Внесённые изменения можно посмотреть тут. Про гитпод больше напоминать не буду :)

Open in Gitpod



Этап 4: виртуальный дальномер aka трассировка первого луча


Помимо координат игрока нам неплохо было бы ещё знать, в каком направлении он смотрит. Потому добавим ещё одну переменную player_a, которая даёт направление взгляда игрока (угол между направлением взгляда и осью абсцисс):



А теперь я хочу иметь возможность скользить вдоль оранжевого луча. Как это делать? Предельно просто. Давайте рассмотрим зелёный прямоугольный треугольник. Мы знаем, что cos(player_a) = a/c, и что sin(player_a) = b/c.



Что будет, если я произвольно возьму значение c (положительное) и посчитаю x = player_x + c*cos(player_a) и y = player_y + c*sin(player_a)? Мы окажемся в фиолетовой точке; варьируя параметр c от нуля до бесконечности, мы можем заставить скользить эту фиолетовую точку вдоль нашего оранжевого луча, причём c — это расстояние от (x,y) до (player_x, player_y)!

Сердце нашего графического движка — это вот такой цикл:

   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;
   }

Мы двигаем точку (x,y) вдоль луча, если она натыкается на препятствие на карте, то прерываем цикл, и переменная c даёт расстояние до препятствия! Чем не лазерный дальномер?



Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 5: сектор обзора


Один луч это прекрасно, но всё же наши глаза видят целый сектор. Давайте назовём угол обзора fov (field of view):



И выпустим 512 лучей (кстати, почему 512?), плавно заметая весь сектор обзора:


Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 6: 3Д!


А теперь ключевой момент. Для каждого из 512 лучей мы получили расстояние до ближайшего препятствия, так? А теперь давайте сделаем вторую картинку шириной (спойлер) 512 пикселей; в которой мы для каждого луча будем рисовать один вертикальный отрезок, причём высота отрезка обратно пропорциональна расстоянию до препятствия:



Ещё раз, это ключевой момент создания иллюзии 3Д, убедитесь, что вы понимаете, о чём идёт речь. Рисуя вертикальные отрезки, по факту, мы рисуем частокол, где высота каждого кола тем меньше, чем дальше он от нас находится:



Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 7: первая анимация


На этом этапе мы впервые рисуем что-то динамическое (я просто скидываю на диск 360 картинок). Всё тривиально: я изменяю player_a, отрисовываю картинку, сохраняю, изменяю player_a, отрисовываю, сохраняю. Чтобы было чуть веселее, я каждому типу клетки в нашей карте присвоил случайное значение цвета.


Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 8: коррекция «рыбьего глаза»


Вы обратили внимание, какой отличный эффект «рыбьего глаза» у нас получается, когда мы смотрим на стенку вблизи? Примерно вот так оно выглядит:



Почему? Да очень просто. Вот мы смотрим на стенку:



Для отрисовки нашей стены мы заметаем фиолетовым лучом наш синий сектор обзора. Возьмём конкретное значение направления луча, как на этой картинке. Длина оранжевого отрезка явно меньше длины фиолетового. Поскольку для определения высоты каждого вертикального отрезка, что мы рисуем на экране, мы делим на расстояние до преграды, рыбий глаз вполне закономерен.

Скорректировать это искажение совсем несложно, посмотрите, как это делается. Пожалуйста, убедитесь, что вы понимаете, откуда там взялся косинус. Нарисовать схему на листочке сильно помогает.



Open in Gitpod



Этап 9: загрузка файла текстур


Настало время разбираться с текстурами. Мне лениво самостоятельно писать загрузчик изображений, поэтому я взял прекрасную библиотеку stb. Я подготовил файл с текстурами для стен, все текстуры квадратные и упакованы в изображение по горизонтали:



На этом этапе я просто гружу текстуры в память. Чтобы проверить работоспособность написанного кода, просто рисую как есть текстуру с индексом 5 в левом верхнем углу экрана:


Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 10: рудиментарное использование текстур


Теперь я выкидываю случайно сгенерированные цвета и подкрашиваю мои стены, взяв левый верхний пиксель из соответствующей текстуры:


Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 11: текстурируем стены по-настоящему


А вот теперь настал долгожданный момент, когда мы наконец-то увидим кирпичные стены:



Основная идея очень простая: вот мы скользим вдоль текущего луча и останавливаемся в точке x,y. Давайте предположим, что мы остановились на «горизонтальной» стене, тогда y почти целочисленнен (не совсем, т.к. наш способ движения вдоль луча вносит небольшую ошибку). Давайте возьмём дробную часть от x и назовём её hitx. Дробная часть меньше единицы, следовательно, если мы умножим hitx на размер текстуры (у меня 64), то это нам даст столбец текстуры, который нужно нарисовать в этом месте. Осталось его растянуть до нужного размера и дело в шляпе:



В общем, идея крайне примитивная, но требует аккуратного исполнения, так как у нас есть ещё и «вертикальные» стены (те, у которых hitx будет близок к нулю [x целочисленный]). Для них столбец текстуры определяется hity, дробной частью от y. Внесённые изменения можно посмотреть тут.

Open in Gitpod



Этап 12: время рефакторить!


На этом этапе я ничего нового не стал делать, просто занялся генеральной уборкой. До сего момента у меня был один гигантский (185 строк!) файл, и в нём стало трудно работать. Поэтому я его разбил на тучу мелких, к сожалению, попутно почти удвоив размер кода (319 строк), не добавив никакой функциональности. Но зато стало гораздо удобнее пользоваться, например, чтобы сгенерировать анимацию, достаточно сделать вот такой цикл:

    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);
    }

Ну а вот результат:


Внесённые изменения можно посмотреть тут.

Open in Gitpod

Продолжение следует… незамедлительно


На этой оптимистичной ноте я заканчиваю текущую половину моей простыни, вторая половина доступна тут. В ней мы добавим монстров и слинкуемся с SDL2, чтобы можно было погулять в нашем виртуальном мире.
+74
24k 370
Comments 43
Similar
Top of the day