Дважды в год компания NextRoll организует мероприятие Hack Week, на котором сотрудники на неделю берутся за проект по своему выбору. Это превосходная возможность для экспериментов, изучения новых технологий и объединения с людьми из всех отделов компании. Узнать о Hack Week подробнее можно здесь.
Так как NextRoll всё активнее использует язык программирования Rust, на Hack Week инженеры обычно пытаются получить опыт работы с ним. Ещё одним популярным вариантом выбора является работа над видеоиграми, и, как вы уже могли догадаться, мы часто видим в проектах сочетание видеоигр и языка Rust.
В прошлом году группа сотрудников работала над развитием моей игры rpg-cli. На этот раз захотелось пойти дальше и взять проект, который показывает некоторые из сильных сторон Rust: низкоуровневым программированием, высоконагруженными вычислениями и операционной совместимостью данных с языком C. Поэтому мы решили портировать на Rust классическую игру Wolfenstein 3D.
Предыстория
id Software знаменита тем, что выжимает максимум из программирования игр для PC: сначала она реализовала сайдскроллеры в стиле NES на не предназначенном для них оборудовании, затем практически изобрела жанр трёхмерного шутера от первого лица и стала лидером в нём, а позже сделала реальностью сетевой и Интернет-мультиплеер. Параллельно эта компания популяризировала распространение ПО по методике shareware, вдохнула жизнь в любительский моддинг и выложила в открытый доступ исходный код всех своих хитовых игр. Об этой истории говорится в книге Masters of Doom Дэвида Кушнера; о технических подробностях рассказывается в серии Game Engine black books Фабьена Санглара.
Игра Wolfenstein 3D, менее известная, чем её потомки Doom и Quake, стала важным этапом в эволюции id Software и игр для PC в целом. Кроме того, из-за более примитивных технологий её исходный код лучше подходит для исследования и реализации. Игра не имеет реального 3D-движка, а симулирует 3D-мир из 2D-карты при помощи техники, называемой ray casting. Вся отрисовка выполняется непосредственным размещением пикселей на экране.
Прочитав несколько лет назад Wolfenstein black book, я попытался портировать игру на Python на основании другого современного порта wolf4sdl. Я стремился быть как можно ближе к исходникам оригинала, что оказалось очень сложно, поэтому со временем я забросил проект. Недавно Марио Ругиеро, тоже прочитавший книгу, предложил в качестве проекта на Hack Week сделать порт игры на Rust. К нему присоединилось множество людей, в том числе и я; однако по моему предыдущему опыту наша задача всё равно была пугающей: некоторые из нас были новичками в Rust, кто-то никогда не играл в Wolf, кто-то ещё не прочитал книгу, и никто из нас ранее не реализовывал ray casting. Мы начали, не надеясь получить что-то осязаемое к концу недели, но увидели в проекте огромные возможности для обучения, поэтому взялись за него.
Разработка
Мы приблизительно разбили игру на компоненты, с которыми можно было работать по отдельности, поэтому каждый участник команды выбрал свой и начал работу с ним:
- Распаковка и парсинг графических файлов.
- Распаковка, парсинг и интерпретация файлов карт.
- Манипуляции с графикой и рендеринг текстур при помощи SDL.
- Ray casting.
- Игровой цикл и управление вводом.
- Рендеринг мира.
В случаях, когда выходные данные компонента требовались в качестве входных данных для следующего компонента, мы использовали заранее обработанные или прописанные в коде данные, извлечённые из справочных реализаций wolf4py и wolf4sdl: распакованные двоичные дампы ресурсов, прописанные в коде карты и стены, и т. п. Это позволило нам работать параллельно.
Ресурсы
Первой задачей в портировании игры было считывание её данных. Wolfenstein имеет набор файлов с различными ресурсами: графикой (изображениями, текстурами и спрайтами), аудио (музыкой и звуковыми эффектами) и картами. Одна из сложностей заключалась в том, что в каждой версии игры файлы слегка различались, имели разные смещения, а в некоторых случаях и разные способы сжатия. Файлы .WL1 для Rustenstein мы взяли из shareware-версии [бесплатная неполная версия игры — прим. пер.] и добавили в репозиторий.
В каждом файле используется разная комбинация нескольких алгоритмов распаковки, и все эти алгоритмы нам нужно было портировать на Rust:
- Традиционное сжатие Хаффмана.
- Сжатие RLEW — алгоритм кодирования длин серий (run-length encoding), работающий на уровне слов.
- Сжатие «Кармака» — разработанный Джоном Кармаком вариант метода LZ (Лемпеля — Зива). Согласно Black Book, не имея доступа к литературе, Кармак «изобрёл» алгоритм, который, как выяснилось позже, был придуман другими.
Оригинальный движок Wolf имел компонент Memory Manager для управления распределением и сжатием памяти (вместо традиционного
malloc
языка C), а также Page Manager для перемещения ресурсов с диска в ОЗУ. На современном оборудовании оба компонента не нужны, так как мы можем считать, что все ресурсы поместятся в памяти, поэтому в наш порт эти компоненты не включены.Код парсинга и распаковки карт можно найти здесь, а для всех остальных ресурсов — здесь.
Карты
Карты Wolfenstein 3D описываются как сетка тайлов размером 64x64. Каждая карта содержит два слоя тайлов: один для стен и дверей, другой для размещения игрока, врагов и бонусов. Значения тайлов обозначают, какая текстура будет рендериться на стенах, какие замки требуются для дверей, куда смотрит игрок и т. д. Все стены имеют одинаковую высоту, и поскольку они представлены как блоки сетки тайлов, все они пересекаются под прямым углом; это сильно ограничивает дизайн уровней, зато значительно упрощает алгоритм рейкастинга для отрисовки 3D-мира.
Ниже показана первая карта первого эпизода такой, как она выглядит в редакторе карт Wolfenstein:
А вот та же карта в ASCII, выведенная нашим отладочным кодом:
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW WWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW WWWWWWWW W W WWWWWWWWWWWWWWWWWWWW
WWWWWW WWWWWWW | | W WWWWWWWWWWWWWWWWWWWW
WWWWWW WWWWWWW W W WWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWW WWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW WWW WWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW WWW WWWWWWWWWWWWW-WWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW W WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW | WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW W WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWW WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WW WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WWWWWW-WWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WWWWW WWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWWWWW
WW-WWWWWW WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WWWWW WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W W WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W W WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WWWWWW-WWWWWWWWWWWWWWWWWWWWWWW-WWWWWWWWWWWWWWWWWWWWWWWWWWWWW
W WW WWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWW WW
W WW WWWWWWWWWWWW WWWWWWWWWWWW WW
W WW WWWWWWWWWWWW WWWWWWWWWWWW WW
W W WWWWWWWWWWWW W W WW
W | WWWWWWWWWWWW | | WW
W W WWWWWWWWWWWW W W WW
W WW WWWWWWWWWWWW WWWW WWWW WW
W WW WWWWWWWWWWWW WWWWW WWWWW WW
W WW WWWWWWWWWWWWWWWWW WWWWWWWWWW WWWWW WW
W WWWWWW-WWWWWWWWWWWWWWWWWWWWWWW-WWWWWWWWWWWW WWWWWWW WW WWWW
W WWWWW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW WWWWWWWWWWWWWWW
W WWWWW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW WWWWWWWWWWWWWWW
W W W WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW WWWWWWWWWWWWWWW
W W WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW WWW W W W WWWWW
W W W WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW W WWWW
W WWWWW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW | WWWW
W WWWWW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW W WWWW
W W WWWWWWWWW WWWWWWWWWWWWWWWW W W W WWWWW
W | W WWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWW W W WWWWWWWWWWWWWW-WWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWW W W W WWWWWWWWW W W WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWW WWWWWWWWWWW | | WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW W W WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWW WWWWWWWWWWWWW W W WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWW WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW W W WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW P | | WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW W W WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
Отрисовка пикселей
Когда дело касается графических ресурсов, распаковка и загрузка данных в память — это только половина работы. Двоичные блоки, из которых состоит каждый графический элемент (изображение, спрайт или текстура) имеют структуру, предназначенную для быстрого рендеринга на VGA-дисплеях, для которых изначально была рассчитана игра. Это означает, что графика поворачивается для отрисовки в столбцах, а сами столбцы расположены в файле попеременно, поскольку стандарт VGA позволял параллельно записывать до четырёх банков видеопамяти.
Каждый байт в двоичных блоках графики является индексом 256-цветной палитры, используемой в Wolfenstein 3D. Справочная реализация wolf4sdl записывает эти блоки в на SDL-поверхность, которая в свою очередь перед копированием на экран преобразуется в цвета RGB. Подробнее см. в этом посте.
Так как привязки Rust для SDL используют другой набор абстракций (в частности, они не раскрывают функцию SDL_ConvertPixels), мы выбрали вариант преобразования индекса палитры в цвета RGB на лету, выполняя запись напрямую в RGB-текстуру, которая затем копируется на холст. Это означает, что процедуры рендеринга необходимо адаптировать для записи байтов красного, синего и зелёного вместо одного байта индекса палитры.
fn put_pixel(buffer: &mut [u8], pitch: usize, x: u32, y: u32, color: (u8, u8, u8)) {
let (r, g, b) = color;
let offset = y as usize * pitch + x as usize * 3;
buffer[offset] = r;
buffer[offset + 1] = g;
buffer[offset + 2] = b;
}
Две реализованные нами процедуры рендеринга графики были напрямую портированы из реализации wolf4py, которая, в свою очередь, почти построчно была портирована из справочного форка wolf4sdl. Первая процедура обрабатывает вывод полного изображения непосредственно на экран. Она используется для экрана заставки, а также для полосы состояния игрока в нижней части экрана в процессе игры:
fn draw_to_texture(texture: &mut Texture, pic: &Picture, color_map: ColorMap) {
texture.with_lock(None, |buffer: &mut [u8], pitch: usize| {
for y in 0..pic.height {
for x in 0..pic.width {
let source_index =
(y * (pic.width >> 2) + (x >> 2)) + (x & 3) * (pic.width >> 2) * pic.height;
let color = pic.data[source_index as usize];
put_pixel(buffer, pitch, x, y, color_map[color as usize]);
}
}
});
}
Вторая, гораздо более сложная процедура, выполняет отрисовку спрайтов и в настоящее время применяется для отображения оружия игрока. Осталось портировать похожую, но ещё более сложную функцию: отрисовывающую отмасштабированные изображения, например, текстуры стен и спрайты врагов.
В процессе разработки вместо оружия отобразился неожиданный спрайт
Желательно будет усовершенствовать эту реализацию так, чтобы основная часть обработки выполнялась один раз, как часть этапа загрузки ресурсов, а двоичные блоки хранились в памяти, готовые к записи на экран.
Соответствующий код находится здесь.
Ray casting
Фундаментом движка Wolfenstein 3D является алгоритм рейкастинга. Эта процедура позволяет нам проецировать 2D-мир (заданный в виде карты тайлов размером 64x64) в 3D-окно только на основании одних 2D-операций. Вкратце этот алгоритм можно описать так:
- Испускаем луч из текущей позиции игрока для каждого столбца пикселей ширины экрана. Например, классическое разрешение Wolfenstein 3D равно 320x200, так что для отрисовки кадра нужно испустить 320 лучей.
- Продлеваем луч в направлении, определяемом текущим горизонтальным пикселем, позицией игрока и его областью обзора, пока он не коснётся стены на карте. Так как стены прямоугольны, вычисления продлевания луча сильно упрощены, поскольку расстояние между тайлами одинаково.
- После пересечения луча со стеной вычисляем при помощи тригонометрии расстояние от игрока до этой стены.
- Задаём высоту стены, обратно пропорциональную вычисленному расстоянию. То есть, чем дальше от игрока находится стена, с которой столкнулся луч, тем меньше она кажется с точки зрения игрока (и тем меньше столбец пикселей, который нужно отрисовать на экране).
Ниже представлена упрощённая версия алгоритма на JavaScript, созданная на основе этого туториала:
function rayCasting(screen, map, player) {
let precision = 64;
let incrementAngle = player.fieldOfView / screen.width;
let wallHeights = [];
let rayAngle = player.angle - player.fieldOfView / 2;
for(let rayCount = 0; rayCount < screen.width; rayCount++) {
// испускаем луч из позиции игрока
let ray = {
x: player.x,
y: player.y
};
// луч движется с постоянными инкрементами
let rayCos = Math.cos(degreeToRadians(rayAngle)) / precision;
let raySin = Math.sin(degreeToRadians(rayAngle)) / precision;
// двигаем луч вперёд, пока он не найдёт стену (ненулевой тайл)
let wall = 0;
while(wall == 0) {
ray.x += rayCos;
ray.y += raySin;
wall = map[Math.floor(ray.y)][Math.floor(ray.x)];
}
// вычисляем расстояние от игрока до стены, которой коснулся луч
let distance = Math.sqrt(Math.pow(player.x - ray.x, 2) + Math.pow(player.y - ray.y, 2));
// вычисляем высоту в текущем x, обратно пропорциональную расстоянию
wallHeights.push(Math.floor(screen.halfHeight / distance));
// выполняем инкремент угла для следующего луча
rayAngle += incrementAngle;
}
return wallHeights;
}
Для изучения реализации рейкастинга, более близкой к алгоритму из Wolfenstein 3D, рекомендуется эта серия туториалов.
Эта процедура — самое сложное, что попалось в эту Hack Week. Но уже на ранних этапах мы заложили пару решений, которые помогли снизить сложность и успеть в срок хоть что-то. Во-первых, мы взялись за самую простую версию алгоритма, поддерживающую стены из сплошных цветов, а не из текстур. Во-вторых, Джош Берроуз разбирался с рейкастингом на основе туториалов, а не пытался создать построчный порт реализации Кармака (которая, по словам Санглара, является «полностью написанными вручную 740 строками крайне неординарного и сверхэффективного ассемблерного кода») или близнеца wolf4sdl (написанного на C, но всё равно активно использующего операторы
goto
и имеющего множество глобальных побочных эффектов наряду с вычислением высот стен).Вот как выглядела первая карта Wolf в виде сверху после её интеграции в процедуру рейкастинга:
Полную реализацию можно найти здесь.
Рендеринг мира
Отображение 3D-мира начинается с разделения экрана горизонтально на две части, верхняя половина раскрашивается в сплошной цвет потолка, а нижняя — в сплошной цвет пола. После этого нужно отрисовать столбец пикселей с высотой, полученной от алгоритма рейкастинга для каждой горизонтальной координаты. Пока продолжалась разработка алгоритма, мы тестировали код рендеринга при помощи прописанных в коде стен:
После того, как процедура рейкастинга была реализована и ей была передана реальная карта Wolfenstein, мы получили массив высот стен для каждого столбца пикселей на экране и начали видеть мир:
Хоть мы и не реализовали рендеринг текстур, есть пара трюков, улучшивших внешний вид сцены: использование разных цветов для горизонтальной и вертикальной граней стены и обратная пропорциональность компонентов r, g, b каждого пикселя к расстоянию до игрока (которое мы знали по высоте стены), создающая эффект темноты:
Код рендеринга мира выглядит следующим образом:
texture
.with_lock(None, |buffer: &mut [u8], pitch: usize| {
// рисуем цвета пола и потолка
let floor = color_map[VGA_FLOOR_COLOR];
let ceiling = color_map[VGA_CEILING_COLOR];
let vm = view_height / 6;
for x in 0..pix_width {
for y in 0..pix_height / 2 {
let ceilings = darken_color(ceiling, vm - y, pix_center);
put_pixel(buffer, pitch, x, y, ceilings);
}
for y in pix_height / 2..pix_height {
let floors = darken_color(floor, y - vm, pix_center);
put_pixel(buffer, pitch, x, y, floors);
}
}
for x in 0..pix_width {
// используем разные цвета для горизонтальных и вертикальных граней стен
let mut color = if ray_hits[x as usize].horizontal {
color_map[150]
} else {
color_map[155]
};
let current = min(ray_hits[x as usize].height, pix_center);
color = darken_color(color, current, pix_center);
for y in pix_center - current..pix_center + current {
put_pixel(buffer, pitch, x, y, color);
}
}
})
fn darken_color(color: (u8,u8,u8), lightness: u32, max: u32) -> (u8,u8,u8) {
let (r,g, b) = color;
let factor = lightness as f64 / max as f64 / DARKNESS;
let rs = (r as f64 * factor) as u8;
let gs = (g as f64 * factor) as u8;
let bs = (b as f64 * factor) as u8;
(rs, gs, bs)
}
Соединяем всё вместе
За день до демонстрации у нас имелись лишь части игры: не была готова загрузка ресурсов, мы нашли баги в парсинге карт и рендеринге спрайтов, из-за которых проект невозможно было показать, а движок рейкастинга работал с прописанной в коде 2D-картой, отдельной от остальной части проекта. За несколько потрясающих последних часов мы связали всё вместе: устранили баги, соединили разные компоненты, и благодаря нескольким хакам и куче уродливого кода нам удалось собрать впечатляющее видео как раз к моменту демонстраций на Hack Week. Нам даже хватило времени в последние минуты добавить анимацию лица персонажа! Этот процесс напомнил мне истории о видеоигровых компаниях, в спешке собирающих демо, чтобы успеть показать их на E3.
До работающей игры далеко, но мы не ожидали даже подобного результата всего за несколько дней работы. В течение этой недели мы довольно много узнали о Rust, и продвинулись дальше, чем если бы работали по одиночке. И в конечном итоге наш проект выиграл награду за техническое исполнение!
Теперь прототип выложен в open source, однако, как я сказал, код требует значительной чистки. Так как работать с проектом было очень интересно и за эту первую неделю мы смогли решить самые сложные задачи (загрузку ресурсов, рейкастинг, рендеринг спрайтов и стен), нам не терпится продолжить его. Вот некоторые из возможностей, которые мы хотели бы добавить следующими:
- Рендеринг текстур стен.
- Отображение и подбирание предметов.
- Добавление врагов на карту, реализация боя и ИИ врагов.
- Реализация дверей и ключей.
- Реализация толкаемых стен.