To draw a room, near walls have to cover far ones. The obvious way sorts every wall far to near and paints them all: from one spot in our little map that paints a 96-column screen 357 times over, almost four screens, and every step you sort again.

Doom's levels are cut in half, then each half again, once, before you play: a tree. id Software's released code walks it every frame. At each cut, R_RenderBSPNode asks one thing, "Decide which side the view point is on", and goes into that side first. So walls arrive nearest first, each one taking screen columns that nothing behind can have, and a half whose columns are all taken is skipped without a look ("Possibly divide back space"). From our spot it looked at 9 of 39 walls.

The idea is from a 1980 paper by Fuchs, Kedem and Naylor. John Carmack, who wrote Doom's renderer, said in 1997 that he used the tree for drawing but missed that it could check collisions too: "a vastly simpler (and faster) solution sitting in front of my face."

Our map, tree, screen and counts are our own simplified version, built in code from the released routines.

Which classic game trick should we cut open next?

Sources: id Software, Doom source code release (linuxdoom-1.10, r_bsp.c and r_main.c, 1997). John Carmack, README for the source release, 23 Dec 1997. H. Fuchs, Z. Kedem and B. Naylor, "On Visible Surface Generation by A Priori Tree Structures", SIGGRAPH 1980. Michael Abrash, Graphics Programming Black Book, ch. 59.
Unofficial. Not affiliated with or endorsed by id Software, ZeniMax or Bethesda.
Sounds and music: our own, made in code.