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 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 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]

This simple map of only four linedefs, with no compression techniques applied, has a blockmap length of 65534 bytes. This is because it covers a large area, causing its lines to pass through multiple blocks.

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 for a vanilla blockmap is approximately 65536 bytes + the amount of linedefs in the longest blocklist * 2 bytes. By combining the data from several blocklists into one big blocklist 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 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[edit]

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[edit]

Some source ports may rebuild the blockmap, possibly leading to changes in gameplay if certain blockmap special effects are in place.

The behavior of the original Doom engine in concert with the original blockmap builder used by id Software is inconsistent: the engine interprets the first entry in every blocklist as an actual linedef index and thus performs a clipping operation against that linedef. However, the blockmap builder created by id Software assumes that there is padding of one zero entry at the start of every blocklist. Building blockmaps with a zero header in every blocklist became common practice because it was assumed that this entry is skipped, when in fact it is not. By default, the vanilla game engine 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.

The source port Boom has a problematic, overreaching bug fix for this in which the zero-header is skipped unconditionally. This is done by blindly skipping the first entry in each blocklist, even if it is not a zero-header. This bug also exists in many source ports that use Boom as a base. Some source ports have fixed this bug when tools for building blockmaps without 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, 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 the inconsistent behavior.

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 blocklists.

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 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 2-byte shorts to skip, needing to be multiplied by two for a byte offset. For example, an entry containing the value of 200 references the 400th byte in the blockmap.

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 a list of all the linedefs colliding in this block and an 0xFFFF marker to signify that there are no more linedefs 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

Compression[edit]

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. There is also a type of compression-like algorithm that allows for very large blockmaps, larger than 65536 bytes, but these blockmaps have a set of strict limitations and can in some cases trigger bugs in the Doom engine's collision code.

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[edit]

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. Id's tool chain made a new blocklist for each block. By using the same blocklist for several blocks where their linedefs are identical, a significant saving can be achieved. This is especially important for empty blocklists, as these often occur in maps and outside the play area.

Oversized blockmap[edit]

Although the addresses used to index blocklists can only address up to the 65536th byte, this refers to the start of the blocklist. The rest of the blocklist can be beyond the 65536 bytes. By placing the longest blocklist at the end, the maximum size of the blockmap can be extended by about the size of the blocklist. 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[edit]

Most map tools produce blocklists in the tools format, with a leading 00 00 header in every blocklist. This is not handled correctly by Doom, and is instead read as linedef 0, leading to extra collision detection checks. Omitting this entry can significantly reduce the amount of bytes needed to produce a working blockmap. Doing this causes problems with a few older ports due to faulty optimizations. This bug has been fixed in most newer ports.

Mid blocklist offsets[edit]

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 and twice for the first blocklist.

In the example above the following two blocklists:

Blocklist Linedef Description Total size in bytes
1 0x0001 First entry in list 1. 2
1 0x0002 4
1 0x0003 6
1 0x0004 8
1 0x0005 10
1 0xFFFF End of list 1 12
2 0x0001 First entry in list 2. 14
2 0x0003 16
2 0x0005 18
2 0xFFFF End of list 2 20

can be compressed into the following combined blocklists:

Blocklist Linedef Description Total size in bytes
1 0x0002 First entry in list 1. 2
1 0x0004 4
1 and 2 0x0001 First entry in list 2 6
1 and 2 0x0003 8
1 and 2 0x0005 10
1 and 2 0xFFFF End of list 1 and 2 12

Blocklist merging[edit]

List merges refers to the technique of merging two or more blocklists that both have linedefs not in the other blocklist(s). 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 to one needing only one 0xFFFF end marker. For each linedef the two lists have in common, another two bytes will be saved.

Geometry simplification[edit]

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.

Source[edit]