Blockmap
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).
For Lua scripting, the searchBlockmap function can be used to search through the blockmap for either Objects or linedefs stored within it.
Lump structure
The 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.
Header
| Bytes | Data type | Description |
|---|---|---|
| 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 |
Offset table
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.
Blocklists
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.
External links
| Map components | [view] | |
|
Thing • Linedef • Sidedef • Vertex • Node • Sector • Reject • Blockmap | ||