[Перевод] Rustenstein 3D: программируем, как будто сейчас 1992 год
Дважды в год компания 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 имеет набор файлов с различными ресурсами: графикой (изображениями, текстурами и спрайтами), аудио (музыкой и звуковыми эффектами) и картами. Одна из сложностей заключалась в том, что в каждой версии игры файлы слегка различались, имели разные смещения, а в некоторых случаях и разные способы сжатия. Для Rustenstein мы использовали файлы .WL1 из shareware-версии, которую мы добавили в свой репозиторий.
В каждом файле используется разная комбинация нескольких алгоритмов распаковки, и все эти алгоритмы нам нужно было портировать на Rust:
- Традиционное сжатие Хаффмана
- Сжатие RLEW — алгоритм кодирования длин серий (run-length encoding), работающий на уровне слов
- Сжатие «Кармака» — разработанный Джоном Кармаком вариант метода LZ (Лемпеля — Зива). Согласно Black Book, не имея доступа к литературе, Кармак «изобрёл» алгоритм, который, как выяснилось позже, был придуман другими.
Оригинальный движок Wolf имел компонент Memory Manager для управления распределением и сжатием памяти (вместо традиционного malloc языка C), а также Page Manager для перемещения ресурсов с диска в ОЗУ. На современном оборудовании оба компонента не нужны, так как мы можем считать, что все ресурсы поместятся в памяти, поэтому в наш порт эти компоненты не включены.
Код парсинга и распаковки карт можно найти здесь, а для всех остальных ресурсов — здесь.
Карты
Карты Wolfenstein 3D описываются как сетка тайлов размером 64×64. Каждая карта содержит два слоя тайлов: один для стен и дверей, другой для размещения игрока, врагов и бонусов. Значения тайлов обозначают, какая текстура будет рендериться на стенах, какие замки требуются для дверей, куда смотрит игрок и т. д. Все стены имеют одинаковую высоту, и поскольку они представлены как блоки сетки тайлов, все они пересекаются под прямым углом; это сильно ограничивает дизайн уровней, зато значительно упрощает алгоритм рейкастинга для отрисовки 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-мир (заданный в виде карты тайлов размером 64×64) в 3D-окно только на основании одних 2D-операций. Вкратце этот алгоритм можно описать так:
- Испускаем луч из текущей позиции игрока для каждого столбца пикселей ширины экрана. Например, классическое разрешение Wolfenstein 3D равно 320×200, так что для отрисовки кадра нужно испустить 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++) {
// start the ray at the player position
let ray = {
x: player.x,
y: player.y
};
// the ray moves at constant increments
let rayCos = Math.cos(degreeToRadians(rayAngle)) / precision;
let raySin = Math.sin(degreeToRadians(rayAngle)) / precision;
// advance the ray until it finds a wall (a non zero tile)
let wall = 0;
while(wall == 0) {
ray.x += rayCos;
ray.y += raySin;
wall = map[Math.floor(ray.y)][Math.floor(ray.x)];
}
// calculate the distance from the player to the wall hit
let distance = Math.sqrt(Math.pow(player.x - ray.x, 2) + Math.pow(player.y - ray.y, 2));
// calculate height at current x inversely proportional to the distance
wallHeights.push(Math.floor(screen.halfHeight / distance));
// increment the angle for the next ray
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| {
// draw floor and ceiling colors
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 {
// use different colors for horizontal and vertical wall faces
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, однако, как я сказал, код требует значительной чистки. Так как работать с проектом было очень интересно и за эту первую неделю мы смогли решить самые сложные задачи (загрузку ресурсов, рейкастинг, рендеринг спрайтов и стен), нам не терпится продолжить его. Вот некоторые из возможностей, которые мы хотели бы добавить следующими:
- Рендеринг текстур стен
- Отображение и подбирание предметов
- Добавление врагов на карту, реализация боя и ИИ врагов
- Реализация дверей и ключей
- Реализация толкаемых дверей
