Blockmap

Doom level format
Things Linedefs Sidedefs Vertices Segs Subsectors Nodes Sectors Reject Blockmap
Extensions: Behavior FraggleScript ACS GL nodes Macros Leafs

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 flat 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 does calculations, if a thing's center is on the very edge of a block and another's center is 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 engine (and many current ports) only using the center of a thing to determine if it is in a block and not taking its entire radius into account. Colin Phipps provides an explanation of the phenomenon. It is fixed in ZDoom, however this alters the gameplay by making actors easier to hit.

Size limitations

This simple map of only four linedefs will typically have a blockmap size of approximately 65536 bytes when built with map creation tools that use identical blocklist compression. The vast majority of its size consists of offsets, as there are few linedefs and the blocklists are easily compressed.

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 blocklists 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 of a blockmap that is fully functional in vanilla Doom is 65534 bytes + the bytes after this 65534 byte mark belonging to blocklist(s) that begin at or before this 65534 byte mark. This is because an offset, being a signed short integer, can at most hold the value 32767, which is doubled to be a byte offset of 65534, and parsing within a given blocklist can continue past this byte offset. By combining the data from several blocklists into one big blocklist that is very long, it is possible to produce blockmaps of sizes well above this 65534 byte mark. This will lead to decreased performance and possibly higher chance of buggy collision 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.

Blockmap size versus map area and complexity

The size of a blockmap is a function of both the total area of a map (ie., the number of 128x128 blocks it covers) and the complexity of the map in terms of the number of linedefs. The more complex a map is in terms of number of lines, the smaller the amount of space is that it can occupy without exceeding vanilla format limitations, and vice versa - fewer lines in a comparatively larger amount of space. The latter case is particularly subject to improvement via compression techniques, as several blocklists can be merged into a single blocklist.

Source port notes

The source port Boom and many ports that are derived from it make the following changes to the way blockmaps are handled:

• There is a problematic, overreaching bug fix that causes the zero entry to be skipped unconditionally. This is done by blindly skipping the first entry in each blocklist, even if it is not a zero entry. Some source ports have fixed this bug when tools for building blockmaps without the zero entry became available.
• Blocklist references are unsigned, raising the blocklist address space limit from 65534 to 131070.
• Blockmap dimensions are unsigned, though this is very unlikely to cause differences in behavior unless the blockmap is carefully designed to lead to such differences.
• The blockmap may get rebuilt, possibly leading to changes in gameplay if certain blockmap special effects are in place. Boom decides to do this when the size of the existing blockmap is 131072 bytes or greater, meaning the existing blockmap is discarded.

In April 2018 a test suite for blockmaps, Block Rocking Bytes, 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 vanilla behavior.

Lump structure

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

Blockmaps are composed of three parts, the header, offsets and the blocklists. All number fields in the blockmap are treated as signed short integers by vanilla Doom.

Header

Offset	Byte size	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

Offset	Byte size	Description
8	2	Offset to blocklist 0
10	2	Offset to blocklist 1
. . .
8 + 2 × (N - 1)	2	Offset to blocklist 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, and count the number of shorts to skip, needing to be multiplied by two for a byte offset. For example, an entry containing the short offset 200 represents the byte offset 400.

Blocks are ordered starting from the southwest in rows advancing north. This means that, for a given blocklist offset, the next blocklist offset would be for the neighboring east block, unless the resulting block amount in this row would be greater than the header specifies, in which case it is the westernmost block in the row above.

Blocklists

The engine expects a list of all the linedefs colliding in this block and a -1 entry (consisting of the bytes FF FF) to signify that there are no more linedefs in the list.

It is up to the blockmap building tool's discretion, but it is usually the case that 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

Byte size	Description
2	First linedef index
2	Second linedef index
. . .
2	-1

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 zero entry at the start of each blocklist. Building blockmaps with a zero entry in every blocklist became common practice because it was assumed that this entry is skipped, when in fact it is not, therefore most tools imitate the id tool chain in this regard and most WADs have blocklists with zero entries. Due to this, the vanilla game on maps built with these tools ends up checking collisions against linedef #0 for every operation. This can cause various bugs during gameplay, particularly in large maps where it results in numeric overflows. As of 2016, ZokumBSP can produce blocklists without zero entries.

Tool format

Byte size	Description
2	0
2	First linedef index
2	Second linedef index
. . .
2	-1

Compression

It is possible to use various techniques to compress the size of a blockmap compared to the implementation used by id Software. Using compression is the only way to build some large maps in a way that will not lead to runtime crashes in vanilla Doom and many source ports. A multitude of techniques are known, but most map building programs have implemented relatively unsophisticated compression algorithms.

The project Block Rocking Bytes has implementations of some of these algorithms and techniques to act as a test bed for source ports.

Identical blocklist compression

By using the same blocklist for several blocks where their linedefs are identical, a significant saving can be achieved compared to id's toolchain which made a new blocklist for each block. This is especially important for empty blocklists, as these often occur in maps and outside the play area.

This is one of the most basic and efficient ways to compress blockmaps. Up until 2016 it was the only compression scheme in use, even though other schemes had been suggested.

Oversized blockmap

By placing the longest blocklist(s) at the end, with their starting points within the allowed address space, 65534 bytes for vanilla Doom, the size of the blockmap can exceed the farthest address space as parsing within a given blocklist is not subject to this addressing limitation.

This technique was first used in a hand crafted blockmap for a test map in Block Rocking Bytes released in 2018 although the idea has been around for some time.

Engine format compression

Omitting the zero entry can significantly reduce the amount of bytes needed to produce a working blockmap. Doing this causes problems with Boom and some ports derived from it due to its blind skipping of the first entry. An example is Back to Saturn X MAP20 which makes use of this type of compression to work with vanilla Doom.

This zero entry is treated by vanilla Doom as linedef #0, as detailed in the Blocklists section.

Mid blocklist offsets

In some cases a blocklist can be a subset of another blocklist. One blocklist could contain the linedefs 1,2,3,4,5 and another the linedefs 1,3,5. By rearranging the linedef entries in the first blocklist and having the second one point into the middle of the first one, the two lists can be combined into one. This can be done without engine format compression, but this may trigger faulty collision code more often.

As an example, consider these blocklists:

Blocklist	Entry	Description	Total size in bytes
1	1	First entry in list 1.	2
1	2		4
1	3		6
1	4		8
1	5		10
1	-1	End of list 1	12
2	1	First entry in list 2.	14
2	3		16
2	5		18
2	-1	End of list 2	20

These two separate blocklists can be compressed into the following combined blocklists:

Blocklist	Entry	Description	Total size in bytes
1	2	First entry in list 1.	2
1	4		4
1 and 2	1	First entry in list 2	6
1 and 2	3		8
1 and 2	5		10
1 and 2	-1	End of list 1 and 2	12

Blocklist merging

List merges refers to the technique of merging two or more blocklists even though they may not have any shared linedefs. This is a variation of the mid list compression, but it will lead to unnecessary collision detection checks. There will always be at least 2 bytes saved when merging two blocklists, due needing only one -1 entry instead of two. For each linedef the two lists have in common, another two bytes will be saved.

Geometry simplification

Geometry simplification is when several co-planar linedefs are replaced with one linedef. This linedef is only used for the collision detection, while the shorter linedefs are used to generate segs for rendering. This simplifies the collision geometry, making blocklists shorter and makes it easier to use other compression techniques.

For a good example of this, look at Doom 2 map01. The central green hallway has several 64 length linedefs used to alternate textures. Tests done on Doom 2 with ZokumBSP have shown that replacing all those small segments with longer linedefs led to improvements from about 8% reduction in size on map31 to 1.2% reduction on map30, with most maps being in the 3 to 6 percent range.

Other structures

When a map is being loaded, memory structures are built to determine in which blockmap blocks things and sectors are. Blocklists are the only such structure that is pre-generated.

Blocklinks

The blocklinks array holds a slot for each block, wherein things are updated whenever they move. A thing can only be in one blocklinks slot at a time, meaning that as soon as it crosses the boundary of a block, it is removed from one and added to another. Since this structure is continually updated with arbitrary things moving in and out, it is implemented as a linked list, where a thing holds the previous and next things in the block while the blocklink slot only holds the first, avoiding the need to maintain a shrinking and growing list.

Because things can only exist in one block at a time, despite being able to overlap multiple blocks, this leads to problems such as the blockmap bug when attacking because neighboring blocks are not visited to check for thing overlaps.

Blockboxes

Each sector has a bounding box consisting of blockmap tiles. This is used for collision detection when the sector is moving. It is defined using its furthest vertex positions and is widened by 32 map units in all directions before this is converted to blockmap offsets. The widening by 32 map units is to better detect wide things overlapping the sector, though this is notably not enough to accommodate the spider mastermind, making it possible to get it stuck inside a rising lift.

Since sectors can be discontiguous and concave, this blockbox can span a very large area not occupied by any geometry belonging to the sector where things are updated when the sector moves. Blockboxes are used without consideration for whether or not things are actually inside the sector in question, which expands the area of effect where sector movement glitches such as things snapping up and sector blocking can take place.

Source

• This article incorporates text from the open-content ZDoom documentation project article BLOCKMAP.