|Frontpage|     |Documentation|     |Blockmap theory|     |Downloads|

Blockmap theory

This is a list of algorithms, concept and format specification useful for those who want a deeper understanding of what a blockmap is, how ZokumBSP works, and how to implement similar algorithms in other blockmap generators.

Blockmap WAD formats

The blockmap format used in DOOM and derived engines generally come in one format, with two subversions. The output that the engine expects is different from what Id's own blockmap tool produced.

Doom engine 'primary' format

The blockmap format is fairly simple. It consts of three main parts. A very short header, a set of offset, known as the grid or offsets, since it is a list of offsets, and the block lists, or just lists for short.


X-origin, 2 bytes (INT16) Y-origin, 2 bytes (INT16) Grid columns, 2 bytes (UINT16) Grid rows, 2 bytes (UINT16)


The header is immediatly followed by a certain amount of 2 byte (UINT16) offsets. The amount of offsets in this grid is the the amount of columns times the amount of rows specified in the header. Each offset points to a variable length lists found in the blockmap.

The grid represents 128*128 game units that enable the engine to quikcly look up what lines are found in an area in order to quickly determine collisions. An empty area should generally point to an empty list.


The final part of a blockmap is a collection of variable amount lists. This lists are referenced in the grid offsets. The size of the lists elemnt depends greatly on the level geometry.

Each list is simply a listing of the linedefs found in that grid. With a final sentinel value of 0xFFFF to represent a list end.

Example blockmap

0-1-128X coordinate where the first cell spans from, starts on left side of the map.
2-3-256Y coordinate where the first cell spans from, starts on the bottom of the map.
4-52Amount of 128 unit wide cells in X direction.
6-72Amount of 128 unit wide cells in Y direction.
8-916Offset to the first blockmap list.
10-110022Offset to the second blockmap list.
12-130022Offset to the second blockmap list.
14-150028Offset to the final blockmap list.
16-170000Linedef 0 is in this grid cell.
18-190002Linedef 2 is in this grid cell.
20-21FFFFEnd of first block list-marker.
22-230001Linedef 1 is in this grid cell.
24-250002Linedef 2 is in this grid cell.
26-270004Linedef 4 is in this grid cell.
28-290005Linedef 5 is in this grid cell.
30-31FFFFEnd of second block list-marker.
32-330003Linedef 3 is in this grid cell.
34-350006Linedef 6 is in this grid cell.
34-350007Linedef 7 is in this grid cell.
36-37FFFFEnd of the last block list-marker.

This is a very small blockmap of 38 bytes, representing a map with 8 linedefs, and a a size at or below 256*256 game units. Take notice that this is a 'compressed' blockmap. Two of the grid cells both have offsets to the same block list.

IdBSP 'secondary format'

This is implemented in ZokumBSP

IdBSP adds a 'header' value for each list, a 0000 entry is always the first entry in a list. The engine treats this as a reference to linedef 0. This dummy entry changes gameplay slightly, and playing back demos recorded with an otherwise identical blockmap, without this header, may lead to desynching.

Zero-footer format

This is implemented in ZokumBSP

It should be noted that ZokumBSP also supports adding the 0000 entry as the last entry in a blockmap list.

Blockmap compression

Blockmap compression is the act of making a smaller blockmap than a naive implementation. Id's own original node builder has no compression and will generate a new block for every cell in the grid, even if there are identical lists already constructed. None of the maps in the original Doom games are close to the maximum size of the blockmap lump.

Mathematical representation

Each block list can be seen as a set, a collection of numbers. Set theory is a branch of mathmatics that deals with groups of numbers.

Identical list compression

This is implemented in ZokumBSP

This is the blockmap compression found in ZenNode originally and it seems BSP also features a variation of this. The General idea is to look at previously generated lists to see if a similar list already exists, a list that is an identical set.

The original ZenNode implementation has special handling for empty blocks, and will always make the grid offsets point to the same empty set. Since ZenNode uses the 0-header format, the set it points to { 0 }, will always contain 0. Due to a questionable optimization, it will not check the full range of lists and often create duplicate sets. This most notcably makes it easily find identical blocks in the same row, but not in other rows.

Offset variation compression

This is implemented in ZokumBSP

By selecting a different offset, different lines can end up in different blocks, and the amounts of blocks needed to make a grid covering all the level geometry may change. This can lead to changes in the size of the blockmap. IdBSP uses the leftmost and bottom-most vertex coordinates and add a safety margin of 8 game units. This not needed, the game handles a blockmap with vertexes on the edge just fine. ZenNode and possibly other there uses offsets of 0,0 compared to Id's 8,8.

By varying the offsets one might get values where all the lines line up in such a way that the blockmap size is lower than with 0,0 or 8,8. If only one value is chosen, 0,0 should be best, since it will always lead to the smallest possible grid size. Adding a safety margin will sometimes lead to the need for more cells in the grid.

Offsets bigger than 127 are never better than smaller offsets, due to the fact that this leads to a buffer of a row or column of empty cells outside the level geometry. Thus in order to find the optimal offset, all 128*128, 65536, different offset combinations should be tested.

ZokumBSP can do several types of offset testing. The default is to test a few values from 0 to 48 in 8 unit increments in X and Y direction. This means it tests both 0,0 and 8,8, but also values like 4,4 and 12,8 and 24,16 etc. This is chosen due to the fact that most level geometry tends to line up on a grid of 8, and to keep the amount of offsets checked (36) down to a reasonable level in order to avoid excessive exection time.

A heuristic brute force option is also added. It will try all 128*128 offsets except the offsets where this generates both a new row and a new column of cells. Either one of them is acceptable alone. This can reduce the amount of blockmaps being tests significantly on some levels. ZokumBSP has code to discard a blockmap being built if it's already bigger than a previously best blockmap.

A brute force search is simply a search of the entire possible offset space that doesn't lead to identical list data, 65536 combinations of offsets. ZokumBSP has code to discard a blockmap being built if it's already bigger than a previously best blockmap.

Sub set block list compression

Every block list is a set. If we have a set {0, 1, 2, 3, 4} then the sets {0, 1, 2} and {1, 3, 4} are both sub sets of the first set. All the numbers in a sub set are founds in the parent set.

Full sub set compression with identical offsets.

This is implemented in ZokumBSP

The idea behind sub set compression is to not only just compress identical sets, but also by letting sub sets be represented by the parents set. ZokumBSP achieves this by sorting all the sets based on their size and starting with the biggest set first and then check to see if any later sets are sub sets of an earlier set and instead point to that. This means that the game will check one or more unnecessary lines if the subset is smaller that the parent set. This can provide a significant reduction in the size of the list part of a blockmap.

Offset optimized optimal run speed sub set compression.

This is not implemented in ZokumBSP

The offsets found in the grid point to a list, but it does not have to point to the first item in a list. If one has a list A {0, 1, 2, 3, 4} then {1, 3} is a sub set of this set. By reorganizing the order of the block list entries and incrementing the sub set offset, a valid blockmap can be built that doesn't slow down the run time performance like full sub set compression with identical offsets do.

One takes the set {0, 1, 2, 3, 4} and splits it into two sub sets. The first set is all the numbers found in only the first set {0, 2, 4}, the second set contains all the numbers found in both sets, {1, 3}. The second sub set should in this case be identical to the small set we had originally. The sets are then added to the blockmap lists with all the numbers from the first sub set, then the other sub set.

16-170020Points to a list with 5 lindefs, bytes 20-31.
18-190026Points to a list with 2 lindefs, bytes 26-31.
20-210000Linedef 0 is in only one set.
22-230002Linedef 2 is in only one set.
24-250004Linedef 4 is in only one set.
26-270001Linedef 1 is found in two sets, start of second sub set.
28-290003Linedef 3 is found in two sets.
30-31FFFFEnd of the block list-marker.
This type of compression would be just as fast run time as identical block list compression, but could yield smaller blockmaps. It may not compress as well as a full sub set compression due to the fact that several sub sets can exist for a set which could leave the sub sets inconsistent or containing redundant linedefs in the set. Consider set A {0, 1, 2, 3, 4} and the sets B {1, 3, 4} and C {2, 4}. B and C are sub sets of A, but A cannot be partitioned into sub sets that satisfy the property that all sub sets can be put in an order in the block list in which no unncessary lines are checked ruin-time. Having the order as {0, 2, 1, 3, 4} would mean a valid offset for a list for set B could be created, but not for C, since it would have to point to 2, and that leads to a sub set {2, 1, 3, 4} which is different from set C.

It should be noted that the last sub set of the list could also contain a sub set within the sub set that corresponds to a set. A hypothetical set D {1, 4} would be such a set. This would yield the following blockmap data:

14-150026Points to a list with 2 lindefs, bytes 26-31.
16-170026Points to a list with 3 lindefs, bytes 24-31.
18-190020Points to a list with 5 lindefs, bytes 18-31.
20-210000Linedef 0 is in only one set.
22-230002Linedef 2 is in only one set.
24-250004Linedef 3 is found in two sets, start of second sub set.
26-270001Linedef 1 is found in three sets, start of third sub set.
28-290003Linedef 4 is found in three sets.
30-31FFFFEnd of the block list-marker.

Non collidable geometry removal compression

Algorithmic detection of non collidable geometry

This is implemented in ZokumBSP

A form of this type of compression is implemented in ZokumBSP using a stringent set of criterias to avoid false positives. The general idea is to remove linedefs which object never can collide with in regular gameplay. The use of this option, which is on by default, can lead to reductions in the lists and the grid size.

Linedefs can have types. Type 0 means it does nothing when activated, walked over, pressed space on or shot at while other types can invoke an action that may or or may not depend on the tag of the linedef and a corresponding sectors. Some types work directly on the sector on the other side, the D (direct) type found in many editors. In the classic Doom games, these are limited to only doors.

The various possible criterias for a linedef to be considered non-collidable if all of the criterias in a single set of conditions are met.

1. Map does not feature donut specials.The donut special is problematic since it makes sectors without a tag change height. The logic for figuring out which sector is the outer oof the donut is somewhat complicated
2. No raising stairs on the map.Raising star linedef specials can change the height of untagged sectors.
3. Linedef is two sided, not impassible, not blocking monsters, no type.If a line has a type or blocks something, it needs to be listed in the blockmap lists in order for invocation of the action to happen.
4. Both sides of the linedef belong to the same sector.This is found in a lot of Id's maps.

Manual removal of non-collidable geometry

This is implemented in ZokumBSP

By simply tagging a linedef with the value 999, that line is not used for any blockmap calculations. This is very useful for ceiling geometry and other places where no objects can collide. Although one might be able to create situations in which this might affect collision detection slightly, this is prferable to having a too large blockmap that will crash the game.

Simplified collission geometry

This is implemented in ZokumBSP 1.0.9

The idea behind a simplified collision geometry is to find linedefs that are actually sub lines of a longer line. Typically this happens when a wall is split into several linedefs to change texture, or a vertex is inserted to add a linedef with a special type in a different direction than the original line. ZokumBSP offers three levels of simplified geometry. This technique can greatly reduce the size of the BLOCKMAP due to reducing the amount of entries.

The algorithm used in ZokumBSP is somewhat simple. It features three different levels of optimization. Level 0 is the default, removing only linedefs tagged with the tag 998 from the in game rendering. Level 1 will try to merge extending lines when they have the same sector properties. Level 2 will in addition to the merges in level 1 also simplify one-sided walls that belong to different sectors.

It should be noted that the algorithm adds more linedefs to a map. This is currently a one-way operation, so it's not recommended to do this without specifying a seperate output file. Reversing the process by hand is possible. New linedefs are added to the end of the list, one could delete all linedefs at the end of the list where the linedef is superimposed on other linedefs.

Further improvements could be made by merging lines by adding a new super line that passes through the outside of the map. This would be beneficial due to the higher chance of getting identical lists. Doing such an optimization would require a much more sophisticated algorithm that can detect whether a line would pass through playable areas in a map.

Additional blockmap algorithms

There are some algorithms that can be used to quicker find a good blockmap. This is especially important for big maps and many offset variations.

Sorting the blockmap list

This is implemented in ZokumBSP

By sorting the blocklist one can much easier find duplicate lists and whether a list is a sub set of another list.

Boundary box exclusion

This is implemented in ZokumBSP

On a big map, even if one uses a sorted list, one ends up testing a lot of lists that a human could trivially say isn't a match. There are some interesting checks one can do to improve this.

If a cell contains walls that are horisontal, it can only be identical or a sub set of lists that are in the same row. Likewise if a list contains vertical lines, any suitable lists must lie in the same column.

If a block contains both vertical and horisontal linedefs, it cannot be a sub set or identical to another list, as there are no other cells that are both in the same column and row.

Finally, duplicate lists and sub sets can only be found in nearby blocks, corresponding to the length of the shortest linedef, integer divided by 128 + 1 blocks away. So if a cell has a 64 length linedef, it can only be found in blocks (64/128)+1 = 1 block away. A line must be at least 128 units long in order to span 3 blocks.

Implementing all these criterias greatly reduce the amount of list comparisons needed as most cells cannot contain all of the lines found in the cell we are trying to reuse a blockslist for.