Пишем шутер от первого лица в консоли! Как работает псевдо-3d графика в играх? #1

Пишем шутер от первого лица в консоли! Как работает псевдо-3d графика в играх? #1

Как работает псевдо-3D графика в старых играх? Пишем на C++ консольную игру шутер от первого лица, используя метод «бросания лучей» (Ray casting).

Сегодня я расскажу о том, как можно написать шутер от первого лица, используя псевдо-3D графику. Такая графика повсеместно использовалась в старых игрушках типа Wolfenstein 3D, Doom, Doom II и др.
Вдохновлением для написания данной статьи стал видеоролик Code-It-Yourself! First Person Shooter (Quick and Simple C++) с YouTube канала OneLoneCoder. Мне настолько понравилась идея и простота её реализации, что я просто не мог сдержаться, чтобы не рассказать о ней!
На моём YouTube канале есть видео с наглядными объяснениями этой темы:



Как выглядела Wolfenstein 3D:





А вот, что мы получим в итоге:




Можно ожидать, что для написания чего то подобного понадобятся тысячи строчек кода и недели работы, но эта программа содержит всего 180 строчек кода!
Я не буду много останавливаться на коде и углубляться в детали программирования, а только попытаюсь объяснить основную идею и показать результаты. На GitHub'e автора кода есть все исходники.

Вывод в консоль


Начнём с того, что просто создадим необходимые переменные:



int nScreenWidth = 120; // Ширина консольного окна
int nScreenHeight = 40; // Высота консольного окна

float fPlayerX = 1.0f; // Координата игрока по оси X
float fPlayerY = 1.0f; // Координата игрока по оси Y
float fPlayerA = 0.0f; // Направление игрока

int nMapHeight = 16; // Высота игрового поля
int nMapWidth = 16; // Ширина игрового поля

float fFOV = 3.14159 / 3; // Угол обзора (поле видимости)
float fDepth = 30.0f; // Максимальная дистанция обзора


Для вывода текста на экран мы не будем использовать стандартную функцию cout, ведь она слишком медленная. Вместо этого будет использоваться следующая конструкция:



wchar_t *screen = new wchar_t[nScreenWidth*nScreenHeight + 1]; // Массив для записи в буфер
HANDLE hConsole = CreateConsoleScreenBuffer(GENERIC_READ | GENERIC_WRITE, 0, NULL, CONSOLE_TEXTMODE_BUFFER, NULL); // Буфер экрана
SetConsoleActiveScreenBuffer(hConsole); // Настройка консоли
DWORD dwBytesWritten = 0; // Для дебага

screen[nScreenWidth * nScreenHeight] = '\0'; // Последний символ - окончание строки
WriteConsoleOutputCharacter(hConsole, screen, nScreenWidth * nScreenHeight, { 0, 0 }, &dwBytesWritten); // Запись в буфер

Это просто метод вывода, поэтому на нем сильно не останавливаемся.
Теперь все готово к написанию кода. Игровую карту мы будем хранить в виде двумерного массива. Решётка будет означать стену, а точка - пустое пространство:



wstring map; // Строковый массив
map += L"################";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"################";

Вдумчивый читатель может заметить, что это же никакое не 3D, и будет абсолютно прав. Третьего измерения не будет, но мы создадим его иллюзию.

Вернёмся к написанию алгоритма. Игровой цикл и вся заготовка будет выглядеть так:



using namespace std;
#include <iostream>
#include <Windows.h>

int nScreenWidth = 120; // Ширина консольного окна
int nScreenHeight = 40; // Высота консольного окна

float fPlayerX = 1.0f; // Координата игрока по оси X
float fPlayerY = 1.0f; // Координата игрока по оси Y
float fPlayerA = 0.0f; // Направление игрока

int nMapHeight = 16; // Высота игрового поля
int nMapWidth = 16; // Ширина игрового поля

float fFOV = 3.14159 / 3; // Угол обзора (поле видимости)
float fDepth = 30.0f; // Максимальная дистанция обзора

int main()
{
wchar_t *screen = new wchar_t[nScreenWidth*nScreenHeight + 1]; // Массив для записи в буфер
HANDLE hConsole = CreateConsoleScreenBuffer(GENERIC_READ | GENERIC_WRITE, 0, NULL, CONSOLE_TEXTMODE_BUFFER, NULL); // Буфер экрана
SetConsoleActiveScreenBuffer(hConsole); // Настройка консоли
DWORD dwBytesWritten = 0; // Для дебага

wstring map; // Строковый массив
map += L"################";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"#..............#";
map += L"################";

while (1) // Игровой цикл
{
// Повторяющиеся действия
}
return 0;
}


Мы будем строить изображение в два цикла, изменяя во внешнем цикле координату по \(X\), а во внутреннем - по \(Y\).
Напомню, что в консоли, как и полагается, вывод текста происходит слева направо с переносом вниз. Так что координатная сетка будет выглядеть следующим образом:




Управление


У нас будут две степени свободы: движение вперёд-назад и поворот.
Реализовать изменение этих параметров не составляет никакого труда:



auto tp1 = chrono::system_clock::now(); // Переменные для подсчета
auto tp2 = chrono::system_clock::now(); // пройденного времени

while (1) // Игровой цикл
{
tp2 = chrono::system_clock::now();
chrono::duration <float> elapsedTime = tp2 - tp1;
tp1 = tp2;
float fElapsedTime = elapsedTime.count();

if (GetAsyncKeyState((unsigned short)'A') & 0x8000)
fPlayerA -= (1.5f) * fElapsedTime; // Клавишей "A" поворачиваем по часовой стрелке

if (GetAsyncKeyState((unsigned short)'D') & 0x8000)
fPlayerA += (1.5f) * fElapsedTime; // Клавишей "D" поворачиваем против часовой стрелки

if (GetAsyncKeyState((unsigned short)'W') & 0x8000) // Клавишей "W" идём вперёд
{
fPlayerX += sinf(fPlayerA) * 5.0f * fElapsedTime;
fPlayerY += cosf(fPlayerA) * 5.0f * fElapsedTime;

if (map[(int)fPlayerY*nMapWidth + (int)fPlayerX] == '#') { // Если столкнулись со стеной, но откатываем шаг
fPlayerX -= sinf(fPlayerA) * 5.0f * fElapsedTime;
fPlayerY -= cosf(fPlayerA) * 5.0f * fElapsedTime;
}
}

if (GetAsyncKeyState((unsigned short)'S') & 0x8000) // Клавишей "S" идём назад
{
fPlayerX -= sinf(fPlayerA) * 5.0f * fElapsedTime;
fPlayerY -= cosf(fPlayerA) * 5.0f * fElapsedTime;
if (map[(int)fPlayerY*nMapWidth + (int)fPlayerX] == '#') { // Если столкнулись со стеной, но откатываем шаг
fPlayerX += sinf(fPlayerA) * 5.0f * fElapsedTime;
fPlayerY += cosf(fPlayerA) * 5.0f * fElapsedTime;
}
}

// Повторяющиеся действия
}


Ray casting


Мы будем строить изображение в два цикла, изменяя во внешнем цикле координату по \(X\), а во внутреннем - по \(Y\).
Для того, чтобы построить часть изображения - вертикальную полоску на экране, нужно найти расстояние от наблюдателя до предмета, который попадет в эту полоску.
У наблюдателя есть некоторый угол обзора \(\theta\), в который могут попасть предметы. Расстояние до них мы и будем пытаться найти:



Расстояние до стены будем искать итерационно: в начале мы имеем направление в котором хотим проверить наличие препятствия, после этого мы циклично, небольшими шагами идем в этом направлении. В конце концов возможно два результата: либо луч столкнулся с препятствием, либо он отправился в бесконечное путешествие.




Чтобы не попадать в бесконечный цикл нужно ограничить радиус видимости. Если стенка не попала в радиус видимости, то мы будем воспринимать это как отсутствие препятствия в данном направлении.

Чем дальше находится стенка, тем меньше места она должна занимать на экране и тем больше места будут занимать небо и земля.
Такой метод определения расстояния до предмета в заданном направлении называется методом «бросания лучей» (Ray casting).
В статье на Википедии есть иллюстрация применения такого метода:



Для построения изображения наблюдатель пускает лучи с некоторым шагом, проходя по всему углу обзора. Направление луча для построения конкретной полоски на экране находится исходя из того, что за весь проход по оси \(X\) экрана нужно полностью пройти угол обзора \(\theta\). Угол обзора - это то, что помещается в ширину экрана:



for (int x = 0; x < nScreenWidth; x++) // Проходим по всем X
{
float fRayAngle = (fPlayerA - fFOV/2.0f) + ((float)x / (float)nScreenWidth) * fFOV; // Направление луча
// Находим расстояние до стенки в направлении fRayAngle

float fDistanceToWall = 0.0f; // Расстояние до препятствия в направлении fRayAngle
bool bHitWall = false; // Достигнул ли луч стенку

float fEyeX = sinf(fRayAngle); // Координаты единичного вектора fRayAngle
float fEyeY = cosf(fRayAngle);

while (!bHitWall && fDistanceToWall < fDepth) // Пока не столкнулись со стеной
{ // Или не вышли за радиус видимости
fDistanceToWall += 0.1f;

int nTestX = (int)(fPlayerX + fEyeX*fDistanceToWall); // Точка на игровом поле
int nTestY = (int)(fPlayerY + fEyeY*fDistanceToWall); // в которую попал луч

if (nTestX < 0 || nTestX >= nMapWidth || nTestY < 0 || nTestY >= nMapHeight)
{ // Если мы вышли за зону
bHitWall = true;
fDistanceToWall = fDepth;
}
else if (map[nTestY*nMapWidth + nTestX] == '#')
bHitWall = true;

for (int y = 0; y < nScreenHeight; y++) // При заданном X проходим по всем Y
{
// В этом цикле рисуется вертикальная полоска
}
}


По сути, у нас теперь есть все для того, чтобы создать иллюзию 3D. Имея расстояние \(d\) до стенки в данном направлении, мы можем вычислить её высоту относительно экрана. Как это сделать? Нужно понять как изменяется относительная высота объектов при изменении расстояния до них:




Из подобия треугольников сразу получаем зависимость относительной высоты кота от расстояния до него. Мы строим проекцию в точку (глаз), при которой мы получаем перспективу:




Видно, что если расстояние \(d\) равно \(d'\), высота кота относительно экрана равна его "настоящей" высоте. То есть расстояние \(d'\), на котором находится экран от наблюдателя - это расстояние на котором размеры объектов не искажаются.
Для отрисовки полоски нужно задать две координаты по Y: первая - это координата, где начинается стенка и заканчивается небо (идем сверху вниз и сначала прорисовываем небо), а вторая указывает, где заканчивается стенка и начинается пол.
Сделаем эти две точки симметричными относительно центра по высоте, задав их следующими формулами:
$$
y_1 = \frac{h'}{2}\left(1-\frac{1}{d}\right) \qquad (1)
$$
$$
y_2 = \frac{h'}{2}\left(1+\frac{1}{d}\right) \qquad (2)
$$
Видно, что если расстояние \(d\) до стенки становится большим, то эти точки сходятся в центр и высота полоски становится маленькой. То есть небо и пол занимают почти все место.
Если расстояние становится маленьким, то эти точки уходят вниз и полоска увеличивается. Легко убедиться, что формулы (1) и (2) задают размер стенки, как и положено, обратно пропорциональным расстоянию до неё. Действительно:
$$
b'=h' - 2\frac{h'}{2}(1-\frac{1}{d}) = \frac{h'}{d}
$$
То есть размер стенки в данном случае равен размеру экрана, а экран расположен на расстоянии 1 метр от наблюдателя.




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



Теперь подробно разберём, как реализовать это:



for (int x = 0; x < nScreenWidth; x++) // Проходим по всем X
{
float fRayAngle = (fPlayerA - fFOV/2.0f) + ((float)x / (float)nScreenWidth) * fFOV; // Направление луча

float fDistanceToWall = 0.0f; // Расстояние до препятствия в направлении fRayAngle
bool bHitWall = false; // Достигнул ли луч стенку

float fEyeX = sinf(fRayAngle); // Координаты единичного вектора fRayAngle
float fEyeY = cosf(fRayAngle);

while (!bHitWall && fDistanceToWall < fDepth) // Пока не столкнулись со стеной
{ // Или не вышли за радиус видимости
fDistanceToWall += 0.1f;

int nTestX = (int)(fPlayerX + fEyeX*fDistanceToWall); // Точка на игровом поле
int nTestY = (int)(fPlayerY + fEyeY*fDistanceToWall); // в которую попал луч

if (nTestX < 0 || nTestX >= nMapWidth || nTestY < 0 || nTestY >= nMapHeight)
{ // Если мы вышли за карту, то дальше смотреть нет смысла - фиксируем соударение на расстоянии видимости
bHitWall = true;
fDistanceToWall = fDepth;
}
else if (map[nTestY*nMapWidth + nTestX] == '#')
{ // Если встретили стену, то заканчиваем цикл
bHitWall = true;
}
}

//Вычисляем координаты начала и конца стенки по формулам (1) и (2)
int nCeiling = (float)(nScreenHeight/2.0) - nScreenHeight / ((float)fDistanceToWall);
int nFloor = nScreenHeight - nCeiling;

short nShade;

if (fDistanceToWall <= fDepth / 3.0f) nShade = 0x2588; // Если стенка близко, то рисуем
else if (fDistanceToWall < fDepth / 2.0f) nShade = 0x2593; // светлую полоску
else if (fDistanceToWall < fDepth / 1.5f) nShade = 0x2592; // Для отдалённых участков
else if (fDistanceToWall < fDepth) nShade = 0x2591; // рисуем более темную
else nShade = ' ';

for (int y = 0; y < nScreenHeight; y++)
{
if (y <= nCeiling)
screen[y*nScreenWidth + x] = ' ';
else if(y > nCeiling && y <= nFloor)
screen[y*nScreenWidth + x] = nShade;
else
{
// То же самое с полом - более близкие части рисуем более заметными символами
float b = 1.0f - ((float)y - nScreenHeight / 2.0) / ((float)nScreenHeight / 2.0);
if (b < 0.25) nShade = '#';
else if (b < 0.5) nShade = 'x';
else if (b < 0.75) nShade = '~';
else if (b < 0.9) nShade = '-';
else nShade = ' ';

screen[y*nScreenWidth + x] = nShade;
}
}
}


На выходе получается достаточно красиво:




Отображение рёбер


Выглядит наша программа уже неплохо, но ориентироваться по карте всё равно тяжело. Хорошо бы добавить отображение рёбер стен.
Но как мы поймем, что смотрим именно на ребро? Если мы определили, что произошло столкновение со стеной, то мы сразу же можем (точно) определить её местоположение, а значит и местоположение её четырёх рёбер.
То есть у нас есть четыре вектора, которые направлены от наблюдателя точно в рёбра стенки. Если угол между испускаемым лучом и одним из этих векторов становится маленьким, то мы будем воспринимать эту часть стенки за ребро и рисовать её другим символом:




Минимальный угол между двумя единичными векторами достигается при их максимальном скалярном произведении. Мы будем искать скалярное произведение между единичным вектором направления и единичными векторами, ведущими в рёбра стенки:



vector <pair <float, float>> p;

for (int tx = 0; tx < 2; tx++)
for (int ty = 0; ty < 2; ty++) // Проходим по всем 4м рёбрам
{
float vx = (float)nTestX + tx - fPlayerX; // Координаты вектора,
float vy = (float)nTestY + ty - fPlayerY; // ведущего из наблюдателя в ребро
float d = sqrt(vx*vx + vy*vy); // Модуль этого вектора
float dot = (fEyeX*vx / d) + (fEyeY*vy / d); // Скалярное произведение (единичных векторов)
p.push_back(make_pair(d, dot)); // Сохраняем результат в массив
}
// Мы будем выводить два ближайших ребра, поэтому сортируем их по модулю вектора ребра
sort(p.begin(), p.end(), [](const pair <float, float> &left, const pair <float, float> &right) {return left.first < right.first; });

float fBound = 0.005; // Угол, при котором начинаем различать ребро.
if (acos(p.at(0).second) < fBound) bBoundary = true;
if (acos(p.at(1).second) < fBound) bBoundary = true;


Если флаг bBoundary принимает значение true, то мы печатаем вертикальную черту вместо стенки.
Теперь мы можем видеть границы стен:




Получилась вполне себе сносная бродилка времен 90x.
Исходники, как я уже говорил выше, вы можете найти на GitHub'e автора кода.
Если данная статья вам понравилась, то поделитесь ею с друзьями или оставьте комментарий - мне будет очень приятно С:
Скорее всего я напишу вторую часть, в которой расскажу о том, как можно сильно улучшить данный результат и сделать настоящий шутер!


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







Если у вас остались вопросы или пожелания, то вы можете оставить комментарий (регистрироваться не нужно)

Анонимно:

Хорошо


Дата: 26-05-2019 в 13:54

Анонимно:

Ждём продолжения. Если можно, то хотелось бы на самом примитивном уровне объяснений отрисовки (и её реализации), на своём примере с единичными объектами.


Дата: 03-08-2019 в 11:59

Анонимно:

Тибу бы, заняться робетгутством и учить людей программированию бесплатно. )))
--------------------------------------------
Бесплатно бы я не хотел работать :)


Дата: 02-10-2019 в 09:14

Егорка:

Обидно что у тебя мало подписчиков и просмотров, ведь то что ты делаешь очень интересно особенно про илюзию 3d и про платы очень надеюсь что ты и далешь будешь снимать подобного рода вещи
------------------------------------------
Пока есть вы, люди, которым это интересно, я буду дальше стараться для вас :)


Дата: 05-10-2019 в 19:27


Для будущих авторов | 12.10.18: Если вы хотите стать автором статей на сайте и получить подтвержденный аккаунт, то обращайтесь на почту! support@ilinblog.ru

Обновления | 21.08.18: Добавлена возможность комментировать статьи. Сайт адаптирован под мобильные устройства.

Обновления | 19.01.18: Добавлена возможность добавления математических формул в статьи посредством языка latex. Пример использования тут. Также добавлена возможность редактирования статей.

Информация о пользователях | 28.10.17: Расширена функциональность страницы пользователей, теперь можно добавить статус и личную информацию.

Обновления | 30.08.17: С недавнего времени появилась возможность создавать свои собственные публикации, которые будут отображаться на странице пользователя. Авторы будут иметь возможность создавать посты на главную страницу сайта.



500
800
65
88