|Doom level format|
The REJECT table is a resource attached to levels which is used to speed up line-of-sight calculations. At the start of a level, monsters are in "sleeping" states, in which they stand in position. They can be activated by "seeing" the player or through sound (such as the player firing a weapon near them). Large levels may contain many monsters; the REJECT table makes it possible for Doom to determine when it is impossible for monsters to see players.
The table works by precalculating whether direct line of sight between sectors is possible. A reject map builder is used to generate the table, which may take a substantial amount of time to calculate. When completed, a table of boolean values is generated, one for each combination of possible pairs of sectors.
In order to determine whether a monster can see a player, the engine looks up the value in the reject table, using the number of the sector the player is in and the number of the sector the monster is in. If the value is found to be true, it is immediately known that there is no line of sight possible between the two sectors, and it is impossible for the monster to see the player. If the value is false, line of sight between the sectors may be possible: a more complicated calculation is performed to determine whether the player is visible to the monster.
The format of the reject table is very simple. The reject table can be represented as follows (considering a level with five sectors):
- (Horizontal axis: sector player is in; Vertical axis: sector monster is in)
The boolean values are then read left-to-right, top-to-bottom and packed into bytes (producing eight values per byte). In packing into bytes, the least significant bit is used first. So the value of the reject resource for the above table would be:
Binary: 11000101 00111110 00100110 00000001 Hexadecimal: 0xC5, 0x3E, 0x26, 0x01
It can be seen that the size of a reject lump in bytes can be calculated thus:
- $ reject size = ceiling(s^2/8) $
Where s is the number of sectors in the level.
Some levels have used the REJECT resource to provide special effects. The table can be used to control whether monsters can see players, so a carefully created table can be used to make the player "invisible" to monsters. It is possible to have monsters stand in place, for example, by placing a monster in a sector which has been "isolated" through setting all of its reject entries to true. Monsters will still activate when injured or when they hear a sound, however.
If the REJECT lump for a map is smaller than ceiling(s^2/8), then some of the line-of-sight lookups will be missing. Doom does no bounds checking on the lookup, so if the player and a monster are in sectors that are not in the table, whatever happens to be in memory after the end of the table will be used as a reject value. For demo compatibility, Chocolate Doom and PrBoom plus attempt to emulate this behavior on small overflows by predicting what would be in memory after the REJECT lump, but it is nearly impossible to do on larger overflows, and many demos on maps with very short reject tables would desync even in Vanilla Doom. Most source ports replace out of bounds REJECT lookups with 0, requiring an expensive line-of-sight check in every case of overflow.