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.
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.
| Bytes | Value | Comment |
|---|---|---|
| 0-1 | -128 | X coordinate where the first cell spans from, starts on left side of the map. |
| 2-3 | -256 | Y coordinate where the first cell spans from, starts on the bottom of the map. |
| 4-5 | 2 | Amount of 128 unit wide cells in X direction. |
| 6-7 | 2 | Amount of 128 unit wide cells in Y direction. |
| 8-9 | 16 | Offset to the first blockmap list. |
| 10-11 | 0022 | Offset to the second blockmap list. |
| 12-13 | 0022 | Offset to the second blockmap list. |
| 14-15 | 0028 | Offset to the final blockmap list. |
| 16-17 | 0000 | Linedef 0 is in this grid cell. |
| 18-19 | 0002 | Linedef 2 is in this grid cell. |
| 20-21 | FFFF | End of first block list-marker. |
| 22-23 | 0001 | Linedef 1 is in this grid cell. |
| 24-25 | 0002 | Linedef 2 is in this grid cell. |
| 26-27 | 0004 | Linedef 4 is in this grid cell. |
| 28-29 | 0005 | Linedef 5 is in this grid cell. |
| 30-31 | FFFF | End of second block list-marker. |
| 32-33 | 0003 | Linedef 3 is in this grid cell. |
| 34-35 | 0006 | Linedef 6 is in this grid cell. |
| 34-35 | 0007 | Linedef 7 is in this grid cell. |
| 36-37 | FFFF | End 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 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.
It should be noted that ZokumBSP also supports adding the 0000 entry as the last entry in a blockmap list.
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.
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.
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.
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.
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.
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.
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.
| Bytes | Value | Comment |
|---|---|---|
| 16-17 | 0020 | Points to a list with 5 lindefs, bytes 20-31. |
| 18-19 | 0026 | Points to a list with 2 lindefs, bytes 26-31. |
| 20-21 | 0000 | Linedef 0 is in only one set. |
| 22-23 | 0002 | Linedef 2 is in only one set. |
| 24-25 | 0004 | Linedef 4 is in only one set. |
| 26-27 | 0001 | Linedef 1 is found in two sets, start of second sub set. |
| 28-29 | 0003 | Linedef 3 is found in two sets. |
| 30-31 | FFFF | End of the block list-marker. |
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:
| Bytes | Value | Comment |
|---|---|---|
| 14-15 | 0026 | Points to a list with 2 lindefs, bytes 26-31. |
| 16-17 | 0026 | Points to a list with 3 lindefs, bytes 24-31. |
| 18-19 | 0020 | Points to a list with 5 lindefs, bytes 18-31. |
| 20-21 | 0000 | Linedef 0 is in only one set. |
| 22-23 | 0002 | Linedef 2 is in only one set. |
| 24-25 | 0004 | Linedef 3 is found in two sets, start of second sub set. |
| 26-27 | 0001 | Linedef 1 is found in three sets, start of third sub set. |
| 28-29 | 0003 | Linedef 4 is found in three sets. |
| 30-31 | FFFF | End of the block list-marker. |
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.
| Critera | Rationale |
|---|---|
| 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. |
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.
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.
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.
By sorting the blocklist one can much easier find duplicate lists and whether a list is a sub set of another list.
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.