Speed Up Your Level:
Optimizing the REJECT Resource and Other Tricks
Written by Dr Sleep

Few level designers take advantage of the REJECT table in their levels, and many of them probably don't even know that it exists. But the fact is that you can speed up your level by nearly 80% by optimizing the REJECT resource - especially in large levels with many monsters. And all it involves is the use of any one of several utilities designed specifically for that purpose. We'll talk about a couple of them - Reject Map Builder (RMB) by Jens Hykkelbjerg, and ZenNode by Marc Rousseau - in a moment; but let's start with just what the REJECT map is and what it does.

What is the REJECT Resource?

The REJECT map within a WAD file is an array, indexed by Sector, which tells the DOOM engine whether it's possible for a monster in a particular Sector to see the player in another Sector. The information is stored as a series of bits for each Sector pair, either a 0 or 1.

• 1 means that there is no direct line-of-sight between the two Sectors.

• 0 indicates that the Sectors may be visible to each other.

For every pair with a 0 bit, the DOOM engine must perform a line-of-sight (LOS) calculation at game time for every possible Sector pair in the level. Considering the number of Sectors and monsters in an average level (e.g., there are 186 Sectors in MAP04 of DOOM II), the LOS calculations are non-trivial and can have a noticeable effect on game speed and frame rate updates. Therefore, the more Sectors that are represented by 1s in the REJECT map, the less LOS calculations performed during game play.

Aside from some very cool special effects that are possible (talked about in the next section), you should note that an optimized REJECT table has no actual effect on monster decision-making. A monster in Sector 299 on the other side of a level is not going to see the player in Sector 0 no matter what. Setting a Sector pair bit to 1 for Sectors that are not in line of sight of each other will not increase or decrease the likelihood that a monster will see and attack the player. It merely reduces the LOS calculations that DOOM has to make. But this reduction can represent a huge gain in level speed. Enemy attacks will still be determined by the ambush bits, sound-blocking, and Thing-placement strategy you employ. 

Figure 1.0:  Small map with a Player in Sector 0 and an Imp in Sector 3.

The REJECT resource can be thought of as a pair table. A proper REJECT table based on the map in Figure 1.0 would look like this:
 

Player Sector

Monster Sector		0	1	2	3
	0	0	0	0	1
	1	0	0	0	0
	2	0	0	0	0
	3	1	0	0	0

      Figure 1.1:  Player Sector 0 cannot be seen from monster Sector 3, thus MS pair 0-3=1 and PS pair 3-0=1.

In Figure 1.1, the engine can immediately ignore the Sector pairs 3-0 and 0-3 because the bit set at 1 says those Sectors can't see each other. This is the sort of REJECT table you would want to generate in your level.

Common sense tells you that the Imp cannot see the Player. There is no direct line-of-sight between Sector 0 and Sector 3. Yet an empty REJECT map (see Figure 1.2) forces the DOOM engine to resolve the LOS between these two Sectors regardless.
 

Player Sector

Monster Sector		0	1	2	3
	0	0	0	0	0
	1	0	0	0	0
	2	0	0	0	0
	3	0	0	0	0

Figure 1.2:  An empty REJECT map is composed of all 0s.

Obviously, if your level is as small as the example given, the difference is negligible. But just imagine the hit your level is taking if it is even only average size - say, 150 Sectors. DOOM has to constantly update LOS, and needlessly. Having an optimized REJECT map makes an incredible difference that is usually apparent the first time you run the new map.