ROOM4DOOM: Stumbling through

It's been a long time since I last wrote a post here. This post is brought on by the Rust GameDev newsletter which this is going to be linked in (wow there are so many cool things being made!) - I'd like to provide a clearer and cleaner timeline of the progress of ROOM4DOOM than a twitter thread I did.

What is ROOM4DOOM?

A couple of years ago I had the bright idea of rewriting Doom in Rust. Why? I guess I wanted to write a game, but not really.. I wanted to write a complete game engine, and well, games require a ton of assets so why not try rewriting Doom? I'd have assets to work with, and an expected outcome with a comparison and validation. It'd also be fun and challenging for sure. At less than 25k lines it also seemed manageable (particularly as I wrote a 25k line mobile app in thee same year).

Incidentally Amro had begun writing a great little series of code-reviews and digests here which we struck up a friendship over. It's well worth a read as he does an excellent job of describing many things. We also created a discord server for rewriting id Software tech - it's not very active but we have some excellently talented members with their own unique projects going on (shoutout to erik and kevansevans).

What is this post?

Something of a step through of the brief history of this project. I had the foresight to save a lot of screenshots of my progress. Also interspersed with random tidbits of what I've done or learned, and some word salad at the end.

First steps

Please excuse the constant changing of appearance in screenshots. Pretty sure that's ADHD on display.

So it's the start of 2020, some months before there was a worldwide pandemic, and I'd written a basic wad parser-loader to get enough data to display E1M1:

All it is doing here is drawing the lines (and skipping some depending on the line flags). No sectors, subsectors, segments. All drawn with SDL2.

And then rather half-arsed drawing of subsectors. Mostly to attach a visual to my internal model of Doom:


Drawing the BSP node bounding boxes. Each node in the tree has a bounding box attached to it prividing the extents. It's a fast way to determine which side to traverse on the way to a point - each step down the tree is a smaller and smaller subset of nodes (check out chapter 59 onwards of Michael Abrash's Graphics Programming Black Book):


This is trying to show the search result as a path taken through the BSP (AABB get progressivel smaller since the are the extents of the nodes which get smaller with splitting). Keep in mind that this is showing only the successful side of a splitting line, not the unsuccessful sides that weren't traversed deeper.


At this point I began trying to clip the lines against the view. As you can see the lines behind the view were also being included (oops). It was also around then that I was trying to move from Dooms BAM (Binary Angles) system of angles to using full radians:


The below shows that I got it working... but offset 90:

And corrected. Doom does a lot of shortcuts in various places. Aside from the BAM use, most angles are translated to a 90 degree limit which is used also for actual screenspace drawing and clipping.


And so begins the leap to 2.5D. First I drew pretty much all lines in the view, no clipping against each other, and sort of transparent so I could get a feel for how things were represented.

Clipping came next naturally. Doom keeps track of which column of pixels has been drawn on screen and clips lines against this, adding the vertical extents of the column, along with keeping track of "portals" which are a line between a sector or subsector that is doublesided (not solid).

After this I took a break from the project for a year or so (2020-11-xx).


And came back with a vengence! 2022...

I started to re-evaluate what i was doing and what my goal was. Previously I wasn't that sure, and even at this point still wasn't, it kept evolving as I learned more. I decided that I was going to attempt to rewrite the C code as close as I could to Doom, which by now I was beginging to notice would be tricky because of a few things:

  • Doom manually manages memory, objects in that memory contain pointers to other objects, and the memory can be defragged (objects moved/compacted) and Doom updates the owners pointers
  • Thinkers are the thing that all world interaction uses, this struct and others that "contain" it are cast back and forward from each other

Anyway... visplanes were kind of started. This was very very basic clipping just to get wall-heights clipped. Planes were drawn in a solid colour.


Texturing was fun...


Because I'd made the decision to use floats instead of fixed-point I had a lot of small issues like this. The green is the window background showing through.

It wouldn't twig for me until later that the f32 as i32 casts weren't working the way I expected - I needed to .floor() things. Honestly it was months before it occured to me to do so. There are 4 ways to deal with conversion:

  • cast with as. This truncates the f32. A 4.51 ends up as 4.0, and -3.51 ends up as -3.0
  • .floor(). A 4.51 ends up as 4.0, and -3.51 ends up as -4.0
  • .ceil(). A 4.51 ends up as 5.0, and -3.51 ends up as -3.0
  • .round(). A 4.51 ends up as 5.0, and -3.51 ends up as -4.0

I also wasn't consistent, and wow did I use a lot of bad or weird casts (and yes I cleaned it all up a few weeks ago finally).

I thought this was correct, but it actually wasn't and wouldn't be corrected until much later.


Time to start drawing planes. I figured starting with the sky would be good, and a few false starts later I had this. Upper sky was good but weird issues down below.


Whatever was the issue above (I forget) it was corrected here and I drew the planes with a solid colour. However.... OFF-BY-ONE! You can see it as a black line on wall edges/ends.


Eventually everything was corrected, and the classic slime-trail appeared in the right place.


Texturing planes begins. This was.... tricky. None of the drawing code I wrote for sprites, walls, or planes is very close to the Doom code. My first attempt at the textures for planes resulted in sierpinski triangles - something I managed to do in about 20 less lines of code here than I used at university (LOL!).

Yeah this ain't right... I think the scale was incorrect

And success!

I love the aesthetics in Doom. While I was doing the textures I also implemented the zlight scales whcih map a light-level and distance to a colourmap.


Sprites. First issue was not terminating or joining columns correctly. Doom stores sprites as "spans" - Fabien Sanglard writes about this in his black book - it's a fascinating read.

Floating barrels.. Shoulda used fixed point.


Everything was starting to look good. But there was more to do...

Like transparency. This was actually really easy. Here the z-order was wrong, and corrected by using .rev() on the iterator. I laughed.

Reaching the end

Everything was coming along nicely. All through this time I was also implementing the gameplay stuff - this is a huge chunk of code for things like:

  • Thinkers: doors, platforms, lights, missiles, enemies
  • Shooting: BSP traversal and clipping
  • Various subsytems: HUD, statusbar, menus, intermission screens
  • Implementing a "multigen"
  • Sound

The multigen is a utility to generate the enemy states + info from a text file, it was something that made it easier for artists to set things up. There are quite a few versions floating around, and some are written in very obtuse C. What i wrote in the end is brute force and lazy - read in the file and work line-by-line using the string tools rust provides.

I solved the requirement for static memory locations of Thinkers by writing a custom allocation in the simplist way possible - aloocate a big block, set every location to a default value (and every item is part of a linked list):

pub struct Thinker {
    prev: *mut Thinker,
    next: *mut Thinker,
    data: ThinkerData,
    func: fn(&mut Self, &mut Level) -> bool,
}

pub enum ThinkerData {
    TestObject(TestObject),
    MapObject(MapObject),
    VerticalDoor(VerticalDoor),
    // etc
    /// The thinker function should set to this when the linked-list node
    /// and memory is no-longer required. On thinker run it will be set to
    /// `Free` and unlinked.
    Remove,
    /// Used to mark a `ThinkerAlloc` slot as free to be re-used.
    Free,
}

it's certainly still possible to get bad logic - and I sure did but it was an excellent learning experience - but it works and works pretty well, plus sticks reasonably close to the Doom code. Once I get demo playback in so I can evaluate more concretely how much ROOM4DOOM diverges from the Doom C and how future changes affect state (Doom is deterministic) I'll try different methods of Thinkers.

But still, linked lists bloody everywhere...


Floating point errors you say?

All of that is caused by the root cause being exacerabated the fact that the vertices stored in wads for maps are in actual fact integers. The original patch comment explains it best:

/// Remove slime trails. killough 10/98
///
// Slime trails are inherent to Doom's coordinate system -- i.e. there is
/// nothing that a node builder can do to prevent slime trails ALL of the time,
/// because it's a product of the integer coordinate system, and just because
/// two lines pass through exact integer coordinates, doesn't necessarily mean
/// that they will intersect at integer coordinates. Thus we must allow for
/// fractional coordinates if we are to be able to split segs with node lines,
/// as a node builder must do when creating a BSP tree.
///
/// A wad file does not allow fractional coordinates, so node builders are out
/// of luck except that they can try to limit the number of splits (they might
/// also be able to detect the degree of roundoff error and try to avoid splits
/// with a high degree of roundoff error). But we can use fractional coordinates
/// here, inside the engine. It's like the difference between square inches and
/// square miles, in terms of granularity.
///
/// For each vertex of every seg, check to see whether it's also a vertex of
/// the linedef associated with the seg (i.e, it's an endpoint). If it's not
/// an endpoint, and it wasn't already moved, move the vertex towards the
/// linedef by projecting it using the law of cosines. Formula:
///
/// ```ignore
///      2        2                         2        2
///    dx  x0 + dy  x1 + dx dy (y0 - y1)  dy  y0 + dx  y1 + dx dy (x0 - x1)
///   {---------------------------------, ---------------------------------}
///                  2     2                            2     2
///                dx  + dy                           dx  + dy
/// ```
///
/// (x0,y0) is the vertex being moved, and (x1,y1)-(x1+dx,y1+dy) is the
/// reference linedef.
///
/// Segs corresponding to orthogonal linedefs (exactly vertical or horizontal
/// linedefs), which comprise at least half of all linedefs in most wads, don't
/// need to be considered, because they almost never contribute to slime trails
/// (because then any roundoff error is parallel to the linedef, which doesn't
/// cause slime). Skipping simple orthogonal lines lets the code finish quicker.
///
/// Please note: This section of code is not interchangable with TeamTNT's
/// code which attempts to fix the same problem.
///
/// Firelines (TM) is a Rezistered Trademark of MBF Productions
fn fix_vertices(&mut self) {
    let start = Instant::now();
    let mut vertexes: HashMap<String, Vec2> = HashMap::with_capacity(self.segments.len() * 2);

    for seg in self.segments.iter_mut() {
        let linedef = seg.linedef.as_mut();
        // Commented this part out because cycles are now very very cheap
        // if linedef.delta.x != 0.0 && linedef.delta.y != 0.0 {
        let mut step2 = false;
        let mut vertex = &mut seg.v1;

        loop {
            if let Some(v) = vertexes.get_mut(&format!("{vertex}")) {
                vertex.x = v.x;
                vertex.y = v.y;
            } else {
                let dx2 = linedef.delta.x * linedef.delta.x;
                let dy2 = linedef.delta.y * linedef.delta.y;
                let dxy = linedef.delta.x * linedef.delta.y;
                let s = dx2 + dy2;
                let x0 = vertex.x;
                let y0 = vertex.y;
                let x1 = linedef.v1.x;
                let y1 = linedef.v1.y;
                vertex.x = (dx2 * x0 + dy2 * x1 + dxy * (y0 - y1)) / s;
                vertex.y = (dy2 * y0 + dx2 * y1 + dxy * (x0 - x1)) / s;
                vertexes.insert(format!("{vertex}"), *vertex);
            }

            if step2 {
                // Also set the v2 linedef
                // linedef.v2.x = vertex.x;
                // linedef.v2.y = vertex.y;
                break;
            }
            // Linedef are not used for rendering
            // linedef.v1.x = vertex.x;
            // linedef.v1.y = vertex.y;
            vertex = &mut seg.v2;
            step2 = true;
        }
        // }
    }

    let end = Instant::now();
    info!(
        "{}: Fixed map vertices, took: {:#?}",
        self.name,
        end.duration_since(start)
    );
}

some of the differences between the original and this version are that I've written it more verbosely, and I'm not particularly worried about the time it takes. ROOM4DOOM also stores vertices directly in linedefs and segments (so each have their own copy) - I will probably rewrite part of this so that a vertex that is meant to be shared will use the same translated vertex - I did do this using a hashmap but it was slow (because hash) and I didn't actually see any improvement graphically.


You could have told me this was an early Quake screenshot (during the time of static sky dragons) and I would have believed you.


The Doom screen wipe used M_Random to randomise the column falldown. The problem with it though is that before the wipe happens M_ClearRandom is called which resets both rndindex and prndindex, resulting in the same sequence every time. I changed it to never clear, and wrap.


Double-res and low-res! (640x400 and 320x200).

At some point I'll add widescreen mode also.

Where to?

Up above I mentioned divergence from the Doom C. What I mean by this is how much it diverges from the core gameplay, and how this affects playback of demos as Doom is deterministic with its fixed 35hz timestep, pseudo-random functions (0-255 values), and ticcmds (command packets for players/map object). You should be able to play back a sequence of ticcmds as input and end up in the same state on every build of the game. Thus, the change from fixed-point to floats makes me curious - I wonder how it affects end state of a demo play-back and how long it takes to affect it.

This ties in to one of the goals I eventually defined for the project - keep gameplay intact as close to original as possible, whcih also meant I kind of had to go with linked lists for book-keeping of Thinkers, although there are other solutions I wasn't sure what would fit until I'd learned the code insideout. Thinkers are linked to each-other, and also in a linked list within each subsector the thinker is in.

As such I eventully settled on a sort of architecture goal - something like a "separation of concerns" and started to try separate things out - ending up with:

  • Game exe: handles init, CLI options, config, starts the game
  • Game state: look at this as "is the game in menu, play, or demo?"
  • Gameplay: the core of what makes Doom, Doom.
  • Everything else as individual crates also: sound, renderer, statusbar, intermission, hud, menus etc. Most use a sort of API I settled on and extend that Gamestate implements

Gamestae and "everything else" need access to each other, but also need separation. Without the trait set as API you'd get crate dependency loops.

Gameplay crate is... a work in progress. Because everything was snowballed at the start I had to slowly peel away the public parts of it until I was left with a glob of public bits which I can now use as a base for building a decent API - the renderer needs access to certain things like the level data and player/map object locations. Objects/thinkers need to send sound requests to the sound server. Statusbars/huds need access to player stats (which they use through the Gamestate trait now).

And all through the code was/is littered with idiotic strings of casts to-from types (mostly cleaned up now) due to not really knowing the overview of a part until it's been read and written. Lots and lots of unsafe due to raw pointers (and maybe some UB?), I certainly do some crappy things in some locations like break a lifetime of a struct field apart from its owner with &mut *(&mut T as *mut T). Eventually I'll clean all that up. Those things exist due to the rust code being a transliteration of the Doom C in most places where suitable rust idioms weren't obvious until after the fact.

Fun project. Learned linked lists, allocations, and floats the hard way.

Performance compared to C

I know this is going to come up.

No. This is not a valid comparison.

Why not?

The Doom code is a product of its environment, and environment that has been preserved in code since the source was released in 1997. That environment is DOS on a 486 66Mhz with 4-8Mb of ram. The many optimizations Doom has are:

  • Tables upon tables. For example the trig tables like finetangent, finesine, finecosine, a table for screen to angle, and more.
  • BAM, binary angles.
  • Many shortcuts to avoid cross or dot product calculations
  • Fixed point arithmetic
  • others I'm not thinking of right now

I did away with all of that in this rewrite, and it was pretty hard work - some sections are nothing like Doom C. I also changed one rather lage thing: using BSP for collision, aim-lines, shoot etc instead of the blockmap. There are no uses of blockmap in this code at all.

As such it's just not fair to compare the performance to Doom C - it's a different pumpkin.

Is this code slow? Fuck no, not by a long shot. All the hot spots are in the renderer with the column drawing. Change the renderer to say, openGL, and it's another kettle of potatoes again. Where it really counts is the gameplay loop, which is pegged at 35hz so... And sound is on another thread altogether with channels for requests.

So much unsafe

I biggest thing I learned is.. so what about unsafe. It's a tool, and like any tool, you need to learn how to use it. I liken it to many things when I was a heavy fab (steelwork/structural) engineer: sure you can lift the guillotine safety cover up to precisely position that cut through an 8mm thick 2m wide plate of steel, but doing so comes with a contract; this guillotine didn't prevent cutting if the safety cover was up, so the obvious safety things applied, keep your damned hands clear or put the safety back down.

Unsafe in rust is like that. Use it to do something you can't typically do, but you must abide by the safety contract when it comes time to stamp that go-pedal and bring the blade down. Don't fear unsafe, instead, learn to use it and respect it.

But... yeah... I probably have do a run around of all the unsafe blocks and make sure I didn't leave some fingers behind by being careless.

And linked lists can be very useful, but hard.

Endnote

This was hard work. Repo here. Kind of documented here.

Please do keep in mind if you read the code that I: 1. ended up trying to transliterate C, which didn't really fit when it cam to arrays and pointers + the use of globals, and 2. it was hard to know the overall path blocks/chunks would take unless most of the meat of it was transliterated in the first place. There are definitely things to make folks look like they sucked on a lemon.

It's actually remarkable how similar a lot of blocks of code can be in many languages. The change usually comes down to context related to memory and access of said memory.

There's a lot to write about, and I hope to go in to more detail about many things at some point such as the Thinkers. The core of gameplay (enemy state machine), and some of the rendering. There's plenty of stuff I've missed commenting in this post because it doesn't quite fit, and while the graphical nature of it all makes for a compelling story, it misses so many of the internal details.

Until next time...