Loading Doom (1993) levels

This is the narrative of my Doom level loading code.
It is coded in C, uses Allegro 4, compiles for Win32, Linux and MS-DOS, and is hosted at bitbucket (link to repository).
Download the demo here.

Target audience

Challenges

The original Doom engine is not a polygonal engine.
The level format stores the minimal ammount of information. Walls are line segments, floors are implicit between those lines. "Modern" rendering approaches universally use polygons to represent the entire level geometry. Libraries and engines expect will expect polygonal data built out of triangles where each vertex has 3D position, and UV coordinates.
Thus, extensive preprocessing is required to turn Doom level data into data useable in a more ordinary engine.

Similar efforts

When starting out, I found this WebGL Doom level loader (archive), and there it mentions that to bypass the challenges of doing the conversion to a polygonal format himself, he used the glBSP node builder (archive), a tool from the 1990s, that adds information to the WAD to solve this same issue.
I didn't want to depend on this tool, so I reinvented the wheel anyway.

References

First of all, if you expect the rest of the explanation to make any sense, you better be familiar with Fabien Sanglard's Doom source code review(archive), and also maybe his full book on the subject, The Game Engine Black Book: DOOM(archive), which is VERY worth a read. Fabien has great credit in spreading knowledge about classic FPS engines, and I personally love his writing.
There he explains concepts such as the BSP, and how Doom rendering is different from the modern polygonal methods.

An image from his explanation of the Doom engine

The most useful document in reading the WAD file format was The Unofficial Doom specs v1.666 by Mathew S Fell, dated December 15th, 1994. Old but great! Still an authoritative work on the topic.
Also very useful was the Doom wiki at doomwiki.org, specially this article; there is also another Doom wiki hosted by Wikia, fuck Wikia.

Peculiarities of the format

The most peculiar bit in the Doom level format is how node bounding boxes are stored, as a sequence of Y upper, Y lower, X lower, X upper coordinates.
I have no idea why Carmack picked this ordering; seems almost random.
static struct wad_flatface bboxflatface(int16_t *bbox) { struct wad_flatface f = { .face = { .verts = { {.pos = {bbox[2], bbox[0], 0},}, {.pos = {bbox[3], bbox[0], 0},}, {.pos = {bbox[3], bbox[1], 0},}, {.pos = {bbox[2], bbox[1], 0},}, }, .num_verts = 4, }, }; return f; }
static struct wad_flatface bboxflatface(int16_t *bbox) { struct wad_flatface f = { .face = { .verts = { {.pos = {bbox[2], bbox[0], 0},}, {.pos = {bbox[3], bbox[0], 0},}, {.pos = {bbox[3], bbox[1], 0},}, {.pos = {bbox[2], bbox[1], 0},}, }, .num_verts = 4, }, }; return f; }
Code to make a quad face out of a bounding box

Processing sequence

  1. Build the node planes for each BSP tree node
  2. Build the flat (floor and ceiling) faces
  3. Build the wall faces

Node planes

The Doom level format has for each BSP node a line connecting (x,y) to (x+dx,y+dy) in the structure below:
struct wad_node { int16_t x, y, dx, dy, bbox_r[4], bbox_l[4], child_r, child_l; };
struct wad_node { int16_t x, y, dx, dy, bbox_r[4], bbox_l[4], child_r, child_l; };

Yet, we know that the node builder, when creating those nodes, made those lines out of existing map linedefs.
Unfortunately, not directly, for some are shorter segments inside a line definition.
Since this was done in fixed point, the loss in resolution causes precision issues, where a node plane and its corresponding linedef are not coplanar.
To fix this, the first step is to find a linedef corresponding to each node plane, and then use the linedef rather than the node structure to do the face splitting that births flat and wall faces.
static void wad_map_build_nodeplanes(struct wad_map_build_faces_t *level) { //Adjust for best results const int TOLERANCE_1 = 2.0; //Distance to linedef const int TOLERANCE_2 = 1.0; //Distance to linedef ends if projected outside const int TOLERANCE_3 = 0.99; //Dot product to check if projected inside const int TOLERANCE_4 = 0.95; //Dot product of node and linedef planes int i, j, k; level->nodeplanes = malloc(level->num_nodes * sizeof(*level->nodeplanes)); //Note the O(n^2) naive algorithm for(i = 0; i < level->num_nodes; i++){ const struct wad_node *node = level->nodes + i; const vec3 nodev[3] = { {node->x, node->y, 0}, {node->x + node->dx, node->y + node->dy, 0}, {node->x, node->y, 100}, }; mplane nodep; vec3_verts2plane(nodev, nodev + 1, nodev + 2, &nodep); vecc_t bestscore = FLT_MAX; mplane bestp; for(j = 0; j < level->num_linedefs; j++){ const struct wad_linedef *linedef = level->linedefs + j; const struct wad_vertex *start = level->vertices + linedef->start; const struct wad_vertex *end = level->vertices + linedef->end; const vec3 linev[3] = { {start->x, start->y, 0}, {end->x, end->y, 0}, {start->x, start->y, 100}, }; mplane linep; vec3_verts2plane(linev, linev + 1, linev + 2, &linep); vecc_t score = 0; for(k = 0; k < 2; k++){ const vecc_t pdist = fabs(vec3_dist2plane(&linep, nodev + idx_n)); if(pdist > TOLERANCE_1) break; //Also do the other checks //[...] score += pdist; } if(score < bestscore){ bestscore = score; bestp = linep; } } assert(bestscore != FLT_MAX); //More checks [...] level->nodeplanes[i] = bestp; } }
static void wad_map_build_nodeplanes(struct wad_map_build_faces_t *level) { //Adjust for best results const int TOLERANCE_1 = 2.0; //Distance to linedef const int TOLERANCE_2 = 1.0; //Distance to linedef ends if projected outside const int TOLERANCE_3 = 0.99; //Dot product to check if projected inside const int TOLERANCE_4 = 0.95; //Dot product of node and linedef planes int i, j, k; level->nodeplanes = malloc(level->num_nodes * sizeof(*level->nodeplanes)); //Note the O(n^2) naive algorithm for(i = 0; i < level->num_nodes; i++){ const struct wad_node *node = level->nodes + i; const vec3 nodev[3] = { {node->x, node->y, 0}, {node->x + node->dx, node->y + node->dy, 0}, {node->x, node->y, 100}, }; mplane nodep; vec3_verts2plane(nodev, nodev + 1, nodev + 2, &nodep); vecc_t bestscore = FLT_MAX; mplane bestp; for(j = 0; j < level->num_linedefs; j++){ const struct wad_linedef *linedef = level->linedefs + j; const struct wad_vertex *start = level->vertices + linedef->start; const struct wad_vertex *end = level->vertices + linedef->end; const vec3 linev[3] = { {start->x, start->y, 0}, {end->x, end->y, 0}, {start->x, start->y, 100}, }; mplane linep; vec3_verts2plane(linev, linev + 1, linev + 2, &linep); vecc_t score = 0; for(k = 0; k < 2; k++){ const vecc_t pdist = fabs(vec3_dist2plane(&linep, nodev + idx_n)); if(pdist > TOLERANCE_1) break; //Also do the other checks //[...] score += pdist; } if(score < bestscore){ bestscore = score; bestp = linep; } } assert(bestscore != FLT_MAX); //More checks [...] level->nodeplanes[i] = bestp; } }
(Simplified) code to build node planes from line definitions

Flat faces

The flat (ceiling and floor) faces are easy to build.
We start with a single quad face, spanning the whole map, and progressively cut it by each node plane, moving down the BSP tree, until each face ends up in a corresponding subsector; using a recursive function.
static void wad_map_build_flat_faces(struct wad_map_build_faces_t *bsp, int node_i, rvface face) { mplane linep = {}; //Arrived at a leaf of the BSP tree if(node_i < 0){ int ssector_i = 32768 + node_i; struct wad_ssector *ss = bsp->ssectors + ssector_i; int i, j, sector; //Cut face by every subsector segment for(i = 0, j = ss->first_seg; i < ss->num_segs; i++, j++){ struct wad_seg *seg = bsp->segs + j; struct wad_linedef *linedef = bsp->linedefs + seg->linedef; struct wad_vertex *start = bsp->vertices + linedef->start; struct wad_vertex *end = bsp->vertices + linedef->end; const vec3 linev[3] = { {start->x, start->y, 0}, {end->x, end->y, 0}, {start->x, start->y, seg->dir ? -100 : 100}, }; vec3_verts2plane(linev, linev + 1, linev + 2, &linep); rvface right, left; rvface_split(&linep, &face, &right, &left); face = right; } //Try and find sector face is in //[...] //Set z,u,v for floor for(i = 0; i < face.num_verts; i++){ face.verts[i].pos.z = bsp->sectors[sector].h_floor; face.verts[i].u = face.verts[i].pos.x; face.verts[i].v = face.verts[i].pos.y; } arr_push(&bsp->flatfaces, ff); //Flip and set z for ceiling rvface_flip(&face); for(i = 0; i < face.num_verts; i++){ face.verts[i].pos.z = bsp->sectors[sector].h_ceil; } arr_push(&bsp->flatfaces, ff); return; } struct wad_node *node = bsp->nodes + node_i; linep = bsp->nodeplanes[node_i]; //Sort and send face further down BSP int sort = rvface_sort(&linep, &face); assert(sort != RVFACE_COPLANAR); if(sort == RVFACE_SPANNING){ rvface right, left; rvface_split(&linep, &face, &right, &left); wad_map_build_flat_faces(bsp, node->child_r, right); wad_map_build_flat_faces(bsp, node->child_l, left); } else if(sort == RVFACE_FRONT){ wad_map_build_flat_faces(bsp, node->child_r, face); } else if(sort == RVFACE_BACK){ wad_map_build_flat_faces(bsp, node->child_l, face); } return; }
static void wad_map_build_flat_faces(struct wad_map_build_faces_t *bsp, int node_i, rvface face){ mplane linep = {}; //Arrived at a leaf of the BSP tree if(node_i < 0){ int ssector_i = 32768 + node_i; struct wad_ssector *ss = bsp->ssectors + ssector_i; int i, j, sector; //Cut face by every subsector segment for(i = 0, j = ss->first_seg; i < ss->num_segs; i++, j++){ struct wad_seg *seg = bsp->segs + j; struct wad_linedef *linedef = bsp->linedefs + seg->linedef; struct wad_vertex *start = bsp->vertices + linedef->start; struct wad_vertex *end = bsp->vertices + linedef->end; const vec3 linev[3] = { {start->x, start->y, 0}, {end->x, end->y, 0}, {start->x, start->y, seg->dir ? -100 : 100}, }; vec3_verts2plane(linev, linev + 1, linev + 2, &linep); rvface right, left; rvface_split(&linep, &face, &right, &left); face = right; } //Try and find sector face is in //[...] //Set z,u,v for floor for(i = 0; i < face.num_verts; i++){ face.verts[i].pos.z = bsp->sectors[sector].h_floor; face.verts[i].u = face.verts[i].pos.x; face.verts[i].v = face.verts[i].pos.y; } arr_push(&bsp->flatfaces, ff); //Flip and set z for ceiling rvface_flip(&face); for(i = 0; i < face.num_verts; i++){ face.verts[i].pos.z = bsp->sectors[sector].h_ceil; } arr_push(&bsp->flatfaces, ff); return; } struct wad_node *node = bsp->nodes + node_i; linep = bsp->nodeplanes[node_i]; //Sort and send face further down BSP int sort = rvface_sort(&linep, &face); assert(sort != RVFACE_COPLANAR); if(sort == RVFACE_SPANNING){ rvface right, left; rvface_split(&linep, &face, &right, &left); wad_map_build_flat_faces(bsp, node->child_r, right); wad_map_build_flat_faces(bsp, node->child_l, left); } else if(sort == RVFACE_FRONT){ wad_map_build_flat_faces(bsp, node->child_r, face); } else if(sort == RVFACE_BACK){ wad_map_build_flat_faces(bsp, node->child_l, face); } return; }
(Simplified) code to build flat faces

Wall faces

First, there is some special logic to build faces for the upper, lower, and middle segments which a wall can have.
for(i = 0; i < bsp.num_linedefs; i++){ const struct wad_linedef linedef = bsp.linedefs[i]; const struct wad_vertex start = bsp.vertices[linedef.start], end = bsp.vertices[linedef.end]; const int length = sqrt(pow(start.x - end.x, 2) + pow(start.y - end.y, 2)); struct wad_wallface right = { .face = { .verts = { {.pos = {end.x, end.y, 0}, .u = length, .v = 0}, {.pos = {start.x, start.y, 0}, .u = 0, .v = 0}, {.pos = {start.x, start.y, 0}, .u = 0, .v = 0}, {.pos = {end.x, end.y, 0}, .u = length, .v = 0}, }, .num_verts = 4, }, .sidedef = linedef.sidedef_r, }; struct wad_wallface left = { //[...] }; const struct wad_sidedef *sidedef_r = bsp.sidedefs + right.sidedef, *sidedef_l = (left.sidedef >= 0) ? (bsp.sidedefs + left.sidedef) : 0; const struct wad_sector *sector_r = bsp.sectors + sidedef_r->sector, *sector_l = sidedef_l ? (bsp.sectors + sidedef_l->sector) : 0; //Sets Z for the wall segment #define VERTS_SETZ(a,b) //[...] if(sidedef_l && sector_l->h_ceil < sector_r->h_ceil){ //Upper texture VERTS_SETZ(sector_r->h_ceil, sector_l->h_ceil); right.type = WAD_BSPFACE_UPPER; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } if(sidedef_l && sector_l->h_floor > sector_r->h_floor){ //Lower texture VERTS_SETZ(sector_l->h_floor, sector_r->h_floor); right.type = WAD_BSPFACE_LOWER; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } if(strncmp(sidedef_r->tex_mid, "-", 8)){ //Middle texture VERTS_SETZ(sector_r->h_ceil, sector_r->h_floor); right.type = WAD_BSPFACE_MIDDLE; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } //The same but for the "left" face //[...] }
for(i = 0; i < bsp.num_linedefs; i++){ const struct wad_linedef linedef = bsp.linedefs[i]; const struct wad_vertex start = bsp.vertices[linedef.start], end = bsp.vertices[linedef.end]; const int length = sqrt(pow(start.x - end.x, 2) + pow(start.y - end.y, 2)); struct wad_wallface right = { .face = { .verts = { {.pos = {end.x, end.y, 0}, .u = length, .v = 0}, {.pos = {start.x, start.y, 0}, .u = 0, .v = 0}, {.pos = {start.x, start.y, 0}, .u = 0, .v = 0}, {.pos = {end.x, end.y, 0}, .u = length, .v = 0}, }, .num_verts = 4, }, .sidedef = linedef.sidedef_r, }; struct wad_wallface left = { //[...] }; const struct wad_sidedef *sidedef_r = bsp.sidedefs + right.sidedef, *sidedef_l = (left.sidedef >= 0) ? (bsp.sidedefs + left.sidedef) : 0; const struct wad_sector *sector_r = bsp.sectors + sidedef_r->sector, *sector_l = sidedef_l ? (bsp.sectors + sidedef_l->sector) : 0; //Sets Z for the wall segment #define VERTS_SETZ(a,b) //[...] if(sidedef_l && sector_l->h_ceil < sector_r->h_ceil){ //Upper texture VERTS_SETZ(sector_r->h_ceil, sector_l->h_ceil); right.type = WAD_BSPFACE_UPPER; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } if(sidedef_l && sector_l->h_floor > sector_r->h_floor){ //Lower texture VERTS_SETZ(sector_l->h_floor, sector_r->h_floor); right.type = WAD_BSPFACE_LOWER; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } if(strncmp(sidedef_r->tex_mid, "-", 8)){ //Middle texture VERTS_SETZ(sector_r->h_ceil, sector_r->h_floor); right.type = WAD_BSPFACE_MIDDLE; wad_map_build_wall_faces(&bsp, bsp.num_nodes - 1, right); } //The same but for the "left" face //[...] }
(Simplified) code to build faces for each linedef
Then, sending the wall faces down the tree is very similar to flat faces, but there is a special case where the wall lies on a node plane.
static void wad_map_build_wall_faces(struct wad_map_build_faces_t *bsp, int node_i, struct wad_wallface lface) { mplane linep; //Arrived at a leaf? if(node_i < 0){ arr_push(&bsp->wallfaces, lface); return; } struct wad_node *node = bsp->nodes + node_i; linep = bsp->nodeplanes[node_i]; //Sort and send face further down BSP int sort = rvface_sort(&linep, &lface.face); if(sort == RVFACE_SPANNING){ struct wad_wallface right = lface, left = lface; rvface_split(&linep, &lface.face, &right.face, &left.face); wad_map_build_wall_faces(bsp, node->child_r, right); wad_map_build_wall_faces(bsp, node->child_l, left); } if(sort == RVFACE_FRONT){ wad_map_build_wall_faces(bsp, node->child_r, lface); } if(sort == RVFACE_BACK){ wad_map_build_wall_faces(bsp, node->child_l, lface); } if(sort == RVFACE_COPLANAR){ vec3 sqn; vec3_sqnormal(&lface.face.verts[0].pos, &lface.face.verts[1].pos, &lface.face.verts[2].pos, &sqn); const vecc_t dot = vec3_dot(&linep.normal, &sqn); if(dot > 0) wad_map_build_wall_faces(bsp, node->child_r, lface); else wad_map_build_wall_faces(bsp, node->child_l, lface); } }
static void wad_map_build_wall_faces(struct wad_map_build_faces_t *bsp, int node_i, struct wad_wallface lface) { mplane linep; //Arrived at a leaf? if(node_i < 0){ arr_push(&bsp->wallfaces, lface); return; } struct wad_node *node = bsp->nodes + node_i; linep = bsp->nodeplanes[node_i]; //Sort and send face further down BSP int sort = rvface_sort(&linep, &lface.face); if(sort == RVFACE_SPANNING){ struct wad_wallface right = lface, left = lface; rvface_split(&linep, &lface.face, &right.face, &left.face); wad_map_build_wall_faces(bsp, node->child_r, right); wad_map_build_wall_faces(bsp, node->child_l, left); } if(sort == RVFACE_FRONT){ wad_map_build_wall_faces(bsp, node->child_r, lface); } if(sort == RVFACE_BACK){ wad_map_build_wall_faces(bsp, node->child_l, lface); } if(sort == RVFACE_COPLANAR){ vec3 sqn; vec3_sqnormal(&lface.face.verts[0].pos, &lface.face.verts[1].pos, &lface.face.verts[2].pos, &sqn); const vecc_t dot = vec3_dot(&linep.normal, &sqn); if(dot > 0) wad_map_build_wall_faces(bsp, node->child_r, lface); else wad_map_build_wall_faces(bsp, node->child_l, lface); } }
(Simplified) code to cut wall faces

Rendition

I first wrote an orthographic top down viewer.
I next put the generated faces into my own BSP engine, which is a WIP game engine.
All textures had to be scaled to a power of 2, along other small issues.
I included code to collapse empty leafs, which seem to happen occasionally. One example is the green armour alcove in E1M3.
for(i = 0; i < bsp->num_nodes; i++){ bspnode *node = bsp->nodes + i; bspnode *parent = 0; int parent_child = -1; for(j = 0; j < bsp->num_nodes; j++){ parent = bsp->nodes + j; for(k = 0; k < 2; k++){ if(parent->children[k] == i){ parent_child = k; break; } } if(k < 2) break; } if(j == bsp->num_nodes) continue; int empty_child = -1; for(j = 0; j < 2; j++){ if(BSPNODE_ISLEAF(node->children[j])){ const int leaf_i = BSPNODE_TO_LEAF(node->children[j]); const bspleaf *leaf = bsp->leafs + leaf_i; if(leaf->last_face < leaf->first_face){ empty_child = j; break; } } } if(j == 2) continue; const int other_child = !empty_child; parent->children[parent_child] = node->children[other_child]; }
for(i = 0; i < bsp->num_nodes; i++){ bspnode *node = bsp->nodes + i; bspnode *parent = 0; int parent_child = -1; for(j = 0; j < bsp->num_nodes; j++){ parent = bsp->nodes + j; for(k = 0; k < 2; k++){ if(parent->children[k] == i){ parent_child = k; break; } } if(k < 2) break; } if(j == bsp->num_nodes) continue; int empty_child = -1; for(j = 0; j < 2; j++){ if(BSPNODE_ISLEAF(node->children[j])){ const int leaf_i = BSPNODE_TO_LEAF(node->children[j]); const bspleaf *leaf = bsp->leafs + leaf_i; if(leaf->last_face < leaf->first_face){ empty_child = j; break; } } } if(j == 2) continue; const int other_child = !empty_child; parent->children[parent_child] = node->children[other_child]; }
Code to collapse empty leafs
I further added Potential Visibility Set a la Quake (see Michael Abrash's Black Book for a description of its use in Quake) generation. Works well, but for a few maps it takes forever to compile, or much more than the others at any rate. I can't yet tell what exactly causes those maps to misbehave, but it seems to be the maps created last (Ultimate Doom and Doom II).
The portals from the PVS generation can be used for pathfinding.
I also implemented loading the THINGS lump, thus enemies and pickups are visible.

Future

The current implementation lacks support for working doors, but it shouldn't be hard to add.
Transparent walls don't work properly.
The renderer could be optimized to use a column-based rasterizer, which would be much faster.
A full Doom source port could be built from this.
I hope to use this to create levels for small, jam-sized 3D games.