Node

From DoomWiki.org

NODES is the name of a WAD lump which is a component of a level. It is normally generated automatically from other data for the level using a node builder tool.

The nodes lump constitutes a binary space partition of the level. It is a binary tree that sorts all the subsectors into the correct order for drawing. Each node entry has a partition line associated with it that divides the area that the node represents into a left child area and a right child area. Each child may be either another node entry (a subnode), or a subsector on the map.

Node structure[edit]

Doom level format
Offset Size (bytes) C99 type Description
0 2 int16_t x coordinate of partition line start
2 2 int16_t y coordinate of partition line start
4 2 int16_t Change in x from start to end of partition line
6 2 int16_t Change in y from start to end of partition line
8 8 int16_t [4] Right bounding box
16 8 int16_t [4] Left bounding box
24 2 int16_t Right child
26 2 int16_t Left child

Each of the two bounding boxes describe a rectangle which is the area covered by each of the two child nodes respectively. A bounding box consists of four short values (top, bottom, left and right) giving the upper and lower bounds of the y coordinate and the lower and upper bounds of the x coordinate (in that order).

The type of each child field is determined by its sign bit (bit 15). If bit 15 is zero, the child field gives the node number of a subnode. If bit 15 is set, then bits 0-14 give the number of a subsector.

Example: E1M1[edit]

Root node division of E1M1

This diagram shows the root node division of the level E1M1: Hangar. (The root node is the highest-numbered entry in the lump.) The partition line is shown in yellow, with a small hash mark drawn at the midpoint of its right side. The partition line is extended in both directions using a blue line. The right bounding box is drawn in green, and the left bounding box is drawn in red.

As expected, the partition line divides the map roughly in half. All points on the map are either to the right or left of the root node partition line. The right bounding box appears on the west side of the diagram because the partition line runs downward (from north to south), as noted by the hash mark on its west side.


Division of first left subnode in E1M1

The second diagram shows how the first left subnode is further subdivided. The bounding boxes overlap, but it is the partition line that is used to determine which subnode of this node any particular point belongs to.


See also[edit]

Source[edit]