Blockmap

From DoomWiki.org

Doom level format

Extensions:

The blockmap is a data structure used for collision detection. That is, the blockmap is used for calculating when a moving thing hits a wall or when two things (one or both moving) collide. The blockmap is simply a grid of "blocks"' each 128×128 units (or double the size of the floor grid). The blockmap can be seen by enabling "grid" mode in the automap.

Similar to how NODES are used for calculating when a line should or should not be drawn, the BLOCKMAP lump is used for calculating a thing/wall collision. Every block contains zero or more linedefs, though normally not too many (and certainly not as many as the entire map) and so in detecting collisions between a moving thing the Doom engine only needs to run calculations on every linedef in the same block as the moving thing (rather than the entire map).

Block #461 of The Inmost Dens in Doom II has 53 linedefs.

Internally the blockmap is used for thing/thing collisions with each block maintaining a dynamic list of all things contained within it. Using the same principle as thing/wall collisions, the engine needs only to check for possible collisions with every thing sharing the same block as the moving thing.

Removing the blockmap from a level will not affect the rendering of the level or any line of sight calculations, but all collision detection will be nonfunctional. It should be noted that modern source ports will usually build a new blockmap from scratch if one does not exist; it is an easy quick operation and internally created blockmaps need not be subject to the same size restrictions as wad lumps.

It is also worth noting that because of the way the original engine did calculations, if a thing's center was on the very edge of a block and another's center was on the edge of an adjacent block it would be abstained from collision detection since both things were actually in different blocks. This bug, which no doubt many players are familiar with, is a result of the original exe (and many current ports) only using the center of a thing to determine if it was in a block and not taking its entire radius into account. Colin Phipps provides an explanation of the phenomenon. It was fixed in ZDoom, however this alters the gameplay by making actors easier to hit.

Contents

[edit] Lump structure

Blockmaps are composed of three parts, the header, offsets and the blocklist.

[edit] Header

Offset Size (bytes) 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

[edit] Offsets

Offset Size (bytes) Description
8 2 Offset to block 0
10 2 Offset to block 1
. . .
8 + 2 × (N - 1) 2 Offset to block 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 unsigned, meaning they can go up to 65535 instead of 32767 (like most other WAD structures). Also, the offsets are not in bytes, but in shorts, so the maximum size for a vanilla blockmap is approximately 128KB, not 64KB.

[edit] Blocklists

Size (bytes) Description
2 0x0000
2 Linedef 0 within the block
2 Linedef 1 within the block
. . .
2 0xFFFF

The blocklist always begins with 0 and ends with -1. In between is a listing of all linedefs which have any portion within the block. Any linedef on the border of two blocks will be placed in only the block on the right side of the line for vertical lines and the block on the top of the line for horizontal lines.

[edit] Source

[edit] See also