Building an Engine, Part 2: Two Decisions

2026-10-03

VolythEngine has grown a lot since the last post. It has doors, lifts, water, monsters, a console, map scripting, and an editor that can actually build levels now. Rather than list all of it, I want to dig into two decisions, one in the engine and one in the editor. Both came down to the same question: what did Quake do here, and do I actually want that?

As in Part 1, Claude writes most of the code, and I set the direction, the rules and the calls.

Decision one: no BSP

What Quake does. In Quake, a map isn’t playable until it’s been compiled. One tool, qbsp, chops the whole level into a tree of convex spaces. Another, vis, works out which of those spaces can possibly see each other and saves the answer as a big table. At runtime, the engine checks which space you’re standing in and only draws what’s on your list. It’s brilliant, and it’s a big part of how Quake ran on 1996 hardware.

Why VolythEngine doesn’t. It’s also a wall between building a level and playing it. vis could take ages on a big map, and a single gap to the void, a leak, meant it wouldn’t run at all. The whole point of VolythEngine is one tool where you build something and hit a key to stand in it. So maps stay exactly what the editor made: a pile of brushes, no tree, no compile step.

That leaves a problem. Without the tree, the renderer has no idea what’s behind a wall, so it draws everything.

How it works instead. The lightmap baker already has a fast ray tracer for shadows, so visibility borrows it. The level is split into a grid of cells, and from points in each cell the engine traces lines of sight to every region of the level. If any line gets through, that region counts as visible from that cell. Stand in a cell, draw its list.

It’s sampling, not proof, which means it can be wrong. The first version sampled each region by its bounding box instead of its actual surfaces, and walls went missing:

The rule that fixed it: correctness beats savings. Every triangle is a sample point. Glass and water don’t block sight. Anything within 256 units counts as visible, no matter what. A cell buried in solid, or outside the map, sees everything. Every one of those started as a cheaper shortcut, and every one got caught, because Claude has to compare screenshots of its own work before it’s allowed to call anything done. That rule is mine, and this is exactly the kind of bug it’s there for. The visibility set is allowed to draw too much. It’s never allowed to draw too little.

Stealing from the leak finder. The editor has a leak finder now. It floods outwards from the entities, and if it can escape the level, it draws a red line through the hole.

Claude borrowed the same flood for visibility, so it only bothers with cells you can actually reach. On LibreQuake’s e0m1, that took it from computing nearly every cell in the grid to about a tenth of them, and the build from 28 seconds to 5. It draws slightly more than the slow version, about 11% more triangles, and every view checked is pixel-identical.

Here’s the payoff, from the spawn point of that same map:

About forty times fewer triangles for the same frame.

Measuring before building. The textbook move here is a bounding volume hierarchy, a tree of boxes, for both culling and clicking on things in the editor. So Claude measured first. Culling e0m1 costs a few microseconds a frame. Clicking to select a brush tests every brush in the map, and on a stress-test map with 4,090 brushes, a click takes 0.38 milliseconds. A tree would save microseconds and need rebuilding on every edit. So there’s no tree. Instead there’s a note in the decisions log saying exactly when to build one: the day a click takes longer than a frame.

Decision two: every edit is a value

The easy way. The quick way to build an editor is to let each button and text field change the map directly, then bolt undo on later. Undo becomes a pile of special cases, and it’s always the first thing to break.

What VolythEngine’s editor does. Claude settled on this early, back when the editor could only change one property at a time. Nothing in the interface is allowed to touch the map. The inspector, the brush tools and the console can only hand back an edit, a small value describing exactly one change:

pub enum Edit {
    /// Change the value of the key-value pair at `index`.
    SetValue { entity: usize, index: usize, from: String, to: String },
    /// Add a brush to an entity at `index`.
    InsertBrush { entity: usize, index: usize, brush: Brush },
    /// Remove the brush at `index`, which must equal `brush`.
    RemoveBrush { entity: usize, index: usize, brush: Brush },
    // ...seven more
}

impl Edit {
    /// The edit that undoes this one.
    pub fn inverse(&self) -> Edit {
        match self.clone() {
            Edit::SetValue { entity, index, from, to } =>
                Edit::SetValue { entity, index, from: to, to: from },
            Edit::InsertBrush { entity, index, brush } =>
                Edit::RemoveBrush { entity, index, brush },
            // ...
        }
    }
}

Two things make this work.

• Every edit says what it expects to find. A SetValue carries the old value as well as the new one. If the map doesn’t match, the edit is refused and nothing changes. A stale edit can never half-apply.
• Every edit knows its own inverse. Undo is just applying it. There’s no snapshotting, and no special case per tool.

The rest falls out of that. An undo step is a list of edits, so dragging three things at once is one Ctrl+Z. Typing a value produces an edit per keystroke, but changes to the same field merge, so typing “900” is one undo, not three. Even “unsaved” isn’t a flag someone has to remember to set. It’s worked out from the undo history, so undoing back to where you last saved clears the star by itself. And saving writes to a temporary file first and swaps it in, so a crash mid-save never leaves you with half a map.

Why it paid off. Every tool built since then speaks only in edits: drawing brushes, the clip tool, texture alignment, rotate and flip, the console’s set command, and vertex editing across several brushes at once.

Which means every one of them could be undone from the day it existed. Undo got written once.

Same question, both times

Quake’s way was built for 1996’s computers and 1996’s tools. Some of it is still the best answer there is, like baked lightmaps and the movement. Some of it was a workaround for hardware that doesn’t exist anymore. I’m keeping the parts that make it feel like Quake, and dropping the parts that make it slow to build in.

Most of my calls are about where the effort goes. Weapons and monsters are placeholders on purpose, so the work goes into the world, the tools and the look. That’s the part I want to spend my time on.