Twice a year, NextRoll celebrates Hack Week, where employees get to work for a week on a project of their choice. It’s an excellent opportunity to experiment, learn new technologies and team up with people from across the company. You can learn all about Hack Week here.

As NextRoll increasingly adopts the Rust programming language, it’s common for engineers to use Hack Week as an opportunity to gain experience with it. Another popular choice is to work on video games and, as you may have guessed, we frequently see them combined in Rust video game projects. Last year, a group of us worked on extending my rpg-cli game. This time, though, we wanted to step it up a notch with a project that would exercise some of Rust’s strengths: low-level programming, intense computations and C data interoperability. And so we decided to port the classic Wolfenstein 3D game to Rust.

id Software was famous for pushing the envelope of PC game programming: first by implementing NES-like side-scrollers on hardware that wasn’t prepared for it, then practically inventing and dominating the 3D first-person shooter genre, then making network and internet multiplayer a reality. Along the way, they also popularized the shareware distribution method, encouraged community modding and open-sourced all of their hit titles. Masters of Doom by David Kushner tells the story; Fabien Sanglard’s Game Engine black books explains the technical details.

Perhaps less notorious than its successors Doom and Quake, Wolfenstein 3D is a big milestone in id Software’s evolution and PC gaming in general. In addition, because its technology is more primitive, the source code is more approachable for study and implementation. The game doesn’t have a real 3D engine but rather simulates a 3D world from a 2D map using a technique called Ray Casting. All the drawing is done by directly putting pixels on the screen.

A few years ago, after reading the Wolfenstein black book, I spent some time trying to port it to Python, based on another modern port, wolf4sdl. I tried to remain as close as possible to the original source, which proved to be very difficult, so I eventually dropped the project. More recently, Mario Rugiero, who also read the book, proposed a Rust port as a project for this Hack Week. Several people jumped in, and so did I; although, based on my previous experience, the enterprise still seemed daunting: some of us were new to Rust, some had never played Wolf, some hadn’t read the book yet, and none had implemented ray casting before. We started without much hope of having something to show by the end of the week, but we saw enormous learning opportunities, so we dove right in.

We roughly identified some components of the game that could be tackled separately, so each member picked one and went to work on it:

• graphic files decompression and parsing
• map files decompression, parsing and interpretation
• SDL graphic manipulation and texture rendering
• ray casting
• game loop and input management
• world rendering

In the cases where the output of one component was required as input for the next, we used pre-parsed or hard-coded data, extracted from the reference wolf4py and wolf4sdl implementations: decompressed binary dumps of assets, hardcoded maps and walls, etc. This allowed us to make progress in parallel.

Assets

The first task of porting the game is to read its data. Wolfenstein ships with a set of files for its different assets: graphics (images, textures and sprites), audio (music and sound effects) and maps. One of the complications is that each version of the game has slightly different files, with different offsets and, in some cases, using different compression methods. For Rustenstein, we used the .WL1 files of the shareware version, which we included in the repository.

Each file uses a different combination of several decompression algorithms, all of which we had to port to Rust:

• the traditional Huffman compression
• RLEW compression, a run-length encoding algorithm that works at the word level
• a “Carmack” compression, which is John Carmack’s variant of the LZ (Lempel-Ziv) method. According to the Black Book, without much access to the literature, Carmack would “invent” an algorithm to later find out that someone else had done it before.

The original Wolf engine has a Memory Manager component to handle memory allocation and compacting (instead of the traditional C malloc) as well as a Page Manager to move assets from disk to RAM. Both components are unnecessary in modern hardware as we can safely assume that we can fit all assets in memory, so we did not include them in our port.

Parsing and decompression code can be found here for maps, and here for the rest of the assets.

Maps

Wolfenstein 3D maps are defined as 64×64 grids of tiles. Each map has two layers of tiles: one for walls and doors, and another to place the player, enemies, and bonus items. The different tile values determine what texture to render on walls, what locks are required for doors, what direction the player is facing, etc. All walls have the same height and since they are represented as blocks in the tile grid, all intersections are rectangular; while this constrains the level designs, it dramatically simplifies the ray casting algorithm for drawing the 3D world.

Below is the first map of the first episode, as seen in a Wolfenstein map editor:

And the same map as ASCII, as printed by our debugging code:

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