Methodology - How WADs are Analyzed

A Bit of Background

One of the reasons for the success of Doom and Doom 2 was that players could make and share their own WAD files. These files contain the level data and assets used by the game to produce your experience, so custom WADs means that players could make their own levels, including custom music and graphics.

It's a great design, and since most WADs are fairly small, it was easy to share them online during the era of the early internet. Many players still make their own levels and share them online today.

However, not every custom WAD is created equal. Many were uploaded before they were finished, and many others were corrupted by the transfer, by sloppy editing programs, or by inexperienced authors.

Generally, broken and unusable files are either taken down by the hosting site or ignored by the playerbase, but there's one small problem. While some groups did try to make and distribute their own levels on CD-ROM, many tried to pad their level count by throwing together WADs they'd grabbed from the internet. Quantity mattered more than quality, and in many cases, it shows.

In order to study and document these old "Shovelware" collections (and other WADs of interest), a custom WAD parsing tool was developed.

This custom tool can do many things, the most obvious of which is create detailed maps that you can browse through on their individual pages. It can also track the history and identity of different parts of the WADs, which will be useful in tracking down the real authorship and history of many custom levels.

But another key feature of this WAD parser is its ability to diagnose potential problems with each WAD and the maps stored within it. You'll find this information scattered throughout this website. This page is here to explain what some of these terms mean, what sort of problems they cause, and how they are detected.

Visplane Risk Analysis

Doom's rendering engine dynamically creates special data structures called "visplanes" to draw the visible parts of the level's geometry. It's a good system, but there's a catch: the game's engine can only allocate 128 visplanes at a time, which means that if a frame would require 129 visplanes, the game runs out of room and crashes with a cryptic message about visplane overflow.

Many modern source ports remove this limitation by handling the memory differently. After all, most of us aren't running DOS anymore, and our computers have a lot more than 8 MB of RAM. But we're not here to talk about which source port is the best. We're here to find out how stable these WADs are and if they'll run properly on a source port that doesn't remove those limits.

The WAD parser doesn't actually attempt to render the level - that's a bit more technical than we need to go - so instead of trying to recreate the engine and see if we can make it crash, a simpler approach is used.

First, it generates an alternative version of the level's map. In this new version, every LINEDEF is replaced by a hitbox. If the LINEDEF is too small, then it's enlarged slightly to ensure the next step will see it.

Two versions of E1M1's map: the second one is the visplane map.

Now, in order to find areas that might risk a visplane overflow, the parser will "fire" a ray from the center of each hitbox. This ray will continue until it reaches a LINEDEF marked as a solid wall or the edge of the map. As the ray moves along, it records the number of hitboxes it touches. The visplane risk for that specific spot and direction is therefore the total number of hitboxes the ray hit before stopping.

There are eight rays fired per hitbox - one in each cardinal and diagonal direction. This is generally enough to find any spaces where things might be pushing the engine a little too far.

The parser simply tallies the results against some expected ranges, and then lists them as Safe, Warning, Critical, and Danger. Areas flagged with Warning should work fine in any source port: they're just starting to get near the point where a map maker should be cautious. Critical areas are hovering just shy of the threshold, and may be able to cause a visplane overflow. Danger areas are over the threshold, so expect crashes in the original engine or source ports that don't remove limits.

Density Risk Analysis

Another quirk of Doom's rendering engine is known as a "Hall of Mirrors". This is typically caused by a the engine trying to display areas without textures. However, it can also be caused by the engine hitting a different limitation: a drawseg overflow. Drawsegs, as the name implies, are segments to be drawn during a frame. If there are too many, the engine simply stops drawing them, creating the Hall of Mirrors effect.

Many inexperienced map makers have experimented with making detailed objects using lots of LINEDEFs. The end result is often either slowdown or a graphical glitch, so the WAD parser uses a variation of the Visplane Analysis routine to locate areas that might trigger a drawseg overflow.

In this case, the hitboxes are artificially inflated, which makes them more likely to overlap. And, instead of sending out rays, this check simply drills down through every hitbox that is over a specific point.

As with the Visplane analysis, results in the Safe range are not expected to cause problems, while areas rated Critical may possibly trigger a Hall of Mirrors effect, and areas rated with Danger are very likely - if not expected - to become a weird blurry mess.

LINEDEF Problems

Maps in Doom are created using, among other things, LINEDEFs. These are small data structures that define the location and information about a piece of the map's geometry. They are also the source of many problems with Doom maps, especially when they've been configured wrong. Therefore, the WAD parser does its best to try and identify potential problems while it scans a map's LINEDEFs.

The simplest problem that can be encountered is a LINEDEF that doesn't have valid vector information. In the WAD file format, the coordinates used by LINEDEFs are stored in their own table instead of inside the LINEDEF structure itself. Each LINEDEF stores its start and end coordinates an indexes into this separate table. If the indexes are invalid, the engine will be in big trouble - it may try to read data from outside of the table as coordinates, or it may just implode and crash to the command line. Some source ports try to mitigate this problem by turning the affected LINEDEFs into a LINEDEF with no length, but it's still a sign that there's something wrong with the WAD itself.

Another, more common, problem is a LINEDEF with no length. In other words, the geometry it describes exists as a point, not a line - the start and end coordinates are the same location. These don't appear to exist in game, but they will technically count against the visplane and drawseg limits.

LINEDEFs like this are rarely made on purpose: it's much more likely that an editing program did something the author didn't intend. For example, an overly sensitive editor might have misinterpreted a brief click as a click-and-drag, causing it to draw a LINEDEF that was never meant to exist. Some editors might also have attempted to "erase" LINEDEFs by turning them into a point at the map's origin - a much simpler method than shifting the rest of the WAD's information to handle the change in geometry. And, as mentioned a moment ago, this is a way some source ports safeguard against broken LINEDEFs.

A similar issue with LINEDEFs are ones with impossible lengths. This is another form of editor mishandling. Maps in Doom work using a 16-bit coordinate system, which means they can place geometry and objects anywhere in a roughly 65,000 x 65,000 box. Map makers never use this full length though, so there's something glitchy about LINEDEFs with incredibly long lengths. Regardless of the reason, it's reported as a LINEDEF of "infinite" length.

The last potential problem the WAD parser looks for in the LINEDEF table are "double sided" LINEDEFs - LINEDEFs with the same front and back texture. There are valid reasons for map authors to design a LINEDEF like this (including some interesting special effects), so it's not an error as much as an unusual choice, but it can signal bigger issues like "leaky" sectors that don't behave as intended.

Missing Textures

In order for the engine to draw something, there must be data for it to use. Doom and Doom 2 provide a large library of textures for WAD editors to use, and there's nothing stopping someone from adding their own images for use as textures. As long as the textures exist in the base game or the WAD itself, everything will be fine.

But, it's easier than you'd think to get this wrong. All it takes is a single typo to mis-identify the intended texture. Also, there's evidence that some editors handled clearing texture information by attempting to "comment out" the original texture: since the engine treats textures beginning with a hyphen as "empty", some just prepended a hyphen to the texture's name and called it a day.

Missing textures will trigger the Hall of Mirrors effect when the player attempts to view them. This might be intentional, but it's very unlikely.

Final Notes

The WAD parser this website uses will probably never be truly finished, as there will always be new WADs to examine as long as the Doom community has creative people willing to share their creations with everyone.

As new features are added to the parser, this page will be kept updated to let everyone know how they work.