Blockmap

From DoomWiki.org

Doom level format

The blockmap is a data structure used for collision detection. That is, the blockmap is used for calculating when a moving thing hits a wall or when two things (one or both moving) collide. The blockmap is simply a grid of "blocks"' each 128×128 units (or double the size of the floor grid). The blockmap can be seen by enabling "grid" mode in the automap.

Similar to how NODES are used for calculating when a line should or should not be drawn, the BLOCKMAP lump is used for calculating a thing/wall collision. Every block contains zero or more linedefs. To detect collisions between a moving thing the Doom engine only needs to run calculations on linedefs in the same block as the moving thing (rather than all the linedefs in the entire map).

Internally the blockmap is also used for thing/thing collisions with each block maintaining a dynamic list of all things contained within it. Using the same principle as thing/wall collisions, the engine needs only to check for possible collisions with every thing sharing the same block as the moving thing.

Removing the blockmap from a level will not affect the rendering of the level or any line of sight calculations, but all collision detection will be nonfunctional. It should be noted that modern source ports will usually build a new blockmap from scratch if one does not exist; it is an easy quick operation and internally created blockmaps need not be subject to the same size restrictions as wad lumps.

Due to the way the original engine did calculations, if a thing's center was on the very edge of a block and another's center was on the edge of an adjacent block it would be abstained from collision detection since both things were actually in different blocks. This bug, which no doubt many players are familiar with, is a result of the original exe (and many current ports) only using the center of a thing to determine if it was in a block and not taking its entire radius into account. Colin Phipps provides an explanation of the phenomenon. It was fixed in ZDoom, however this alters the gameplay by making actors easier to hit.

Size limitations[edit]

The size limitations in the blockmap data structure offset puts some upper limits on the maximum size of a level. Various techniques have been invented to pack more data into the blockmap entry without breaking compatibility. A very common technique is to combine references to identical block lists by making them all point to the same blocklist instead of multiple identical blocklists. The original tool chain from id had no such optimizations and produced very large blockmaps.

The maximum size for a vanilla blockmap is approximately 65536 bytes + the amount of linedefs in the longest blocklist * 2 bytes. By combining the data from several block lists into one big list that is very long, it is possible to produce blockmaps that are well above the 65536 byte limit. This will lead to decreased performance and possibly higher chance of buggy collission detection due to bugs in other parts in the code base. Many ports have fixed these bugs, but some retain them for demo playback compatibility.

Source port notes[edit]

Some source ports may rebuild the blockmap, possibly leading to changes in gameplay. The source port Boom also had a problematic optimization where the zero-header was skipped. This is done by blindly skipping the first entry in the blockmap lists, even if it isn't a zero-header. This bug also exists in many source ports using Boom as a base. Some source ports have fixed this bug when tools for building blockmaps with the zero-header became available.

Some source ports allow for unsigned blocklist references, effectively doubling the blocklist address space.

In April 2018 a test suite for blockmaps, Blockrocking Beats, was released. It contains various unusual blockmaps that are compatible with the original executable and Chocolate Doom but may fail with ports that aren't fully compatible with the original Doom.

Lump structure[edit]

Block #461 of The Inmost Dens in Doom II has 53 linedefs.

Blockmaps are composed of three parts, the header, offsets and the blocklist.

Header[edit]

Offset Size (bytes) Description
0 2 x coordinate of grid origin
2 2 y coordinate of grid origin
4 2 Number of columns
6 2 Number of rows

Offsets[edit]

Offset Size (bytes) Description
8 2 Offset to block 0
10 2 Offset to block 1
. . .
8 + 2 × (N - 1) 2 Offset to block N - 1

Note that there are N blocks, which is equal to columns × rows (from the header). All offsets are relative to the start of the BLOCKMAP lump. Also, the offsets are not in bytes, but in signed 2-byte shorts. The offsets are saved as 2 byte signed shorts with the least significant byte first. This means that an entry containing the value of 200 references the 400th byte in the blockmap. To compute a blocklist offset of f.ex DF 00, reorder it to 00 DF, multiply it by 2 to get the byte in the blockmap file that is being referred to, 1BE. This means that the blocklist for that block beings at byte 0x1BE in the blockmap data lump.

Blocklists[edit]

Blocklists for the original executable generally have two accepted formats. These are sometimes referred to as the executable format and the tool format. Id's toolchain added an extra 2-byte zero-header at the start of each blocklist. This entry is handled by the engine as linedef 0. The engine expects lists of all the lindefs and a FF FF marker to signify that there are no more lindefs in the list. Due to most tools imitating the id tool chain, most wads have blocklists with the zero-headers. As of 2016, ZokumBSP can produce blocklists without the zero-header. Any linedef on the border of two blocks will be placed in only the block on the east side of the line for vertical lines and the block on the north of the line for horizontal lines.

Engine format[edit]

Size (bytes) Description
2 First linedef within the block
2 Second linedef within the block
. . .
2 0xFFFF

Tool format[edit]

Size (bytes) Description
2 0x0000
2 First linedef within the block
2 Second linedef within the block
. . .
2 0xFFFF

Source[edit]

See also[edit]