Blockmap
From DoomWiki.org
| Doom level format |
|---|
Source port extensions: |
The blockmap is a data structure used for collision detection. That is, the blockmap is used for calculating when a moving mobj hits an obstruction. The blockmap envelops the entire level and is divided into a grid of blocks 128×128 units each (which is double the size of the flat grid). The blockmap can be seen by enabling the grid in the automap, available by pressing G in the automap in vanilla Doom. The part of this structure that pertains to collisions with linedefs is prebuilt and located inside the WAD as the level's BLOCKMAP lump, however mobjs are added and removed from blocks while the game is running.
Similar to how NODES are used for calculating when a line should or should not be drawn, the blockmap is an optimization that avoids the need for slow, brute force calculation. When an object can potentially collide with another object—be it a linedef colliding with either a hitscan attack or a mobj, or a hitscan attack and mobj colliding—the block(s) at or around the object is checked for other objects. This way, the Doom engine only needs to consider objects close to each other for collision, which is significantly more efficient than checking all objects in the entire map when something shoots or moves.
Removing the blockmap from a level will not affect the rendering of the level or any line of sight calculations, but all collision detection that relies on the blockmap will be nonfunctional. This can be done via manual editing, but it can also happen as a glitch during gameplay, known as the all-ghosts effect. It should be noted, that modern source ports (starting from Boom) will usually build a new blockmap from scratch if one does not exist initially; it is quick operation, and on-the-fly created blockmaps need not be subject to the same size restrictions as those precomputed inside the WAD.
Though the blockmap is intended as only an optimization, it also comes with significant gameplay-affecting glitches due to various oversights in how the engine interacts with it. The most notable of which is that if a mobj's center is on the very edge of a block so that its radius extends to the next block over, and a hitscan attack touches this radius extended into this next block, collision detection fails entirely, jointly because hitscan attacks purely affect blocks they overlap and a mobj can only exist in one block at a time. This is especially noticeable with extra wide monsters, such as the arachnotron or spiderdemon. Colin Phipps provides an explanation of the phenomenon. It is fixed in ZDoom and Woof, however this alters the gameplay by making actors easier to hit—both for the player and monsters.
Contents
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 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 a 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—roughly speaking—a function of both the enveloping square area of a map 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 the vanilla format limitations, and vice versa; removing lines allows for a comparatively larger amount of space. The blockmap builder tool's capabilities and biases have final say, however; its capabilities may include compression techniques that attempt to counter an increasing linedef count, such as by merging several blocklists into a single blocklist. Biases play a smaller role and include determining the offset of the blockmap, what to do with edge cases, and the details of applying compression.
Source port notes[edit]
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 by using an heuristic to restrict the fix to blockmaps which actually double the listing of line 0 in every block.
- 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[edit]
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[edit]
| 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[edit]
| 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[edit]
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[edit]
| 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[edit]
| Byte size | Description |
|---|---|
| 2 | 0 |
| 2 | First linedef index |
| 2 | Second linedef index |
| . . . | |
| 2 | -1 |
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.
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]
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[edit]
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[edit]
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[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.
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[edit]
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[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.
Other structures[edit]
When a map is being loaded, memory structures are built to determine in which blockmap blocks mobjs and sectors are. Blocklists are the only such structure that is pre-generated.
Blocklinks[edit]
The blocklinks array holds a slot for each block, wherein mobjs are updated whenever they move. A mobj 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 mobjs moving in and out, it is implemented as a linked list, where a mobj holds the previous and next mobjs in the block while the blocklink slot only holds the first, avoiding the need to maintain a shrinking and growing list.
Blockboxes[edit]
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 mobjs 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 mobjs are updated when the sector moves. Blockboxes are used without consideration for whether or not mobjs 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.
Related bugs[edit]
The following are engine bugs stemming from interactions with the blockmap in the engine that violate the ideal that the blockmap should be a pure optimization. Some listings are notorious bugs that have dedicated articles.
- All-ghosts effect: When the engine draws a line to detect walls or things in that line, this information is saved to an array in memory. Detecting too many objects will overwrite memory belonging to the blockmap, corrupting it. As a result, interactions involving the blockmap will only work in a limited capacity (if a specific number of intercepts are overflowed) or break entirely, requiring a level restart.
- Bullets can ignore actors: Because of the joint interaction of a mobj only being able to exist in one blockmap tile, the one under its centre, despite having width and possibly extending out of the tile, and a tracer (e.g. autoaim detection, or a bullet's path) detecting mobjs only in the blockmap tiles directly under its path, collision detection by the tracer can fail to detect a mobj because the mobj has its centre in a blockmap tile untouched by the tracer.
- Wide actors can get stuck by things walking inside them: Similarly, since actors can only stand in one blockmap tile, and outside collision detection can therefore miss a particularly wide actor extending far past its tile, it is possible for mobjs to walk inside a very wide mobj and get the wide mobj stuck. This is likely to happen in community-made levels where hordes of demons accompany a spiderdemon.
- Bullets may be stopped by thin air: The original level-editing tools used by id Software—and many third-party tools—place linedef 0 into every blockmap tile even when it does not touch that tile. Though it leads to redundant collision checks, it more significantly leads to collision detections over distances that are too great, leading to overflow and collisions that are considered closer (or father away) than intended. As a result, casting tracers (e.g. hitscan attacks) in the direction of linedef 0 in a level built to this specification can lead to collisions with this linedef happening at wrong distances. This is a primary contributor to a more general bug with its own article.
- Overeager mobj updating when nearby sectors move: A sector (such as a lift) updates the heights of mobjs in the vicinity. Notably, things in the vicinity include things not touching the sector, as the mobjs only need to be in the blockbox to be eligible for updates. This exacerbates a problem of said updates having buggy behavior, a significant factor leading to the bug where mobjs may snap up to ledges. This is fixed in Boom, making things only touching the sector get updated.
- Overeager collision detection termination when a blocking linedef is found: When collision detection traverses linedefs, it stops when it finds an impassable linedef, meaning an obstruction was found and skipping checking remaining linedefs. These linedefs are in the order determined by the relevant blockmap tile's blocklist. This is a problem when side effects can happen when traversing linedefs, because random data order inside the map that is invisible to the player is used to determine gameplay effects.
- Moving sectors can fail to collide with wide actors: Due to the way blockboxes (the bounding box around a sector) are determined, very wide actors (in particular, the spiderdemon) may fail to collide with a moving sector. For example, if a lift moves up while the wide actor is standing on its edge, the wide actor can fail to collide with the rising lift and subsequently remain on the ground unable to move because its side is stuck inside the lift. This happens because the sector's bounding tiles (wherein collision is detected) are determined to be those enveloping the sector's bounding box with some extra map units of allowance, however this extra allowance is not enough for very wide mobjs.
- Blast damage can hit the same actor multiple times: Due to blast damage hurting monsters in a given blockmap tile's blocklinks (the list of actors standing on that tile) sequentially, and it being possible for that sequence to have its order altered mid-traversal, it is possible for the engine to traverse these blocklinks and encounter the same actor twice and therefore deal damage to it twice.
Source[edit]
- This article incorporates text from the open-content ZDoom documentation project article BLOCKMAP.
External links[edit]
- ZokumBSP blockmap theory, details as they pertain to ZokumBSP
