Blockmap

From ZDoom Wiki
(Redirected from BLOCKMAP)
Jump to: navigation, search
DoomWiki.org
For more information on this article, visit the Blockmap page on the Doom Wiki.

The blockmap's purpose is 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 128x128 units (or double the size of the floor grid). If you want to see the blockmap just look at the automap and enable the grid.

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 it only needs to run calculations on every linedef in the same block as the moving thing (rather than the entire map).

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.

Interestingly enough, removing the blockmap from a level (though this is all but impossible with most modern ports, which will build a blockmap in memory if one is absent) will keep the behavior of everything the same (display of the map, enemy line of sight and so on), but everything can pass through impassible lines and nothing will be able to hit anything else.

It's also worth note 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 of you are familiar with, is a result of the original exe (and no doubt 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. You should note that this bug was fixed in ZDoom. There is an excellent article written by Colin Phipps which you can find here on doom2.net.

BLOCKMAP Structure

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

Header

bytes:
2: x-coordinate of grid origin
2: y-coordinate of grid origin
2: number of columns
2: number of rows

Offsets

bytes:
2: offset to block 0
2: offset to block 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. These offsets are also unsigned, meaning they can go up to 65536 instead of 32767 (like most other WAD structures).

Note: These offsets in the Doom Source code used shorts for iterating through the list rather than bytes. Therefore the actual offset if you are reading byte by byte is 2 * offset.

Blocklists

bytes:
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.