Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
purist

Self referencing sector question

Recommended Posts

I have a catwalk in my map that is made of a self referencing sector. When the player is on it monsters do not acknowledge him. Same applies even if the monster has already been awoken. Is there a way to prevent this happening or is it an unavoidable side effect of self referencing sectors?

Share this post


Link to post

I cannot answer your question directly but can offer a workaround.

Boom can simulate crystal sectors with linedef special 242 Create Fake Ceiling and Floor. There's no need for self-reference magic and you avoid being invisible to the monsters in other sectors.

For an example see sector 407 and linedef 4814 in CC4 MAP21. There are many more examples in that map.

Share this post


Link to post

Why purist says that monsters can't see you inside self-referencing sectors? Load Plutonia Map03, go to the invisible bridge and observe monsters attacking you while you're standing on it... Bad nodebuilder?

Share this post


Link to post

Good catch. Rebuilding the nodes with Zennode makes the monsters in other sectors ignore you. Rebuilding them with BSP32 doesn't.

Share this post


Link to post

I've had that problem with zennode before too. I was doing weird lighting tricks and the monsters could only see and hear me if I was in the sector with them.

Share this post


Link to post

Nodebuilders. I never suspect the Nodebuilders. I recently switched to a custom one used in BTSX, I wonder if they hit the same snag? I'll run it through another tonight to see if that works. I did think it must have worked right in Plutonia and other WADs but couldn't tell why.

EDIT: And it worked. Thanks guys!

Share this post


Link to post

Sounds like maybe the REJECT map. I think some of them mark self-ref sectors as being invisible.

Share this post


Link to post
Never_Again said:

Plutonia MAP03 has an all-zero REJECT.

True. In fact all Plutonia maps have zeroed REJECT lumps. TNT, however has strongly-populated REJECT lumps. Probably used a different node builder.

I was actually referring to OP's map. Since a node build fixed the problem, the problem may have in fact been caused by the REJECT lump. I could be wrong, but I seem to remember that ZenNode's REJECT builder did something unusual with self-reference sectors, when the default options were used.

Share this post


Link to post
kb1 said:

I could be wrong, but I seem to remember that ZenNode's REJECT builder did something unusual with self-reference sectors, when the default options were used.

It's more likely the other way around. I don't know about ZenNode, but I do know that a lot of older reject builders used linedef references to speed up the process: for any two given sectors, it creates a chain of two-sided linedefs that connect one sector to the other, then checks only lines of sight along that chain. Linedefs with both sides in the same sector will never form part of such a chain, and sectors composed entirely of such linedefs will be deemed to be never visible from any other sector.

This may have been an acceptable solution back when computers were slower and reject building took forever, but not so much these days (especially since self-referencing sectors are a well-known trick and it is trivial to detect whether a given map contains any and thus requires special treatment).

Share this post


Link to post

You are both right, inasmuch as you are not arguing about the same thing.

The problem is indeed nodebuilder-related, but the NODES lump has nothing to do with it. An all-zero REJECT transplanted into a copy of Plutonia MAP03 treated with Zennode makes the monsters attack you when you are on the crystal bridge. Ditto for a WAD treated with glBSP.

Zdbsp seems to produce only an all-zero REJECT or a zero-length marker with that name.

Of all nodebuilders I tried only the ancient WARM produced a self-reference-friendly (kind of) REJECT; it made the top of the bridge non-transparent, though, by "borrowing" the brown water flat from the adjacent sectors.

Next up was RMB. It, too, turned the monsters outside the bridge sectors into pacifists until I used the INCLUDE option in a .rej file. Of course, I had to provide all the sector numbers myself.

Conclusion: nodebuilders' inability to give self-referencing sectors a preferred treatment is the root of the problem. REJECT tables that stop monsters outside self-referencing sectors from attacking you when you are inside of those sectors are merely a symptom.

Share this post


Link to post

REJECT tables are still one of the big mysteries of Doom -there are relatively few tools that can build them, and one of the best dedicated ones (RMB) had its source code lost -written in Pascal, no less.

In addition, there's not -yet- an uniquely defined way of building them, or at least building them "perfectly". Some even feel that they are a relic -and some source ports don't depend on them for performance enhancement or visibility checks at all.

Share this post


Link to post

Is that really surprising?
They *ARE* a relic of a time long gone and bring little to no effect on modern hardware.

Computers have become so fast that you need several hundreds of active monsters to see a marginal effect - and then you maybe save 2-5% of the playsim's execution time - but depending on the map's complexity that's only a handful of percents. You save little to nothing of little to nothing. And that's a conclusion I already made more than 10 years ago with some of the largest maps of their time.

What REJECT does, though, is hog a lot of memory and create some significant cache thrashing if the map gets large enough.

And if you use the 1.2 blockmap based sight code it's even less relevant because that code doesn't even try to do expensive BSP traversals across the entire map to perform one sight check - it merely fires a trace from the origin to the target and will stop at the first obstruction it finds.

To sum it up: Back in the 90's there were legitimate reasons for this kind of speedup - but for the last 10+ years there was just no need and therefore no motivation to invest work here.

The cost to benefit ratio of REJECT is extremely bad, they take a long time to create, require a lot of memory to work and provide little in return for such a waste of resources.

Share this post


Link to post
Graf Zahl said:

Is that really surprising?
They *ARE* a relic of a time long gone and bring little to no effect on modern hardware.

Computers have become so fast that you need several hundreds of active monsters to see a marginal effect - and then you maybe save 2-5% of the playsim's execution time - but depending on the map's complexity that's only a handful of percents. You save little to nothing of little to nothing. And that's a conclusion I already made more than 10 years ago with some of the largest maps of their time.

What REJECT does, though, is hog a lot of memory and create some significant cache thrashing if the map gets large enough.

And if you use the 1.2 blockmap based sight code it's even less relevant because that code doesn't even try to do expensive BSP traversals across the entire map to perform one sight check - it merely fires a trace from the origin to the target and will stop at the first obstruction it finds.

To sum it up: Back in the 90's there were legitimate reasons for this kind of speedup - but for the last 10+ years there was just no need and therefore no motivation to invest work here.

The cost to benefit ratio of REJECT is extremely bad, they take a long time to create, require a lot of memory to work and provide little in return for such a waste of resources.

Graf, you've said something similar to the above many times on this and other forums, despite evidence to the contrary. Your "2% to 5%" is misleading. Here's why:
1. All ports must check REJECT, or they break the effect of some maps. So it's a given fact that whatever memory they require is consistent across all ports.
2. In a peer-to-peer multi-user game (like Doom's original net code), all clients must maintain 35 fps for any of them are expected to maintain 35 fps.
3. So, if the slowest computer encounters the extra 2-5% delay, and that causes it to fail to complete it's tic on time, all clients suffer 100% loss.

You cannot isolate one time-consuming function and place a "2 to 5%" number upon it, and call it a day. Any delay that can be avoided is a plus, and can make the difference between a fluid game, and a lagged mess.

I understand your point, and, yes, it's even a better point if you use the 1.2 algorithm. But, you cannot argue that a fully-built REJECT does save some time, so why fight about it?

One day I will release my tools which include a functional "perfect" REJECT builder (written in VB6, no less). It's pretty fast, but it does a #-of-lines-cubed-times-#-of-samples formula, so, on big maps, it does take some time. (yikes)

It walks down each linedef, and calculates a visibility triangle. Point C is a point on the source linedef, and points A and B are the endpoints of another linedef. Then it does intersection checks for something obstructing the triangle. If a triangle can be drawn from the sample point on the source linedef to the endpoints of the second line without obstruction, visibility is possible.

My biggest obstacle is time - I have a couple hundred years of projects to complete, so prioritization is kinda important.

Share this post


Link to post
kb1 said:

I understand your point, and, yes, it's even a better point if you use the 1.2 algorithm. But, you cannot argue that a fully-built REJECT does save some time, so why fight about it?



Because unless you intentionally make a map that disporportionally benefits from fully built REJECT the time spent here is utterly irrelevant unless you use a computer more than 15 years old.

The thing is, in order for REJECT to save time, there must be some measurable time to be saved first. I had to start nuts.wad with ZDoom just to get sight checking per tic above 0.1ms on my system - that't be 1ms if you factor in an older machine and the less efficient sight checking code from Doom 1.9. And that's with 6000 monsters! Go down from there to realistic amounts and we are entering nanoseconds territory on anything even closely resembling a usable computer these days.

Now, that time I mentioned would be the ENTIRE time soent sight checking, so even in the best case scenario REJECT wouldn't save you more than maybe 30% of it, most likely even far less, because most active monsters tend to be near their target where REJECT won't help.

I don't think we need to go further from there, if even in the most extreme cases the time that can theoretically be saved is next to nothing and you may have a success ratio that's maybe 1/3. That's 1/3 of next to nothing.

Before making outrageous claims about REJECT's usefulness you first have to make sure that the problem this addresses is actually worth addressing, and that's clearly not the case anymore. You just can't save processing time that's not even used.

On old 90's CPUs things were different, of course, but these times are long gone.

Share this post


Link to post
kb1 said:

It walks down each linedef, and calculates a visibility triangle. Point C is a point on the source linedef, and points A and B are the endpoints of another linedef. Then it does intersection checks for something obstructing the triangle. If a triangle can be drawn from the sample point on the source linedef to the endpoints of the second line without obstruction, visibility is possible.

Any algorithm that samples points along a line (or inside a sector or subsector) can never be "perfect" as visibility may be possible from one of the unsampled points.

A better approach is a portal-flow technique which Quake mapping tools use, also used within the Doom3 renderer. I think the Vavoom "glvis" program works the same way.

Doing it properly will be faster too. Though I agree with Graf that building good REJECT tables would be a waste of time these days.

Share this post


Link to post

Some possible optimizations I had thought for REJECT maps:

  • Trading space for speed. Their single-bit representation may be memory efficient, but it trades speed for space due to the required bit shifting and masking in order to get a value out of it. Using something closer to the CPU's native access patterns, e.g. arrays of booleans/bytes/ints may waste some more memory, but access will be faster.
  • Cache pollution? Well sure, it's not a small structure (it's O(n^2) to the number of sectors n in a map), but it's only used during the playfield calculations, so it doesn't interfere with the biggest cache trashers in the game: the textures and the screen buffer, with their inefficient vertical rendering.
  • Using a sparse representation in memory, such as a linked list or a packed array for each sector, maintaining a list of visible sectors for each sector. It might be tricky to still get O(1) or O(c) access time, though. However, an analysis of the IWADs' REJECT table density I once performed resulted in most of them being above 70% dense, so probably the benefits from a spare representation would not be significant.
  • Building them dynamically: visibility checks performed from the monsters themselves with LOS checks are used to build a REJECT table during gameplay, essentially working as a cache for LOS calculations. Of course, this way demo compatibility and REJECT table trickery are lost.

Share this post


Link to post
andrewj said:

Any algorithm that samples points along a line (or inside a sector or subsector) can never be "perfect" as visibility may be possible from one of the unsampled points.

A better approach is a portal-flow technique which Quake mapping tools use, also used within the Doom3 renderer. I think the Vavoom "glvis" program works the same way.

Doing it properly will be faster too. Though I agree with Graf that building good REJECT tables would be a waste of time these days.

That's why "perfect" is in quotes. Of course, depending on the sample size, you may be talking about a gap that's thin enough that a monster would not be realistically looking through it anyway.

You guy must have kick-ass machines - I notice a difference, using a modified 1.2 algo, on a 6-core hyperthreading 3.20 GHz box... But, again, I play big maps in peer-to-peer coop. Believe me, I will not complain while I enjoy faster gameplay:) The lag will be most-noticable at the beginning of the map, when all the sight-checking is dominant. Once the whole level is moving, it's either not as much of a concern (though still present), or everything else is distracting, causing other delays.

I must admit, I have no understanding of the "wasting your time" comment, since it is once, and you obviously have fast machines, and the savings, no matter how small, are realized forever, from that point forward.

My question to anyone is: "Does every map you've ever wanted to play, play at the frame rate you want it to?" If that answer is ever "no", then why downplay any optimization THAT'S REQUIRED to be checked??? What am I missing here?

Share this post


Link to post

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  
×