Doom: The Wall Was Also a Way to Avoid Work

A wall has two jobs in a first-person game. It gives the player something to see, and it hides whatever is behind it. The second job can be valuable to the computer.

There might be an elaborate room beyond that wall, with more walls, textures and objects. If none of it can affect the current view, spending time drawing it is a remarkably thorough way to accomplish nothing.

Doom made a convincing environment partly by being selective about the work it performed. Its renderer used a spatial organization of the map to visit relevant geometry in a useful order, then reject regions whose possible appearance was already hidden. The clever part was making the organization of the world serve the production of the picture.

The monsters weren’t concerned with the data structure. They had other commitments.

The game and the surviving evidence

The original Doom arrived on December 10, 1993, a date confirmed by the publisher’s anniversary account.¹ Its id Software setting and presentation belong to a complete game, with design, art, sound and programming contributing to the result. A renderer explains some of its engineering appeal; it doesn’t explain the whole experience of playing it.

John Carmack’s signed source-release README gives unusually candid evidence about the engine. Dated December 23, 1997, it credits Bernd Kreimeier’s cleanup and explains that the released code was the Linux version: a proprietary sound library prevented publication of the DOS code. This surviving implementation is useful evidence of the design, rather than a byte-for-byte record of the first 1993 executable.²

John Carmack at GDC, March 11, 2010, much later than Doom’s original release. Photo by Official GDC, source and reuse record, CC BY 2.0. This is the existing Commons crop, made in 2020; no additional alterations.

The distinction prevents some attractive mistakes. Later source ports can offer capabilities that weren’t in the original game. Carmack’s README itself suggests slopes, looking up and down, and a client/server Internet game as possible improvements. It also says the original movement and line-of-sight testing didn’t use the BSP tree in the way he later wished they had.²

One mechanism isn’t the answer to every question just because it worked impressively for rendering. That is a reassuringly ordinary observation inside an extraordinary piece of software.

A map organized for looking

BSP means binary space partitioning. A dividing line separates a two-dimensional region into two sides; those sides can be subdivided again. The resulting tree records a succession of spatial choices.

A leaf represents a final region in that organization. Following the tree allows a renderer to order the regions relative to the viewer without sorting every wall independently from scratch each frame.

The released renderer’s R_RenderBSPNode first visits the child on the viewer’s side. It then checks whether the other child’s bounding box might still be visible before traversing that child. Its solid-wall clipping records blocked horizontal screen ranges; openings receive different treatment.³

That short description carries two distinct ideas. The tree supplies an order. The accumulated visibility information supplies reasons to stop. A tree that organizes the map is useful, but it doesn’t by itself prove that a particular region is hidden.

Let’s work through an invented example rather than pretend to reproduce one of Doom’s maps. We choose a dividing line at map coordinate x = 4. The viewer stands at x = 2, on the left side. The left child therefore gets visited before the right child.

This is an ordering decision about the sides of a partition. It doesn’t imply that every possible object on the left is nearer than every possible object on the right by simple straight-line distance. The structure and its geometric divisions are doing more specific work than a generic distance ranking.

Our model uses a pretend screen 160 columns wide, numbered 0 through 159. It doesn’t calculate perspective, wall heights or textures. Instead, we supply invented projected ranges so we can examine the visibility decision separately.

Forty columns are already spoken for

During the near-side visit, an opaque wall covers columns 40 through 79, inclusive. That is 40 columns:

79 - 40 + 1 = 40

The +1 matters because both endpoints are included. Leaving it out is an efficient way to introduce a small error into every subsequent count.

Now suppose the distant child’s bounding box projects to columns 50 through 69. All 20 possible columns lie inside the wall’s blocked range. In this simplified model, the far child can be rejected.

The renderer doesn’t need to prove that every surface in the distant room is separately hidden. The bounding box is a conservative enclosure: if its entire possible screen range is blocked, anything contained within that range cannot add a visible column under our assumptions.

Original explanatory diagram, 2026. Invented partition, screen columns and blocking ranges; not a Doom map, screenshot or performance measurement.

Change the far projection to columns 70 through 99. Columns 70 through 79 remain blocked, but 80 through 99 are open. The far child must be considered. Some geometry may contribute to the picture.

The difference is only 20 open columns, yet it changes the decision from skip to visit. A visibility test has to preserve possible contributions, even when they are modest. One missing strip can turn a correct optimization into a conspicuous hole.

Now add another opaque near wall spanning columns 80 through 99. Together the two blocked ranges cover 40 through 99. The same distant projection, 70 through 99, becomes fully blocked and can be rejected again.

Our checker represents blocked columns as a set. It verifies all three cases: enclosed projection rejected, partly exposed projection retained, and combined coverage rejected. That representation makes the arithmetic easy to inspect; it isn’t a transcription of Doom’s interval-list code.

An opening changes the evidence

Suppose the near structure contains a window. Its upper and lower surfaces may obstruct parts of the picture while the opening reveals a room beyond. Marking its entire horizontal range as solid would erase information the player should see.

This is why our model explicitly assumes opaque walls that completely block the corresponding viewing directions. It doesn’t attempt to encode partial vertical visibility. A screen column contains many pixels, and seeing an obstruction somewhere in the column doesn’t establish that the whole column is unavailable.

The released code distinguishes solid wall segments from passable viewing openings.³ That is an implementation detail with a larger explanatory value: an optimization must record the right kind of evidence. An obstruction and a complete obstruction are different facts.

Bounding boxes have a related limitation. Their enclosure can project into an open range even if the actual geometry inside contributes nothing. In that case the safe decision is to visit and discover more. A conservative test tolerates extra work to avoid discarding visible content.

There is consequently no universal promise that the tree makes every frame cheap, or that total rendering time follows a tidy logarithmic formula. The viewpoint, arrangement of walls and amount of visible detail influence how much work remains. The useful achievement is an opportunity to skip work with a defensible reason.

For a game, those reasons are part of the artistic budget. Time saved on hidden regions becomes time available for the world the player can actually see. The technical restriction and the visible result are closely related.

The world also needed names

Doom’s data organization offers a second revealing separation. The released WAD loader reads a directory of named resources, called lumps, with file positions and lengths. Its name lookup runs backward through the loaded entries so later resources can replace earlier ones.⁴

Here is another invented miniature, using a name that doesn’t imply a real Doom asset. A base file contains:

File	Resource name	File offset	Length
Base	TEST	100	20
Patch	TEST	700	12

Load the base entries first and the patch entries afterward. A backward lookup for TEST finds the patch entry and selects its 12 bytes beginning at offset 700. It doesn’t average the two resources or append them together. It chooses the later matching entry.

That is a small rule with useful consequences. A consumer asks for a name, while the loader chooses the stored bytes. Replacement can happen without embedding every resource directly into the program executable.

The replacement still has obligations. If the consumer expects a particular data structure, a matching name doesn’t make arbitrary bytes valid. Our checker tests selection order only; it doesn’t validate a texture or load a playable level.

Separating resources from code creates room for modification without making every aspect of the game a resource. It doesn’t follow that all game behavior is an editable WAD script. The engine still determines how it interprets the material supplied to it.

Nor does access to the engine source grant permission to reproduce all the original art. Carmack’s release note explicitly says real Doom data is still required. The repository’s later GPL licensing and the original release terms belong to their own chronology.² Source availability and data rights deserve separate entries in the ledger.

Giving the computer useful reasons

Doom’s renderer and its resource loader solve different problems, yet both make choices explicit. The renderer asks whether a region can still affect the picture. The loader asks which named resource should supply the bytes.

Those decisions are more powerful when they rest on a useful organization. A partition tree supports traversal. A directory supports lookup and replacement. Neither structure makes its contents correct automatically, but each gives the software a practical way to find the relevant work.

I find the visibility example particularly satisfying because the saving has a concrete cause. The distant room isn’t drawn merely to be covered up afterward. Under the test’s assumptions, the nearby wall has already supplied sufficient evidence to leave it alone.

The player sees a wall. The renderer also sees a respectable excuse.

Footnotes

1. Bethesda, DOOM Turns 22!, December 10, 2015. Used for the original December 10, 1993 date, not the page’s genre-first implications or later-game features. ↩

2. John Carmack, source-release README, signed December 23, 1997. Linux release, Kreimeier cleanup, DOS sound-library limitation, data requirement and proposed improvements distinguished from 1993 features and later repository licensing. ↩ ↩² ↩³

3. id Software, Linux Doom 1.10 r_bsp.c, especially R_RenderBSPNode, R_CheckBBox and solid/pass wall clipping. Surviving later released implementation, not the first DOS build; numerical examples are original. ↩ ↩²

4. id Software, Linux Doom 1.10 w_wad.c, W_AddFile and W_CheckNumForName. The invented TEST entries explain directory selection, not a complete historical WAD. ↩