Rustenstein 3D: Game programming admire or not it’s 1992

Twice a yr, NextRoll celebrates Hack Week, the assign staff acquire to work for a week on a mission of their resolution. It’s an comely opportunity to experiment, be taught recent applied sciences and group up with of us from all the plot by the firm. You would possibly perchance perchance be taught all about Hack Week here.

As NextRoll an increasing selection of adopts the Rust programming language, it’s popular for engineers to exercise Hack Week as an opportunity to form ride with it. One other standard resolution is to work on video video games and, because it’s seemingly you’ll perchance also unbiased have guessed, we on a normal basis gaze them combined in Rust online game projects. Closing yr, a neighborhood of us worked on extending my rpg-cli game. This time, despite the indisputable fact that, we wanted to step it up a notch with a mission that would possibly perchance exercise about a of Rust’s strengths: low-stage programming, intense computations and C records interoperability. And so we made up our minds to port the everyday Wolfenstein 3D game to Rust.

identity Tool used to be renowned for pushing the envelope of PC game programming: first by implementing NES-admire side-scrollers on hardware that wasn’t ready for it, then practically inventing and dominating the 3D first-person shooter style, then making community and web multiplayer a actuality. Alongside the map, they additionally popularized the shareware distribution technique, encouraged community modding and open-sourced all of their hit titles. Masters of Doom by David Kushner tells the chronicle; Fabien Sanglard’s Game Engine sad books explains the technical critical points.

Perchance much less notorious than its successors Doom and Quake, Wolfenstein 3D is a astronomical milestone in identity Tool’s evolution and PC gaming in traditional. In addition, because its technology is more damaged-down, the source code is more approachable for request and implementation. The game doesn’t have a valid 3D engine but quite simulates a 3D world from a 2D design the exercise of a technique known as Ray Casting. The total drawing is performed by straight hanging pixels on the display.

Just a few years within the past, after studying the Wolfenstein sad e-book, I spent a whereas attempting to port it to Python, primarily based totally on any other recent port, wolf4sdl. I tried to remain as close as seemingly to the original source, which proved to be very tense, so I finally dropped the mission. Extra not too prolonged within the past, Mario Rugiero, who additionally read the e-book, proposed a Rust port as a mission for this Hack Week. A lot of of us jumped in, and so did I; even despite the indisputable fact that, primarily based totally on my previous ride, the endeavor unruffled regarded daunting: about a of us have been recent to Rust, some had by no map accomplished Wolf, some hadn’t read the e-book but, and none had implemented ray casting sooner than. We started without valuable hope of having one thing to existing by the terminate of the week, but we observed astronomical learning opportunities, so we dove valid in.

We roughly acknowledged some system of the game that will be tackled one at a time, so every member picked one and went to work on it:

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

In the cases the assign the output of one component used to be required as input for the subsequent, we former pre-parsed or tense-coded records, extracted from the reference wolf4py and wolf4sdl implementations: decompressed binary dumps of sources, hardcoded maps and partitions, etc. This allowed us to acquire growth in parallel.

Assets

The valuable assignment of porting the game is to read its records. Wolfenstein ships with a region of recordsdata for its a form of sources: graphics (images, textures and sprites), audio (music and sound results) and maps. One of the most complications is that every model of the game has a minute of a form of recordsdata, with a form of offsets and, in some cases, the exercise of a form of compression suggestions. For Rustenstein, we former the .WL1 recordsdata of the shareware model, which we included within the repository.

Every file makes exercise of a certain combination of quite loads of decompression algorithms, all of which we had to port to Rust:

• the primitive Huffman compression
• RLEW compression, a speed-length encoding algorithm that works on the observe stage
• a “Carmack” compression, which is John Carmack’s variant of the LZ (Lempel-Ziv) technique. Per the Sad Book, without valuable acquire admission to to the literature, Carmack would “acquire” an algorithm to later discover that any other person had performed it sooner than.

The long-established Wolf engine has a Memory Manager component to tackle reminiscence allocation and compacting (as a change of the primitive C malloc) along with a Page Manager to creep sources from disk to RAM. Every system are useless in recent hardware as we are able to safely decide that we are able to fit all sources in reminiscence, so we didn’t consist of them in our port.

Parsing and decompression code would possibly perchance unbiased additionally be chanced on here for maps, and here for the the leisure of the sources.

Maps

Wolfenstein 3D maps are defined as 64×64 grids of tiles. Every design has two layers of tiles: one for partitions and doorways, and any other to connect the participant, enemies, and bonus items. The a form of tile values settle what texture to render on partitions, what locks are required for doorways, what course the participant is facing, etc. All partitions have the equivalent height and since they’re represented as blocks within the tile grid, all intersections are rectangular; whereas this constrains the stage designs, it dramatically simplifies the ray casting algorithm for drawing the 3D world.

Below is the first design of the first episode, as considered in a Wolfenstein design editor:

And the equivalent design 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                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

Pixel drawing

For the graphic sources, decompressing and loading the records to reminiscence is correct half of the chronicle. The binary chunks that acquire every graphic (image, sprite or texture) are arranged explicitly for rapid rendering on the VGA displays the game used to be at the beginning designed for. This vogue that the graphics are rotated to be drawn in columns, and the columns themselves seem interleaved within the file since VGA allowed for parallel writing to four a form of video reminiscence banks.

Every byte within the graphic binary chunks is an index to the 256 color palette former in Wolfenstein 3D. The reference wolf4sdl implementation would write those chunks to an SDL flooring, which would, in flip, be translated to RGB colors sooner than being copied to the display, as described in this blog post. For the rationale that Rust bindings for SDL exercise a certain region of abstractions (and, in specific, they don’t repeat the SDL_ConvertPixels feature), we opted for converting from palette index to RGB colors on the flee, writing straight to an RGB texture that then will get copied to the renderable canvas. This vogue that the rendering routines ought to be adapted to jot down pink, inexperienced and blue bytes to accept as true with every pixel, as a change of the one palette index byte.

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;
}

The two graphic rendering routines we implemented have been straight ported from the wolf4py implementation, which in flip used to be ported nearly line by line from the wolf4sdl reference fork. The valuable routine handles showing a elephantine image straight to the display. Here is former for the title display along with the participant assign bar on the backside of the in-game peek:

fn draw_to_texture(texture:  &mut Texture, pic:  &Image, 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.records[source_index as usize];
                put_pixel(buffer, pitch, x, y, color_map[color as usize]);
            }
        }
    });
}

The 2d routine, a valuable more complex one, is accountable for drawing sprites and is at the moment former to repeat the participant weapon. A equivalent but valuable more advanced feature is left to be ported: the actual person that attracts scaled images resembling wall textures and enemy sprites.

It would possibly perchance most likely perchance be super to provide a decide to this implementation such that the bulk of the processing is performed as soon as as fragment of the asset loading step, and the binary chunks are saved in reminiscence, ready to be written to the display.

The connected code would possibly perchance unbiased additionally be chanced on here.

Ray Casting

On the coronary heart of the Wolfenstein 3D engine is the Ray Casting algorithm. This routine enables us to mission a 2D world (defined by the 64×64 tilemap) into a 3D peek, completely primarily based totally on 2D operations. The algorithm would possibly perchance unbiased additionally be summarized as follows:

1. Solid a ray from the participant’s most recent assign for every pixel column within the display width. To illustrate, the classical Wolfenstein 3D resolution is 320×200, so this implies casting 320 rays to plot a frame.
2. Prolong the ray in a course certain by the most recent horizontal pixel, the participant’s assign and its topic of peek, unless it hits a wall within the design. For the rationale that partitions are rectangular, the calculations to elongate the rays are vastly simplified, since there’s a relentless distance between a tile and the subsequent.
3. Once the ray intersects a wall, calculate the distance from the participant to that wall, the exercise of trigonometry.
4. Feature a height for the wall, inversely proportional to the calculated distance. Here is: the further the wall the ray hits is from the participant, the smaller the wall looks from the participant’s level of view (and the smaller the column of pixels we are able to want to plot on the display).

Below is a simplified JavaScript model of the algorithm, primarily based totally on this tutorial:

feature rayCasting(display, design, participant) {
  let precision = 64;
  let incrementAngle = participant.fieldOfView / display.width;

  let wallHeights = [];
  let rayAngle = participant.perspective - participant.fieldOfView / 2;
  for(let rayCount = 0; rayCount < display.width; rayCount++) {

    // originate the ray on the participant assign
    let ray = {
      x:  participant.x,
      y:  participant.y
    };

    // the ray moves at constant increments
    let rayCos = Math.cos(degreeToRadians(rayAngle)) / precision;
    let raySin = Math.sin(degreeToRadians(rayAngle)) / precision;

    // map the ray unless it finds a wall (a non zero tile)
    let wall = 0;
    whereas(wall == 0) {
      ray.x += rayCos;
      ray.y += raySin;
      wall = design[Math.floor(ray.y)][Math.floor(ray.x)];
    }

    // calculate the distance from the participant to the wall hit
    let distance = Math.sqrt(Math.pow(participant.x - ray.x, 2) + Math.pow(participant.y - ray.y, 2));

    // calculate height at most recent x inversely proportional to the distance
    wallHeights.push(Math.flooring(display.halfHeight / distance));

    // increment the perspective for the subsequent ray
    rayAngle += incrementAngle;
  }

  return wallHeights;
}

For a ray casting implementation closer to the original Wolfenstein 3D one, this collection of tutorials is instructed.

This routine used to be clearly the most not easy we tackled for the length of this Hack Week, but we made about a selections early on that lowered the complexity sufficient so as to ship one thing on time. First, we went with the most traditional model of the algorithm that supports partitions of solid colors as a change of textures. 2nd, Josh Burroughs realized ray casting one at a time, primarily based totally on tutorials, as a change of attempting to acquire a line-by-line port of the original Carmack implementation (which, quoting Sanglard, is a “fully-handcrafted 740 lines of extremely unorthodox and big efficient assembly code”) or its wolf4sdl counterpart (which is C but unruffled relied closely on goto statements and had a form of global side-results along with calculating wall heights).

Here’s what the tip-down peek of the first Wolf design regarded admire after integrating it into the ray casting routine:

The elephantine implementation would possibly perchance unbiased additionally be chanced on here.

World Rendering

The 3D world is displayed by first splitting the display horizontally in two halves, describe the upper half with a ceiling solid color and the decrease half with a flooring color. After that, a pixel column wants to be drawn with the height purchased from the ray casting algorithm for every horizontal coordinate. While the algorithm used to be unruffled in pattern, we tested the rendering code with tense-coded partitions:

Once the ray casting routine used to be implemented and fed with an accurate Wolfenstein design, we purchased an array of wall heights for every pixel column within the display, and we started to inspect the arena:

Although we haven’t implemented texture rendering, there are about a tricks that give a decide to the looks of the scene: the exercise of a form of colors for the horizontal and vertical faces of a wall, and making the r, g, b system of every pixel inversely proportional to the distance to the participant (which everybody is aware of from the height of the wall), to generate a darkness attain:

The world rendering code, then, looks admire this:

texture
 .with_lock(None, |buffer:  &mut [u8], pitch:  usize| {
     // plot flooring and ceiling colors
     let flooring = 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(flooring, y - vm, pix_center);
             put_pixel(buffer, pitch, x, y, floors);
         }
     }

     for x in 0..pix_width {
         // exercise a form of 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 most recent = min(ray_hits[x as usize].height, pix_center);
         color = darken_color(color, most recent, pix_center);

         for y in pix_center - most recent..pix_center + most recent {
             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 relate = lightness as f64 / max as f64 / DARKNESS;
    let rs = (r as f64 * relate) as u8;
    let gs = (g as f64 * relate) as u8;
    let bs = (b as f64 * relate) as u8;
    (rs, gs, bs)
}

A day sooner than the demo, we most productive had pieces of the game: asset loading wasn’t accomplished, we had existing-stopper bugs in design parsing and sprite rendering, and the ray casting engine used to be working in a 2D hardcoded design, prick aid loose the the leisure of the mission. In an wonderful few closing hours, all the pieces valid fell into assign: the bugs have been ironed out, the a form of system fit together and, with about a hacks and a form of grotesque code, we managed to connect together an spectacular-taking a inspect video, valid in time for the Hack Week demo session. We even had time to throw in a final-minute face animation of the character! The total ride actually reminded me of those reports about online game companies hanging together one-off builds in a urge, valid to acquire it to E3 demos.

Here is unruffled far from a functioning game, but it surpassed our most optimistic predictions from about a days sooner than. For the length of this week, we realized a blinding deal about Rust, and we went further than lets have if we have been working on our safe. And the mission ended up a hit the technical award of the match!

The prototype is now printed as open-source, even despite the indisputable fact that, as said, the code unruffled wants critical smooth-up. For the rationale that mission used to be a form of stress-free and, in this valuable week, we managed to resolve about a of the most not easy aspects (sources loading, ray casting, sprite and wall rendering), we’re enthusiastic to proceed working on it. Just some of the aspects that lets tackle next are:

• Rendering wall textures
• Point to and decide up items
• Add enemies to the design, put into effect wrestle and enemy AI
• Put in power doorways and keys
• Put in power push partitions