NODES

From ZDoom Wiki

Nodes are probably the most complicated structure present in Doom WADs (Doom and Hexen format alike). The information within this page is not at all necessary knowledge if you want to build ZDoom (or any kind) of maps, it's mainly here for completeness and for anyone seeking further information on the inner workings of Doom and the structure of maps and WADs.

Nodes and their related structures (SEGS and SSECTORS) all pertain to rendering the level. Often Doom maps are pretty large and only in very rare cases is every line of a map visible from every point (and most of those maps you'll want to avoid anyway). As is the case, it doesn't make any sense for the engine to draw every single wall and pillar at the same time since you probably can't see more than 10% of the average map at any one time (that is variable of course, I'm just making a generalization). If the engine took up such a task the game would run much, much slower (to the point of near standstill) and would be painfully unplayable, even if the map was the size of, for instance, Doom 2 MAP02.

This is where nodes come into play. Nodes are branches on something called a binary space partition or BSP for short. In what is a rather complex algorithm, BSP divides up your map over and over in order to determine which walls are in front of others. The basic idea is to split the map in half and then split each half in half and so on until you're left with the smallest possible space in which all wall segments within (those are the SEGS) cannot possibly occlude any other walls within the same space. That space is called a SSECTOR (sub-sector).

Only sectors are divided, and thus no sub-sector can ever be in two sectors. SEGS are usually along linedefs, though most often some are created in order to form a proper sub-sector. For this reason nodes builders will also add extra vertices to a map in order to connect new segs properly (since segs, like linedefs, need starting and ending vertices).

The overall 'goal' of sub-sectors is to become a convex shape, which means that any line between any two points on the boarder of the shape will be contained in its entirety in the polygon (in other words, this new line will not intersect any of the lines of the shape). For reference, all triangles and rectangles are convex, however not all quadrilaterals are convex (parallelograms with no right angles, for instance, are not convex).

I won't get much more into the really technical details of it, such as how sub-sectors are put into a binary tree. However, if you want an idea of how a node builder might break up a simple, single sector, here's an image which is more or less accurate, though someone with more knowledge on the subject may want to provide a more accurate one as they see fit:

In this diagram the black lines are linedefs and the blue dotted lines are segs. Notice how all the sub-sectors are now convex. Also note that, though I didn't draw it, each linedef also becomes a seg and in the case of the top-most and bottom-most linedefs, those actually get split into three and two segs respectively for each spot where a seg intersects the line (which will have a vertex added there).

The final goal of the binary tree is to make each leaf of the tree be a sub-sector, though this is not really necessary and a lot of times inefficient when you're only dealing with around 1000 or so polygons (and most maps contain thereabouts or less), though many nodes builders have the option to control linedef splits. It's also worth noting that less segs (which results in less vertices) means the filesize will be smaller, and building nodes will greatly increase the size of your WAD file.

Specification

Bytes	Data Type	Description	Notes
0-1	Short	X position of partition line	(?)
2-3	Short	Y position of partition line	(?)
4-5	Short	Change in X	(?)
6-7	Short	Change in Y	(?)
8-9	Short	Y upper bound for right box	(?)
10-11	Short	Y lower bound for right box	(?)
12-13	Short	X lower bound for right box	(?)
14-15	Short	X upper bound for right box	(?)
16-17	Short	Y upper bound for left box	(?)
18-19	Short	Y lower bound for left box	(?)
20-21	Short	X lower bound for left box	(?)
22-23	Short	X upper bound for left box	(?)
24-25	Short	Node or sub-Sector for right child	(?)
26-27	Short	Node or sub-Sector for left child	(?)