too much A_CHASE

Wads like the nuts.wad series are known for taking a toll on your frame rate, even on powerful computers. I've read this is mostly because the codepointer A_CHASE is being called too many times at once, which causes the game to slow down.

NUTS3 for example has 12263 monsters. But Holy Hell MAP02 has about 5000 some and doesn't really chug down at all. Obviously not all monsters are awake at once, but I guess the question is how can you tell how many monsters are active on the map at once? What range of monsters can you have awake and chasing the player before the game starts to slow down?

I had an idea for a map where all monsters would be summoned into the map by teleport ambush, but if I intend to have a lot of monsters in the map, they'll have to be awoken incrementally, and I was wondering what a safe number of monsters to awake at once might be.

40oz said:

Wads like the nuts.wad series are known for taking a toll on your frame rate, even on powerful computers.

depends on port, I guess (and in prb+'s case, on complevel as well, iirc). On a mediocre laptop glb+ runs perfectly smooth for me on nuts and the like. Though I guess fancy ports with gl-lighting and whatnot might struggle.

I had an idea for a map where all monsters would be summoned into the map by teleport ambush, but if I intend to have a lot of monsters in the map, they'll have to be awoken incrementally, and I was wondering what a safe number of monsters to awake at once might be.

holy hell map05 is a decent example of having monsters wake up incrementally through the map (even if the design of the closets themselves is questionable). I'd say monster count induced lag is most common and problematic in MP play (zandro notably, in my experience), but you'll probably be fine if you could manage to keep less than a couple thousand mobs active at a time.

Some people will argue the point, for some reason, but, if you build a proper REJECT lump, most of your A_CHASE issue goes away. Line of sight checks are expensive. When the REJECT lump is left blank, Doom must perform each and every line of sight check the hard way. But, with a proper REJECT lump, many of those checks are immediately "REJECTed".

Now, with a map like NUTS, with one big sector with 10,000 monsters, REJECT won't help much. But, what's cool about using REJECT is that #1: It *never* slows the map down, and #2: It almost always speeds it up. There's really no reason not to use it in the final release, but, more and more, I see new maps using blank REJECT lumps. Some ports even allow the REJECT lump to be missing.

Part of the problem is:
#1 - New map compilers don't build the REJECT lump, at least not by default.

#2 - Most REJECT builders are command-line DOS programs which confuses some people.

#3 - REJECT lumps are large (Num_sectors ^ 2 + 7) / 8, so, with ports that support missing REJECT lumps, the WAD file can be smaller.

#4 - Building a proper REJECT lump takes a lot of computing power and time, which should suggest why it makes sense to do that work in a REJECT builder, vs. at game time :)

kb1 said:

Part of the problem is:
#1 - New map compilers don't build the REJECT lump, at least not by default.

#2 - Most REJECT builders are command-line DOS programs which confuses some people.

#4 - Building a proper REJECT lump takes a lot of computing power and time, which should suggest why it makes sense to do that work in a REJECT builder, vs. at game time :)

Could you clarify these points with some examples from some node builders? Legitimately curious here. I've been using Zen Node for all of my vanilla related work, and I'm fairly certain I'm using some compression option than only Zen Node supports. I've never seen node generation take any longer than a few seconds, and if the the reject lump isn't being built, I'd sure like to know. Bare in mind, I'm doing all of my work on a quad core I7.

At the risk of answering my own question, I am not aware that vanilla fully supports an empty reject lump -- an empty reject lump results in most monsters becoming blind, as I've come across a few supposedly vanilla compatible maps that either had an empty reject lump or not one at all!

BlueFeena said:

I've never seen node generation take any longer than a few seconds,

It shows that you've never been making a truly big map. Building nodes in D2INO MAP19 takes 20 seconds on my computer. ;)

BlueFeena said:

and if the the reject lump isn't being built, I'd sure like to know.

1. You can easily check your wad in SLADE3.
2. When you select a NodeBuilder in a map editor, sometimes you can see variations of each one, like "Zennode" and "Zennode (no reject)". The one that doesn't say "(no reject)" should build REJECT.

BlueFeena said:

At the risk of answering my own question, I am not aware that vanilla fully supports an empty reject lump -- an empty reject lump results in most monsters becoming blind, as I've come across a few supposedly vanilla compatible maps that either had an empty reject lump or not one at all!

I'm not the best person to ask about the most modern specific tools. I use a custom REJECT builder I wrote, which is not yet suitable for release. But, I can try to clarify a couple of points:

Proper REJECT lump - A proper REJECT lump is of the size (num_sectors^2 + 7) \ 8 bytes. This allows one bit, either 0 or 1, for each sector, for each sector. When Doom checks line-of-sight (LOS) it first consults this bit array, asking the question: Can this monster in Sector 12 see the player in Sector 22? A "1" tells Doom "No, LOS is obstructed", and this is where optimization occurs. Otherwise, a "0" tells Doom "maybe LOS is possible", and Doom has to perform a real LOS test, which takes a lot more time.

Blank REJECT lump - A blank REJECT lump contains all zeros, causing Doom to have to perform full LOS checks each time. This is what you get by default, if you do not specify that you want a proper REJECT lump, or your node builder does not have the capability to build one.

REJECT lump too small - I've seen a few 1994 maps with REJECT lumps that are too small. My guess is that the lump was copied over from a smaller map by mistake. Anyway, in vanilla, this can cause Doom to act strangely, as it tries to read REJECT info from some invalid place in memory. Monsters may act blind in one play, and can see fine at other times. This can cause Doom to create demos that cannot be reliably played back, even on the same machine. In newer ports, this can cause a crash. Some ports detect this condition, and automatically generate a blank REJECT lump in memory. In any case, releasing a map with a small REJECT lump is always a mistake.

Missing/empty REJECT lump - Very similar to the above description, this can make vanilla Doom act strangely, make blind monsters, and generate unreliable demos. If undetected, this will crash ports. Unless your port of choice explicitly handles missing/empty REJECT lumps, and you don't care to support the ports that don't, you're better off supplying at least a blank REJECT lump.

Trick/custom REJECT lumps - It is possible to engineer a REJECT lump that creates blind sector-to-sector checks that would otherwise be visible. For example, you can make dark sectors invisible to monsters by placing 1's into the proper areas of the REJECT lump. An old DOS program, RMB, specialized in this area. But you have to be careful that your node builder doesn't overwrite your carefully-built REJECT lump!


I do remember ZenNode creating REJECT lumps. I do not know about the newer node builders. This is an issue, especially on limit-removing maps that require the newer tools that do SIDEDEF compression, BLOCKMAP doubling, and newer node formats. It is these huge maps that would benefit most from a proper REJECT lump, but I do not know if those node builders bother with building the REJECT lump. I think, last time I checked, ZDoom's node builder did not generate a REJECT lump.

As far as I know, all ports still read the REJECT lump, so it's a shame to supply a blank lump and receive no benefit from it. I've heard arguments that state that it doesn't really save a lot of time. My counter argument is that ANY time saved is a good thing, especially in multi-player games, > 35 FPS interpolated rendering, 2,000+ monster maps, 32-bit color hires rendering. Unless you NEVER experience lag, and your frame rate never drops lower than you like, any speed-up is good. And, in fact, a proper REJECT lump can make a noticeable difference, especially with a lot of monsters.

Thanks for a good explanatory post, kb.

Two older informative threads on the subject:

Sunder.wad, map11 - FPS
Reject map building - How is it done?

kb1 said:

Missing/empty REJECT lump[/B] - Very similar to the above description, this can make vanilla Doom act strangely, make blind monsters, and generate unreliable demos. If undetected, this will crash ports. Unless your port of choice explicitly handles missing/empty REJECT lumps, and you don't care to support the ports that don't, you're better off supplying at least a blank REJECT lump.

For ZDoom (and presumably any other port that supports these), not having a REJECT table means the check will be skipped. So the difference between this and and an all zero table is memory consumption.

Edit: Just noticed that there's code to discard an all 0 reject table, so nevermind I guess.