The Doom Movement Bible

gemini09 said:

Regarding "Line skipping", I see it as a really bothersome problem and hope that source-ports have a remedy for it.

There is a pretty good home remedy. Just stack two triggers close to each other. That will massively decrease the change of the trigger not working. Also diagonal lines seem to be more reliable.

So, as I already questioned here, would a row of 5 walkover-activated special linedefs behind each other, with a gap of 15 map units between them, perfectly guarantee that at least one of them would always be triggered if the player crossed them (in any number of tics) and had perfect timing for linedef skipping? If so, is 5 the lowest number of linedefs that would guarantee this perfectly, or what is the actual lowest number?

Uh... outside of teleporting, obviously, the furthest you can theoretically move in a single movement step (aka a single P_TryMove check) depends on the angle of the wall you are sliding against. If it's an axis-aligned wall you will be limited to 30 units. If it's an angled wall, then at a 27-degree wall (actually tan^-1 0.5 or 26.57), it seems like it might be theoretically possible to move up to... 30 / cos(26.57) * (1.118)^4 =~ 52.4 units in one move maybe? (About 46.9 x / 23.4 y or vice versa.) But that would be astoundingly precise and probably impossible to do in practice due to other rounding / precision errors.

If moving 60 units into any orthogonal direction in a single P_TryMove is impossible, then 4 walkover lines behind each other should always suffice to make an unskippable formation.

EDIT: If the maximum per-axis movement was actually 46.9, it would mean that 3 lines should suffice, with gaps greater than 15 but lesser than 16 units between the lines (coule be achieved by making the lines slightly angled), or greater gaps if the lines were non-orthogonal.

I imagine so. If you can move 16 units on an axis, then 1 line is insufficient. If you can move 32 units, then 2 lines is insufficient. If you can move 48, then 3 is insufficient. So if the axis-aligned distance is less than 48, as seems likely, then 3 is enough.

Linguica said:

If you can move 16 units on an axis, then 1 line is insufficient. If you can move 32 units, then 2 lines is insufficient. If you can move 48, then 3 is insufficient.

Exactly my train of thought. Here is another quick guess: If the linedefs were perfectly diagonal (which guarantees the highest player "radius" for collision with them), the minimum required momentum to skip a single linedef would be 22.63 on both axes, or a significantly greater momentum on one axis to account for just a slightly smaller momentum on the other axis. Similarly, the minimum required momentum to skip 2 diagonal linedefs would be 45.26 on both axes, or (again) a significantly greater momentum on one axis to account for just a slightly smaller momentum on the other axis. Considering the maximum momentum is only slightly greater than 45.26 on one axis, but significantly smaller than 45.26 on the other axis, this makes me think that 2 diagonal lines would actually suffice for an unskippable formation, with a gap of 22.62 units between them. But then again, it's just a quick guess.

I was playing Level 17: Tenements a week ago on Doom Touch (using GlBoom) and at one point, I died and my dead body slid through the shrinking gap created by a retracting lift. I can only assume the lift must have pushed my body up through the ceiling and allowed it to enter the void, because my body slid all the way through and passed straight through the opposite wall before I could even comprehend what had happened.

Wat

It certainly didn't clip "through a ceiling", because things in Doom engine can't ever get above the ceiling or below the floor. However, it's possible that the player's dead body got squashed between the ascending lift's floor and the side chamber's ceiling, which turned it into gibs and set its thing width and height to zero. If the body still had a momentum at that time, it could easily pass through walls with any speed, for reasons explained in Linguica's "SKIP GLIDE" post, combined with the fact that a thing with zero radius could never physically overlap any linedef and therefore never detect a collision with any linedef.

Wait, so the pile of bones that actors turn into after being crushed doesn't interact with Impassable Linedefs at all? I suppose they're never really meant to be moving.

Amazing work.

I hope this is of interest in some way, this is purely my own discovery, from as far as I can tell.

On E4M1, you have to get the red key



Right here, by this gated area.



Align yourself to the corner of the wall and the status bar as per the the highlighted areas. Once done, run diagonally forwards/right.



You will pick up the red key 95% of the time without problem.

Joe667 said:

Level 17: Tenements

Does PrBoom "crush" corpses on the edge of a lift? Looks like it does. In that case, yes, you managed to get a very rare series of events:

* Die on edge of height-difference sectors
* Slide along edge of sector due to special corpse-sliding code (maybe)
* Get crushed by the edge of a lift into a 0 width, 0 height puddle of gibs
* Continue sliding right through a wall because you now have no dimensions

deadwolves said:

I hope this is of interest in some way, this is purely my own discovery, from as far as I can tell.

Seriously? https://www.doomworld.com/vb/post/1587751

Joe667 said:

Wait, so the pile of bones that actors turn into after being crushed doesn't interact with Impassable Linedefs at all? I suppose they're never really meant to be moving.

They still interact with solid things and with sector heights - for example, when moving towards a ledge that is more than 24 units higher than their current Z position, the moving gib's position would be blocked - and only if this happens, the gib may possibly interact with linedefs by trying to slide along them etc.

Every part of space in the void shares the floor and ceiling height of one of its neighboring sectors. Which particular sector it is depends on the map's nodes. But it's common that the void behind a 1-sided linedef on the map's outer edge shares the floor and ceiling heights of the sector in front of this 1-sided linedef - so that if a thing can pass through walls, it usually wouldn't get blocked by an increased floor height on the outer edge of the map (simply because there usually isn't one), and will actually pass through the wall.

Noclip flag/cheat would make the thing ignore things and sector heights as well - but pools of gibs don't have a noclip flag, they just have zero dimensions.

so bouncing of a right wall in the beginning of map01 related to the last bug?

Linguica said:

But doing this quickly still requires some multiplication and division, and here’s where another aspect of the Doom engine comes in. Everything in the Doom engine is stored as 32-bit integer values - and, more specifically here, as fixed-point values, where one bit is a sign value, 15 bits are used for the actual integer portion and 16 bits for the fractional portion. 15 bits is not a ton; it’s only enough to store up to 65535 before it overflows. So when you are multiplying two arbitrary numbers together, you have to be careful that they don’t multiply to a value larger than 65535.

It's signed so the integral values can be between -32768 and +32767, instead of 0 and 65535.

Thanks Linguica for this detailed account. I had heard of many 'buggy' effects but haven't seen them described as well as this before.
Would anyone like to comment on how our knowledge of these effects should affect level design, if at all?
My own view is that wall-running and strafe-running are the most doable effects and I do my best to prevent any possible trivialisation of my levels by players running far too fast. It's probably always possible for such effects to speed up running to the exit, I just don't want anyone strafe-running across an 'impossible' jump to reach an 'unreachable' location. Any thoughts?

Linguica, amazing explanations, thank you!

MathsDevil said:

I just don't want anyone strafe-running across an 'impossible' jump to reach an 'unreachable' location. Any thoughts?

I can relate. I assume people play any wads in ZDoom and as such assume they also have the capability of jumping, so when I make gaps, I make them longer, when I make ledges, I make them higher or impassible or both (Rocket Jumps on source ports with mouselook!).

MathsDevil said:

Any thoughts?

IIRC for two equal-height floors, the player has to be able to land on the other side on the 7th midair tic in order to make it. Let me calculate it out for SR50 for a axis-aligned jump:

tic 0: center of player is 16 units off edge (i.e. barely touching the beginning ledge), z-height 0
tic 1: 39.57 units off edge, z-height 0 (z-height is not updated until after the XY movement calculation)
tic 2: 63.14 units off edge, z-height -2 (gravity applied is -2 if your z-momentum is 0)
tic 3: 86.71 units off edge, z-height -5 (-2 - 3)
tic 4: 110.28 units off edge, z-height -9 (-5 - 4)
tic 5: 133.85 units off edge, z-height -14 (-9 - 5)
tic 6: 157.42 units off edge, z-height -20 (-14 - 6)
tic 7: 180.99 units off edge, we MUST land here because otherwise our z-position is updated to -27 and the player can only climb up 24 units. So we need our front edge, which is 16 units ahead of us, to hit the other side of the gap: this is 180.99 + 16 = 196.99 units total.

So yeah, a 197-unit gap ought to be sufficient to prevent a SR50 strafe run on an axis. If the strafe run is at a 45 degree angle, then the corner of the player sticks further out, so the distance has to be 196.99 - 32 + 45.25 = 210.24 units.

That distance would be twice up to three times greater if wallrunning was involved instead of SR50, right?

How difficult would it be to have smooth cylindrical collision instead of clunky box based? Sorta like Marathon's.

This is awesome :D Thanks for putting this together

One thing I was unable to write up was an explanation of wallrunning on slanted walls. It's incredibly finicky and basically acts like a nonlinear system, since the amount you slide along the wall depends on your distance from it, your speed, and your movement angle, and all three are highly dependent on the previous movement calculation (not to mention your own angle and input). Not to mention that the code to redirect your TAP along the wall uses the granular sin/cos tables which introduces a little bit of drift either towards or away from the wall which in certain circumstances can mean the difference between success and failure. AND not to mention that if you do succeed at getting a good wallrun and hit the speed cap, that actually significantly changes your direction too. I was at the point where I considered actually, like, coding some sort of automated simulation, but that's way too much effort. But a few things:

* wallrunning on a slanted wall tends to work best when in a south / westerly direction, which is ironic given that "normal" wallrunning requires you to run due north / east.
* a wallrun along a properly angled wall can actually give you a top speed HIGHER than a normal wallrun, making it probably the highest-speed maneuver in the game that doesn't rely on something super weird.
* the "bumpiness" of trying to wallrun on a slanted wall is due to the slide calculations screwing up and trying to slide you inside the wall, which causes the algorithm to fall back to the "stairstep" code and push you away from the wall and severely hobble your speed.
* wallrunning on a slanted wall fails most severely when your direction along an axis exceeds +15, where it gets split into two halves and all of this gets amplified.

MathsDevil said:

My own view is that wall-running and strafe-running are the most doable effects and I do my best to prevent any possible trivialisation of my levels by players running far too fast. It's probably always possible for such effects to speed up running to the exit, I just don't want anyone strafe-running across an 'impossible' jump to reach an 'unreachable' location. Any thoughts?

Strafe-running is basically a normal movement technique at this point, so designing jumps to not be accessed by it is fine I think.

Beyond that though, I think it's much better to let players play how they want, and if they find an exploit or shortcut through wallrunning, rocket-jumping, etc., then good for them. Those kinds of things can be fun -- Quake certainly wouldn't have been improved if the map designers knew about rocket jumping and tried to prevent it at all costs. And most people won't do that kind of stuff much anyhow, and if your map is good, they will probably be interested in playing it more-or-less normally as well.

I think it'd be better to make sure that any areas a player might potentially reach through movement tricks doesn't land them in inescapable situations, even if it's a place where they should "never" get to.

Linguica said:

One thing I was unable to write up was an explanation of wallrunning on slanted walls.

The sole reason behind this seems to be the imprecisions in the sine table.
This will completely go away if the sines and cosines are calculated with proper math functions.

Here's how I originally fixed it in ZDoom when I first discovered this effect. First the original code, second the fixed version projecting the vector without using any trigonometry:

		if (i_compatflags & COMPATF_WALLRUN)
		{
			fixed_t newlen;
		
			if (deltaangle > ANG180)
				deltaangle += ANG180;
			//	I_Error ("SlideLine: ang>ANG180");

			lineangle >>= ANGLETOFINESHIFT;
			deltaangle >>= ANGLETOFINESHIFT;

			newlen = FixedMul (movelen, finecosine[deltaangle]);

			tmxmove = FixedMul (newlen, finecosine[lineangle]);
			tmymove = FixedMul (newlen, finesine[lineangle]);
		}
		else
		{
			divline_t dll, dlv;
			fixed_t inter1, inter2, inter3;

			P_MakeDivline (ld, &dll);

			dlv.x = slidemo->x;
			dlv.y = slidemo->y;
			dlv.dx = dll.dy;
			dlv.dy = -dll.dx;

			inter1 = P_InterceptVector(&dll, &dlv);

			dlv.dx = tmxmove;
			dlv.dy = tmymove;
			inter2 = P_InterceptVector (&dll, &dlv);
			inter3 = P_InterceptVector (&dlv, &dll);

			if (inter3 != 0)
			{
				tmxmove = Scale (inter2-inter1, dll.dx, inter3);
				tmymove = Scale (inter2-inter1, dll.dy, inter3);
			}
			else
			{
				tmxmove = tmymove = 0;
			}
		}

On 4/15/2016 at 1:19 AM, Graf Zahl said:

The sole reason behind this seems to be the imprecisions in the sine table.

I think "sole" reason might be overstating it, since the inflation in P_AproxDistance depends on the movement angle which affects the potential top speed, but I agree that the imprecise sine table is the main culprit behind the intensely aggravating experience of trying to wallrun and feeling like you're on an incredibly bumpy surface instead.

Like I said, wallrunning on a slanted wall to the southwest tends to work better, precisely because the movement doesn't get split into two parts and so there's not a second half of the slide dependent on the result of the first half. It's kind of cool that there's two versions of the exact same trick that depend on entirely different code (doubled movement + the stairstep fallback for axis-aligned wallruns, improperly inflated slide vectors for the other).

Linguica said:

I think "sole" reason might be overstating it, since the inflation in P_AproxDistance depends on the movement angle which affects the potential top speed, but I agree that the imprecise sine table is the main culprit behind the intensely aggravating experience of trying to wallrun and feeling like you're on an incredibly bumpy surface instead.

Like I said, wallrunning on a slanted wall to the southeast tends to work better, precisely because the movement doesn't get split into two parts and so there's not a second half of the slide dependent on the result of the first half. It's kind of cool that there's two versions of the exact same trick that depend on entirely different code (doubled movement + the stairstep fallback for axis-aligned wallruns, improperly inflated slide vectors for the other).

I don't think that here P_AproxDistance mattered much, because ZDoom never changed that part until very recently. Using P_InterceptVector to calculate the new movement vector made the problem go away completely.

I think the difference in direction comes from what angle it selects. Maybe in one direction it got one facing a bit towards the wall and in the opposite direction one that faces a bit away.

Here's my original bug report for ZDoom about this issue. At that point in time the other wallrunning issue was already fixed, and the report clearly says something about walking southward:

http://forum.zdoom.org/viewtopic.php?f=7&t=2903

Graf Zahl said:

I think the difference in direction comes from what angle it selects. Maybe in one direction it got one facing a bit towards the wall and in the opposite direction one that faces a bit away.

That's definitely the cause - on one test map I could get it to build up speed if a 2S linedef was pointing one direction, but just flipping the linedef caused it to fail.

What appears to generally happen is that the slide vector inches the player either towards or away from the wall, depending on which way the imprecise sin/cos table directs the slide vector, and then when it gets too close / too far away, it screws up - if it's too close, the slide vector projects inside the wall and so the engine resorts to stairstepping, and if it gets too far away, the player loses contact with the wall entirely and slows down.

The directions and angles where it works "properly" are, I think, just the ones where these effects happen to cancel each other out, and the movement away from the wall each tic as inflated by P_AproxDistance for that angle is almost exactly canceled out by the movement back towards the wall from the player's input.

If you are going fast enough to have the movement split up into two halves, this gets even worse, since the second half's movement is entirely dependent on the first half's sliding vector.

Looks like this thread's gathering quite a crowd... the number of views and active users are starting to pile up!

Well played, Ling Bizkit!

HavoX said:

Looks like this thread's gathering quite a crowd... the number of views and active users are starting to pile up!

Well played, Ling Bizkit!

It's no Instadoom though. I guess I'm slipping.

It is a very nice write-up though with "a bit more value" than Instadoom; loved reading it. And it will definitely be a great place to point people to when they want to learn something.