The exact logic of linedef skip and how to deal with it

[Jacek Nowak (jacnowak)]

Hi!

 

I think that's the name for a phenomenon that a walkover linedef just doesn't trigger if you happen to run over it fast enough.
I find it frustrating as sometimes it just plain breaks the level.
I *think* it does not happen in GZDoom as I never encountered it in this port.

But I can't tell exactly at what point it's more or less likely to occur.

 

Here are my findings:
- it happens extremely frequently in Crispy Doom: if I place 10 walkover lines next to each other, practically each time I straferun over them one or two isn't triggered; I thought that it's lines being close to each other that makes it more likely but it doesn't seem to be the case, even if they are 40 units apart (so the whole section is 400 units with 10 walkover triggers in it) the behaviour is still the same
- it happens much less frequently in prBoom+ (complevel 9): actually I *thought* it doesn't happen there at all: I have a voodoo doll that travels at insane speed on a conveyor belt and I haven't yet encountered a situation in my testing that it doesn't trigger what it's supposed to trigger
- but it still DOES happen in prBoom+ sometimes, I have a section in my map where there are 3 walkover lines and it looks that almost 50% of times one of them isn't triggering (it seems to always be the same one!), one thing being special about them is that you jump to that area from above - there are 3 linedefs and 50% of the times they all trigger but 50% of the times the one in the middle does not trigger - and it happens even if I just run normally, not straferun: so it happens very frequently for that particular line but not for other lines, which is weird, especially as it's the middle one and both the one before and after seem to trigger consistently

 

Is there knowledge somewhere regarding in what situations linedef skip is most likely to occur (location at specific coordinates or something?) and how to protect your map against it? It seems to be a really frequent thing and it must be frustrating to mappers if there is no easy cure but I couldn't find much information online about it.

[zokum]

There is an upper limit on how many linedefs you can trigger per gametic. That limit is 8. Having 10 linedefs that can trigger at the same tic can easily go over that limit. Your stuff needs to be spaced out better, and in multiplayer 4 players CAN trigger lines at the same tic...

There is a small chance of not triggering a linedef when moving fast. With a ton of linedefs spaced out like that, you'll statistically hit a new frame where you moved to far for the engine to consider you having crossed a linedef.

If possible, you can duplicate the lines and put them say 16 pixels apart or something. At some distances it's impossible not to trigger one of the lines. If this messes with your logic, that's unfortunate.

I have had to construct maps with extra linedefs to get around this limit. Important teleporters in dm maps could also benefint from a backup line like 8 pixels behind the actual teleport line to ensure the player always teleport.

[Jacek Nowak (jacnowak)]

Thanks @zokum for your reply. I think what I'm seeing is not related to limit of 8 linedefs triggered per gametic.

I made a simple test map that has 8 walkover linedefs. I attach that map.

In Crispy this fails pretty much consistently if I straferun - it's rare to have a run from one side to the other where all 8 sectors are lowered. Most often at least one is not lowered, sometimes as many as 3 out of 8!

In prBoom+ I wasn't able to break this this test map despite trying at least 20 times - every time all sectors were lowered. This led me to think that linedef skip bug has been fixed in Boom/prBoom+ but it doesn't seem to be the case as I just discovered it in my map (real map I'm working on) and it happens surprisingly often in one particular spot. There are only 3 linedefs in a row where it fails so it's definitely not because of the limit of 8 lines (and it's singleplayer so even if a monster triggers something somewhere on the same tic it's still well below the limit), it might have something to do with triggering the lines mid-air but I'm not sure. Changing the angle of the line seems to help but it's all a bit nondeterministic so I'm not sure it definitely helped...  I think I will just duplicate all walkover linedefs in my map just to be sure...

 

So the question is - why in prBoom+ linedef skip occurs much less often then in Crispy?

What ports have fixed is completely? Is GZDoom definitely free of it?

Or does the bug definitely happen in prBoom+ complevel 9? If not, maybe there is something else going on in my map that I can't see.

 

testw.zip

[zokum]

Reread the post. I explained why it happens. When moving at high speed there is a certain chance you moved so far that the engine does not realize you crossed a line. This happens if you are just in front of a line then well beyond it. Using strafe runs to skip linedefs in order to speedrun or reach areas normally out of bounds is a well known speed running tactic.

Point is, there are several ways you can fail to trigger a linedef. The teleport linedefs are also one-sided, and can only be triggered when moving towards the 1st side of a linedef.

Fixing the algorithm to catch these skips isn't all that difficult, but it will ruin demo compatibility and change how certain maps are played.

[Jayextee]

If I remember correctly, this is more-likely with cardinal directions (straight N/E/S/W) than it is with angled/diagonal lines; makes sense due to entity collisions being essentially boxes, I guess.

[BoxY]

I played with your demonstration file a bit, and indeed in PrBoom+ all linedefs activate consistently if I straferun west across them, and in Crispy I was getting usually 2 or 3 linedefs pretty consistently failing to activate. It seems to be a variety of different linedefs that fail with some more susceptible than others, but I don't exactly feel like running across 500 times and plotting a graph of failure rates for each one. Regardless of what happened when strafing west, the rest would always activate when I strafed east back to the other side. Only once did I get all 8 to activate in one westward pass.

 

 

Flipping the player spawn to the other side and strafing east first would trigger the linedefs 100% reliably on Crispy. It doesn't seem to have anything to do with the front and back orientation of the linedefs, I flipped them around into different configurations and got the same behaviour. I also tried slanting all of the linedefs by 1 map pixel to see if that would just automagically fix everything without any luck.

 

Why Crispy and PRB+ would differ so stubbornly on this simple test completely baffles me since as far as I know the collision and movement behaviour of both ports should be indistinguishable. Certainly basic collision check misses like the infamous noclipping mancubus fireballs exist in both ports, and Doomguy's hitbox and movement physics haven't changed either.

 

Increasing the slant of the linedefs by like ten degrees reduced the failure rate, but I was still getting one usually failing to activate.

 

In general I'd say all you can do is not cram too many linedefs together between slender sectors, and give them a good slant to the expected angle of entry to improve the chance that some part of the target hitbox will intersect them during a check. Making a large V with two identical linedef actions seems to be consistent and reliable, certainly most monster teleport closets are built that way.

 

In conclusion, the west wind is unlucky and brings bad omens, so trying praying to the ancient dragon god of the east and burning some sacred incense before you open the editor.

 

[Jacek Nowak (jacnowak)]

Thanks a lot all for the input, I found what the issue was - and I apologize for a mistake I made in my first post. I actually did NOT specify complevel in prBoom+ when doing tests with the attached map.

 

So I redid the tests and here are my results:

- in both Crispy, PrBoom+ -complevel 2 and PrBoom+ -complevel 9 linedefs fail to trigger in the same way; this is just consistent linedef skip bug

- in prBoom+ if you do NOT specify complevel linedefs always trigger

 

So that means that vanilla has this bug as expected and BOOM did not fix it so PrBoom+ keeps this bug if complevel is specified as 9 (BOOM). PrBoom+ fixes this however if you don't specify complevel.

 

The confusion arose because I was testing my real map in prBoom+ without specifying complevel, then I changed my run script and now it has complevel 9. I knew that I tested this map many times and nothing ever failed, I added a new area that started to fail very often and I got baffled. It was just coincidence of specifying complevel. I can now get other triggers to fail on my map if I play with complevel 9.

 

So I think two lessons to learn here:

If you make a BOOM-compatible map better duplicate important triggers as in vanilla. I thought that I don't need to do it and I was wrong.

PrBoom+ is not the same thing as BOOM so don't specify complevel unless you really want to emulate something older (or you are testing your own maps).

Edited September 6, 2020 by jacnowak

[Aurelius]

If you're interest in the specifics of line skipping (or Doom movement and collision related shenanigans in general), check out this thread by Linguica that explains quite thoroughly why things like line skips happen.

 

And like it has already been mentioned, duplicating your activation lines is a pretty robust solution, and 16 map unit separation between the duplicates is usually enough (while also keeping in mind the 8 line action limit that, if exceeded, causes spechits overflow and some of the actions are ignored.) And if you're worried about your actions going haywire if you activate the same one multiple times (floors raising or lowering too much etc.), in Boom you can always create a voodoo closet and have the activation be a simple ceiling movement that releases the voodoo doll, making it completely resistant to being borked by multiple activations.

 

Also, you can design your map geometry to prevent players accumulating enough speed to execute line skips. For example, you can set the walkover line behind tight corners or add a forced "drop" by stopping the players forward momentum, making them bang their head against a ceiling that's too low and forcing them to fall down a teeny bit to get under it, effectively preventing them from accelerating enough to skip the line.

[Jacek Nowak (jacnowak)]

Out of curiosity I did the test in Eternity and Doom Retro - couldn't break it so it seems that they also fixed linedef skip bug, so it looks that if you map in BOOM format the only situation this can occur in a contemporary port is when you run in PrBoom+ AND you explicitly specify complevel 9.

 

Another finding I just found out - the 8 line action limit (spechits overflow) only applies to Vanilla - it has been fixed in BOOM and it only occurs in prBoom+ on complevel 2. It does not occur on complevel 9. So at least you don't need to worry about this one when mapping in BOOM format.

 

Thanks again everyone for all input, it was really valuable and helpful!

[plums]

Just to clarify a point: In PrBoom+ if you don't specify a complevel, it will use whatever compatibility option is specified in Options -> General -> 2nd page -> Default Compatibility Level. By default this is set to "Latest PrBoom+" which is equivalent to complevel -1.

 

With complevel -1, the options in Options -> Setup -> Doom Compatibility will affect behaviour of various things. (complevels 9 and lower don't use these options at all; complevels higher than 9 will use at least some of these options, depending on what you choose.) This particular bug was fixed in MBF, which is complevel 11. If you set "Use exactly Doom's movement clipping code" to Yes, you'll still encounter the bug with any complevel. (Most people typically leave these options alone though.)

 

As laid out in the thread by Linguica, and mentioned by other replies here, you are less likely to skip linedefs if you are moving North and/or East than South/West, as well as less likely to skip them if they're 45° rather than horizontal or vertical.

Edited September 7, 2020 by plums

[Maes]

14 hours ago, zokum said:

Reread the post. I explained why it happens. When moving at high speed there is a certain chance you moved so far that the engine does not realize you crossed a line.

This is a common problem whenever somebody first codes something that remotely looks like a video game/involves simulated collisions. A classic example is the quintessential "bouncing ball" program. At some point, if using the naive collision detection algorithm the programmer will discover that there's a certain speed and time step duration combination (which ultimately boils down to a minimum detectable movement change per time step) that "breaks" his little universe's crude laws of physics. That's actually not entirely dissimilar to the concept of the speed of light and Planck length/time in the real world, which cannot be broken otherwise weird things happen.

 

In computer land, you can usually fix this by using double-checking collision/crossing algos, at the cost of more computational complexity. Doom uses a combination of both the naive method and double- (or even triple-) checking in some special cases.

 

Edited September 7, 2020 by Maes