Дважды в год компания 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-операций. Вкратце этот алгоритм можно описать так:

1. Испускаем луч из текущей позиции игрока для каждого столбца пикселей ширины экрана. Например, классическое разрешение Wolfenstein 3D равно 320×200, так что для отрисовки кадра нужно испустить 320 лучей.
2. Продлеваем луч в направлении, определяемом текущим горизонтальным пикселем, позицией игрока и его областью обзора, пока он не коснётся стены на карте. Так как стены прямоугольны, вычисления продлевания луча сильно упрощены, поскольку расстояние между тайлами одинаково.
3. После пересечения луча со стеной вычисляем при помощи тригонометрии расстояние от игрока до этой стены.
4. Задаём высоту стены, обратно пропорциональную вычисленному расстоянию. То есть, чем дальше от игрока находится стена, с которой столкнулся луч, тем меньше она кажется с точки зрения игрока (и тем меньше столбец пикселей, который нужно отрисовать на экране).

Ниже представлена упрощённая версия алгоритма на 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, однако, как я сказал, код требует значительной чистки. Так как работать с проектом было очень интересно и за эту первую неделю мы смогли решить самые сложные задачи (загрузку ресурсов, рейкастинг, рендеринг спрайтов и стен), нам не терпится продолжить его. Вот некоторые из возможностей, которые мы хотели бы добавить следующими:

• Рендеринг текстур стен
• Отображение и подбирание предметов
• Добавление врагов на карту, реализация боя и ИИ врагов
• Реализация дверей и ключей
• Реализация толкаемых дверей