The blockmap is a data structure used for collision detection in a map, provided by the resource lump called
BLOCKMAP. It is used for a number of situations such as calculating when a moving Object hits a linedef or when two Objects (one or both moving) collide.
The blockmap is simply a grid of "blocks", each of which is a size of 128×128 fracunits. Each of these blocks stores a linked list of all linedefs, Objects and PolyObjects located within it. To perform collision detection for a moving Object, the game then only needs to search through the list of the block that the Object is inside to find map components that it might collide with, rather than searching through the entire map. Whenever an Object or PolyObject changes position, it is moved from the list of the old position's block to the list of the new position's block.
If an Object has the primary flag
MF_NOBLOCKMAP checked, the Object will be removed from the blockmap links for the block it is physically located in, making the Object effectively intangible to any moving Objects that would attempt to collide with it. This does not prevent such an Object from colliding with other Objects when it is moving itself, however.
When development mode is enabled and the automap is being shown, the blockmap for the current map can be seen by toggling the grid on. Note that not all maps will have a
BLOCKMAP lump included with them in a WAD or PK3 file; in this situation, SRB2 can build a new blockmap for the map from scratch. This is usually required when the map is too large for a blockmap to be successfully generated (due to a size limitation).
BLOCKMAP lump consists of three components: The header specifies the size and origin of the block grid. For each block, a blocklist lists all the linedefs contained in the block. To determine where each blocklist starts, an offset table is used.
|0–1||Signed 16-bit integer||X coordinate of the grid origin|
|2–3||Signed 16-bit integer||Y coordinate of grid origin|
|4–5||Unsigned 16-bit integer||Number of columns in the grid|
|6–7||Unsigned 16-bit integer||Number of rows in the grid|
The offset table starts at byte 8. It is a list of unsigned 16-bit integers, where each integer stores the offset to the blocklist for one of the blocks. The total number of blocks is the number of columns multiplied by the number of rows, as specified in the header. The offsets are expressed in units of two bytes. Since the maximum value in an unsigned 16-bit integer is 65,536, the maximum offset is therefore 128 kilobytes.
BLOCKMAP lumps can therefore be at most 128 KB large. However, if a map lacks a
BLOCKMAP because it would exceed this size limit, SRB2 can calculate the blockmap at runtime when the map is loaded.
Each blocklist is a list of all linedefs that are contained within the block, stored as signed 16-bits integers. The list is bookended by two dummy entries: The first entry is always
0x0000, while the last entry is always
0xFFFF. Any linedef on the border of two blocks will be placed only in the block on the east side of the line for vertical lines and the block on the north of the line for horizontal lines.