Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Linguica

The Doom Movement Bible

Recommended Posts

METRICS

Let’s start with the basics. The Doom engine’s code for player movement basically looks as follows:

  • Collect player input
  • Apply thrust vector to player based on input
  • Clip player's speed if it is too large
  • Actual checks, calculations, and movements
  • Apply friction slowdown to player for next tic
And rinse and repeat. Just from this, and a couple of variables, we can start off by determining the possible top speeds of the player character.

For hopefully apparent reasons, the player’s top speed is achieved when the speedup applied by the player’s input is equal and opposite to the slowdown applied by the friction.

Per tic, the player is given a thrust equal to 0.03125 units times the magnitude of the input command. Since commands are (normally) limited to a maximum of 50, this gives us a maximum frictionless acceleration of 1.5625 units/tic^2.

Then, per tic, after the movement is calculated, the player is slowed down via a friction coefficient. The specific value is 0.90625 - in other words, every tic the player is slowed down to 90.625% of their current speed.

For the speedup and slowdown each tic to be equivalent, with a running speed of 50, we need to find x where (1 - 0.90625)x = 1.5625. This comes out to a theoretical top forward running speed of 16.666 (heh) units per tic. (Note that the actual empirical top speed is a little less than this, for certain reasons, but close enough.)

Note that the player has a hard-and-fast top speed coded in - at the start of the player movement code, before the actual movement is calculated, the game checks if the X- and Y-components of their speed are greater than 30 units/tic (or less than -30), and if so, clips them to 30 (or -30). We're not going to be dealing with this speed limit for a while, but you should note that this only happens before the movement code begins and doesn't prevent the speeds from going above 30 while inside the movement code.

Finally, since I don't know where else to mention this, I need to point out that the player's collision box is an actual literal square box, and more importantly, the bounding box is always axis-aligned, regardless of which way the player is actually facing. This fact becomes very important later for a lot of things.

Share this post


Link to post

STRAFE RUNNING

One quirk of the Doom engine (and a lot of other game engines, really) is that the X- and Y-coordinates of the player are stored and calculated separately. This leads to the nice little effect that when the player moves forward and to the side simultaneously, the two movement vectors are both applied, and the direction of the resulting overall movement has a greater magnitude than either does separately.

In normal Doom gameplay, running forward has a maximum thrust of 50, and strafing sideways has a maximum thrust of 40. Strafing thereby has a maximum thrust per tic of 1.25 and a top speed of 13.333 units / tic. If you take the forward and side movement vectors as the sides of a right triangle, you find that the theoretical straferunning top speed is 21.34 units per tic - a 28% speed increase over normal running. Not bad.

Share this post


Link to post

“SR50” STRAFE RUNNING

But there’s a way to move even faster. Due to some quirks of the input code, it’s possible to hold down several buttons simultaneously in such a way to get a strafing thrust of 50 instead of 40. This results in a top speed of 23.57 units / tic - a 41% speed increase over normal running, and a 10% increase over normal straferunning.

This variety of straferunning is generally referred to as “SR50” for fairly arcane reasons - speedrunners created various tools to analyze demos, and some would print out the commands input each tic. One of the commands was “SR” for “strafe right,” which was followed by the magnitude of the command. Since this technique resulted in a strafe value of 50 instead of 40 and thus the tools would show commands of “SR50” instead of “SR40”, SR50 came to be commonly used as a synecdoche for the technique.

Oh, and just for posterity let's calculate the "real world" maximum running speed:

23.57 units/tic * 35 tics/sec = 825 units/sec
825 units/sec / 16 units/foot (a common conversion factor) = 51.5 feet/sec
51.5 feet/sec = 35 miles per hour.

Share this post


Link to post

SKIP GLIDE
 


trick at 0:02

Now let’s move on to actual tricks. This first one is considered one of the most difficult to pull off in practice, but is actually the easiest to explain in terms of the engine. I’m calling it the “skip glide,” although it’s sometimes referred to as a “bar glide,” although that is really confusing since there’s another trick that often called the "bar glide".

To understand this trick, you must first understand the basic way that Doom tries to process movement. In each tic, the Doomguy has a certain x- and y-momentum. I’m not going to call it “momentum,” though, since that term suggests certain properties which the Doom analogue does not have (you can move further than your “momentum” would suggest, or conversely, you can have "momentum" while not moving at all). Instead, I am going to talk about the "momentum" in terms of the potential new position the player wants to move to, and refer to it as the Teleport Attempt Position, or TAP. (From now on when you see "TAP" you can mentally insert "momentum," but hopefully using a different term will make you append an reminder it's not "real" momentum, but a weird pseudo-analogue with different properties.)

This is because the player does not “move,” per se, during a tic. Instead, the game merely removes the player from one point on the map and instantaneously places her on another point. This sort of discrete movement is probably universal in games, but it also raises a question: how do you know if you’re running into something in front of you?

In Doom, the first step, and usually the only step, is about as simple as you can get: take the player’s TAP - say, for instance, they want to move 15 units on the X-axis and 0 on the Y-axis - and perform a test to see if the player would be able to be “teleported” to that point without hitting anything in the landing zone. If the answer is yes, then just move them there!

With this in mind, it becomes straightforward to see how the skip glide works. Take, for example, the canonical example on Doom 2 Map21. The player is at a legal position just before the diagonal bar gap. On the next tic, the engine tests to see if the player could be teleported to a position just *after* the diagonal bar gap. With careful alignment, this will be true, and so the engine moves the player there with no complaints.

 

Share this post


Link to post

SQUEEZE GLIDE
 


trick at 0:25

This more common trick is also often referred to as the “bar glide” (sigh), because it often involves moving between key-locked bars placed 32 units apart; the term “squeeze glide,” however, seems to me to be more evocative and less confusing.

In a squeeze glide, the player perfectly aligns themselves with a gap that is precisely as wide as they are (32 units), and after some interminable period of fruitless rubbing, finally manages to squirt through (wow, that sounded dirty).

glide.gif

 

Throughout this writeup I occasionally have GIFs from the automap, where I have hacked on the code to add a blue box representing the position the engine is trying to move the player to. The blue box doesn't represent anything "real", just where the engine is trying (and often failing) to place the player or other thing in the world at that instant.

In theory, a squeeze glide should be very straightforward: the player is 32 units wide (along an axis), and if you have an axis-aligned space of exactly 32 units wide, you should be able to slot right in. However, the Doom engine is seldom so simple.

The main problem is that movement in the Doom engine is, once again, quantized, and moreover, it is imperfectly quantized. I’ve skipped over how the player’s movement vector is calculated, but in short, it uses sines and cosines to combine the player’s direction with their movement vectors to come up with final X- and Y-thrust vectors. So for example, when a player is pressing forward and is facing north, the X-component of their movement vector ought to be (some value) * cos 90, which should come out to zero. Unfortunately, the Doom engine doesn’t store angles and cosines perfectly - it uses a precalculated tables of values, and as it turns out, the sine / cosine table doesn’t actually *include* 0 as a value - the closest is +/- 0.0002ish. So the result is that even when a player is heading as close to northwards as they possibly can, there is still an infinitesimal amount of drift east or west.

So given that, and remembering how the player’s TAP works, you can see what happens:

  • The player wants to try and move into the space directly between bars
  • The engine takes their TAP, which has some quantized slop in it, and sees if it could move them to that position or not
  • Because the space is precisely as wide as the player, and the player must EXACTLY be able to move into the space, the imprecise angle values makes this a real chore - if you have exactly 0.0002 unit’s worth of XTAP, that means you need to be exactly 0.0002 units west of the space between the bars in order to make it in.

Figuring out how to make the squeeze glide work consistently turns out to be more of an art than a science, and speedrunners will spend hours upon hours learning the subtle movements necessary to perform it in a reasonable amount of time.

 

Share this post


Link to post

LINE SKIPPING (SOUTH / WEST)
 


trick at 19:06

Once we understand how the engine uses a player’s TAP to test a new position, it’s only a little further to understand line skips. In a line skip a player seems to do the impossible: run right over a linedef without actually triggering it.

To understand how this works, you must first understand the order of events in the engine:

  • Use player’s TAP to test for their potential new position
  • As part of this process, compile a list of any linedefs overlapping the potential new position
  • If it’s valid, move them to that position
  • Cast a trace line between the center of the player’s old position and their new position, and then check every linedef in the already-compiled list to see if the trace crosses any of them
  • If so, check those lines for special actions, and activate them

So there are 2 steps in crossing a special linedef: first the player must 1) be touching the linedef within their bounding box in their updated position, and 2) the trace between old and new positions must cross that linedef.

So given this algorithm, how can you fool it? Well, here’s how.

Tic 1: the player’s TAP wants them to move up to a point where their center is almost, but not quite, crossing the linedef in question
Tic 1: the engine notices that this new point touches the linedef and adds it to the list
Tic 1: after successful movement, the engine then casts a trace, but this trace does not cross the linedef, so whatever
Tic 2: the player’s TAP moves them up far enough that they move entirely *past* the linedef and are no longer touching it
Tic 2: the special linedef isn’t even in the new compiled list of touched linedefs, so it can’t be activated

So as you can see, so long as you are moving faster than half the player’s width per tic, with good positioning and some luck, it’s no big deal to skip right over a linedef. Remember, though, that the player’s bounding box is always axis-aligned, so this trick is easier to perform along an axis, where the player’s “radius” is 16 units. However, even in a 45-degree diagonal, where the player’s “radius” is 22.6 units, a properly executed SR50 run with its 23+ units per tic can still pull it off.

Also note that I’ve titled this one “south / west” line skipping. It WILL NOT WORK THIS WAY if you are moving north or east, for reasons we have not discussed yet.

 

Share this post


Link to post

ITEM BUMPING


trick at 0:16

Here’s another oddity that’s due to a weird quirk of how Doom checks a player’s potential new position. The algorithm goes as follows:
  • Use player’s TAP to determine potential new position
  • Check if there is anything obstructing the landing zone at that position
  • As part of this, check if there are any things overlapping the landing zone
  • And as a part of that, if any of those things are pick-uppable, pick them up
Do you see the problem? The game will pick up items touching a potential TAP landing zone even if the move is ultimately unsuccessful. That means if you barrel full speed into an impassible linedef with an object right on the other side of it, the engine will - just as you are about to crash into the linedef - attempt a TAP slightly on the other side of the wall, and pick up any items that happens to be right there.

Share this post


Link to post

MONSTERS OPENING DOORS


trick at 0:09

Although this isn’t directly related to player movement, it’s still noteworthy, and follows many of the same principles. The engine largely treats monster movement identically to player movement - it tracks the monster’s TAP, and then uses that TAP to test a potential landing zone for the monster’s next move.

Much like with the player picking up items, the engine has a certain laundry list of things it does when testing a potential new monster position. One of these things is to compile a list of any linedefs touching the potential new position. If any of these linedefs have special actions, the AI specifically tries to “use” them, with the idea being that if there is a door in the way, the monster can open the door.

The trick here comes when a door has been built in such a way that one side of it is, for example, locked by a key, but the other side acts as a “normal” door. When a speedy monster like the archvile comes near it, its large TAP can mean the engine tries to place them overlapping the far, unlocked side of the door, and thereby open it.

Share this post


Link to post

Part 2: The SlideMove Swamp

Up to now, all of the movement tricks have revolved around the basic quantized nature of the Doom engine and its movement code. From here, however, we delve deeper into the code, into a function innocuously called P_SlideMove, which carries a warning to any unwary readers that “this is a kludgy mess.” I don’t know if this comment was added by John Carmack, or by Bernd Kreimeier while cleaning up the source code, but it’s, uh, accurate.

Share this post


Link to post

WALL RUNNING

We have seen how large TAPs can lead to glitches, with skipped linedefs, etc. Luckily, the Doom engine tries to account for this! If problems arise when a player can move too far in one go, why not split up movements into several bite-sized pieces? And that’s just what the Doom engine does - if a player’s XTAP or YTAP is greater than 15 units (which, not coincidentally, is slightly smaller than the 16 units of a player’s radius), the engine will try to split the player’s movement into two steps, and run those steps sequentially. That way there’s an intermediate position that the engine is going to check and therefore is less likely to end up skipping over something entirely. You can think of this procedure as a double-TAP (heh).

Quote

(“But wait,” you cry. “You were just talking about linedef skips! So if this code exists specifically to prevent such a thing, how does that work?” Unfortunately, there’s a fairly big flaw in this code:


if (xtap > 15 OR ytap > 15)
Can you spot it? Well, what happens if the player’s movement is towards the south or west? XTAP and YTAP are *negative* numbers, and the code, for some strange reason, does not actually check that.)

 

Anyways, back to the topic at hand. So when the Doom engine tries to move the player via their instaneous TAP, if that movement fails because the landing zone is blocked, the engine punts to P_SlideMove, which is a function to check for a collision in the way, and if so, to move the player appropriately to make that collision seem realistic.

To begin, the engine figures out the direction the player is moving, and draws three traces from the three leading corners of the player’s bounding box.

It then checks each of these traces to see if they collide with anything. If so, the engine determines what percentage of the way along the desired path the collision occurs, and moves them up to this point.

It then takes the remainder of the TAP, and redirects it in the direction of the wall the player just “collided” with - this is the “slide” portion of the movement.

slide.png

This all works fine, more or less. But there’s another insidious problem here: the sliding code uses the player’s original TAP, even if the TAP has been halved because the player’s movement has been split into two separate parts.

So with this in mind, how does wallrunning happen? Well, let’s review the steps:

  • Player is brushing up against a long horizontal wall
  • Player’s current TAP is, let’s say, 20 XTAP and 2 YTAP
  • The engine notices that XTAP is too big and decided to split it into 2 steps, each of 10 XTAP and 1 YTAP
  • The engine tries the first half check and can’t move the player any further north because the wall is there
  • P_SlideMove starts and casts 3 traces from the player’s north and east-facing corners - but these traces use the TAP of 20 / 2, not 10 / 1
  • The traces hit the wall just to the north
  • The engine moves the player, say, 5% of the way along the desired TAP
  • The engine redirects the remaining 95% of the TAP eastwards and moves the player 19 units east or thereabouts
  • The engine dusts its hands, and immediately starts the *second* half of the movement check, where it goes through the same process, moving the player another 19 units east

So in other words, when the player is moving northwards or eastwards with a XTAP / YTAP greater than 15, and has the initial movement check blocked by something, the engine has the potential to perform *two full movements* in a single tic! Note that this doesn’t actually change the TAP or anything - it’s just as if the player moves two tics’ worth of movement in a single tic.

 

Share this post


Link to post

THING RUNNING
 


trick at 0:12

Following on from wallrunning, what happens if the player happens to be close to a solid object, or even better, a long row of solid objects?

The game will try and move the player to a new position, and be blocked because there is an object in the landing zone. Then the engine calls P_SlideMove and casts 3 traces from the player’s corners, and finds: no linedefs? What does the engine do now?

Well, oddly, the Doom engine doesn’t actually check for collision with things in this function, only for collision with linedefs. In case of last resort, when the engine can’t actually find any linedefs that appear to be blocking the player, it instead performs a “stairstep” - it tries to move the player purely along their YTAP, and failing that, purely along their XTAP. And remember that all things in the Doom engine have axis-aligned bounding boxes - so this means that if the player is moving towards a solid thing, and the “stairstep” fallback decides to move them purely horizontally, it is pretty much as if the player is sliding along the side of the thing anyway.

So with this in mind, thingrunning occurs in pretty much exactly the same fashion as wallrunning - the player is moving north or east at a high rate of speed, their movement check gets split in two, and each half gets the full TAP applied while there is a thing blocking the landing zone. The full XTAP or YTAP gets applied in a single tic, making the player seem to run twice as fast while sliding along the edge of the thing. This trick is best-known for its dramatic use in Map23, where a player can thingrun across a line of barrels to “jump” over part of the map in a seemingly impossible fashion.

thingrun.gif

 

Share this post


Link to post

WALLRUN “AIR CONTROL”
 


trick at 10:17

The first time I saw this trick, I was so taken aback that it actually motivated me to write this whole guide you are currently reading.

One of the hard-and-fast rules of Doom movement is that the player has no “air control” whatsoever. In short, if the player’s feet are not touching the ground, they are solely at the whims of physics (such as those physics are). So I was amazed when watching a Map14 speedrun where the player performs a midair wallrun along a wall towards the exit - and at the end, actually appears to turn in midair and move into the southern exit hallway despite having moved perfectly eastwards up to that point.

At first I simply could not understand how this trick was possible - the player’s TAP was purely towards the east! They had 0 YTAP, how could they move south! But, as usual, the code is more subtle than it first appears.

It turns out that if the player is too close to an obstruction, the engine won’t even attempt to move them any closer to that obstruction, but instead goes immediately to the “stairstep” fallback. The magic number here is 3.125% - if one of the trace lines cast from the player’s corners intercepts a wall at less than 3.125% of the way along its length, the game won’t even attempt to move the player along the original direction of movement, but instead skips straight to the stairstep fallback. The important part of this is that when the engine tries to move the player either directly vertically or directly horizontally in the stairstep code, it doesn’t actually change the player’s TAP in the process.

So with this in mind, the amazing midair directional change becomes explainable. The player “takes off” while pressed up against the wall, with a large XTAP and a slight southern YTAP. During each tic in midair, the engine checks if it can move the player to the east and slightly to the south, and when this is blocked by the wall in the way, it gives up and “stairsteps” the player due east - but doesn’t actually change the player’s TAP at all, and thereby maintaining the slight negative YTAP the whole time. Then, finally, when the exit hallway is within reach, the player’s movement check succeeds, and the player appears to manage to “grab a toehold” in an utterly impossible fashion.

air control.gif

 

Share this post


Link to post

LINE SKIPPING (NORTH / EAST)

I include this trick for the sake of completeness, although it is really just the result of adding together two previously described tricks. We have already seen how a player moving faster than 16 units / tic can skip a linedef activation by having good positioning. We’ve also seen how when moving fast to the north or east, the player's movement is split up into two parts, but the sliding code can cause a player to effectively move twice as far within one tic.

Well, these can be combined to skip linedefs while traveling to the north or east. If the player wallruns (or thingruns) with a total speed of over 32 units / tic, or 16 units per half movement step, they will be able to skip over the linedef in the same manner as the south / west linedef skip.

Share this post


Link to post

MOMENTUM PRESERVATION

This trick is not terribly flashy, and it’s hard to find a “proper” name for it. I’ve seen it called “door trick,” as it seems to be most often used by a speedrunner while waiting for a door to open. Door stuck?

The trick is simple - by pressing up against solid walls in a certain way, the player is able to maintain their full TAP even while standing still. (This is evident by the visual aid of the player’s weapon wobbling back and forth at full speed - for this reason, certain variations of this trick are often referred to as a “wobble glide”.) This means that if you are running into an opening door, and can maintain your TAP while the door opens, the instant the door is open wide enough you will shoot right through, saving precious milliseconds.

momentum preservation.gif

But how does this trick work? Normally if you run into a wall in Doom, your TAP is cut way down - as is evident by the barely-there sway of your gun. Well, to understand this trick, we have to get down deep into the weeds of how the Doom engine figures out collisions.

Remember that normally when calculating collision with a wall, P_SlideMove will calculate the percentage of the player’s trace towards the wall - or maybe skip that part altogether if it’s less than 3.125% - and then redirect the remainder in the direction along the wall. (This is what kills your speed normally - if you barrel straight into a wall, the sliding speed is proportional to the cosine of the difference in the angle between your direction and the wall’s direction, and cos 90 is 0.)

But let’s go deeper - how, *exactly*, does the engine figure out if you’re about to collide with a wall? When you get down to it, the engine wants to figure out a simple mathematical equation: take the line segment describing the wall, and the line segment describing the movement trace from one of the player’s corners, and find out if these line segments intersect. There are various ways of doing this with matrices and vector math and so forth, but Doom uses the simplest method: take the endpoints of line A and see which side of line B they are on, and then take the endpoints of line B and see which side of line A they are on. If both are on opposite sides of the other line, then the two line segments cross.

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 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 from -32768 to 32767. So when you are multiplying two arbitrary numbers together, you have to be careful that they don’t multiply to a value larger than that. The square root of 32767 is 181, so even comparing lines a mere 200 units long could potentially overflow it. So what to do?

This is a part of how the Doom engine handles this issue in a function where it checks for line segment intersections:

left = (line->dy / 256) * (dx / 256);
right = (dy / 256) * (line->dx / 256);

As you can see, it just divides all the values by 256 before going on. (It actually right-shifts them by 8, to be pedantic, but same difference.) By doing this, it can be reasonably sure that the product of the values won’t be big enough to overflow, and we’re still only effectively dropping from 16 fractional bits to 8 fractional bits by doing this, which isn’t much of a problem, right?

Well, normally, it *isn’t* a problem - but what happens if a player’s TAP in one direction is extremely small? Say, for instance, a player is running into a corner with a XTAP of 20 and a YTAP of 0.001. The following will happen:

  • The engine tries to move the player 20 units east and 0.001 units north, but can’t do it because there is a wall just to the north
  • The engine punts to P_SlideMove and draws 3 traces from the player’s corners
  • The engine checks the first trace and it detects the wall to the east like normal
  • The engine checks the second trace but because the values are all divided by 256, the tiny 0.001 YTAP is rounded to zero and the trace thereby doesn’t “hit” the wall to the north
  • After the traces, the engine tries to move the player to the fractional position along the first trace, let’s say 50% of the way along that trace
  • But when the engine tries to place the player at a position 0.0005 units further north, it fails because the wall is there
  • The engine gives up and “stairsteps” which preserves the momentum

So in conclusion: if you are running into a corner with an infinitesimally small XTAP or YTAP, it is possible to maintain your TAP because the engine’s rounding measures result in a false negative and a subsequent preservation of the player’s TAP.

 

Share this post


Link to post

VOID GLIDE


trick: 0:20

Now we’re into the real big guns: not just skipping a special linedef, but skipping an *impassable* linedef altogether.

At first glance, this trick ought to be impossible. In order to pass through a wall, the player has to be instantaneously moved at least 32 units - from one side of the wall to the other. But the maximum velocity you can attain through SR50 is 23.57 units, and even when wallrunning, you’re still doing two separate movements of 23.57 within a single tic. Moreover, the game has a hard "speed limit" of 30 units at the start of the movement calculations. So how can you possibly build up the speed to move 32 units at once?

Well, although it’s true that 23.57 is the maximum TAP you can attain through normal input, it’s not the fastest the engine will allow you to go - nor is thrust from player input the only way to increase TAP!

(I’m going to elide any mention of damage boosts here - those are difficult to control and difficult to test. It is possible to build up speed in excess of 23.57 by being hit by, say, a rocket, but there is a better and less dangerous method.)

Let’s head back into P_SlideMove again. You may remember that I have mentioned that after moving a fractional distance along a trace, the remainder of the TAP is redirected along the direction of the linedef. So: how is this accomplished? Well, the process has three steps:

  • Determine the magnitude of the remaining player TAP
  • Create a vector along the new angle with this magnitude
  • Decompose the new vector into its x- and y components and use that as the player’s new XTAP and YTAP

This is easy enough to do with sines and cosines, and most of the code works fine. However, there is one huge glaring shortcut that the code takes. Rather than determine the magnitude of the remaining player TAP *properly*, it uses a function called P_AproxDistance (sic). And what does P_AproxDistance do?

return (the longer of XTAP or YTAP) + (half the shorter of XTAP or YTAP)

That’s right - no sines or cosines, no squares or square roots, no nothing. Just one axis plus half the other axis. As you might imagine, this is not a terribly accurate “aproximation.”

One nice aspect of this approximation is that it is always *larger* than the actual value. So let’s say we want to calculate a player slide, where let’s say the XTAP is 3 and the YTAP is 4. The Pythagorean theorem tells us that the magnitude of the slide ought to be 5 - the hypotenuse of the right triangle with 3 and 4 as sides. Using P_AproxDistance, however, we calculate a magnitude of 5.5. We’ve managed to speed up 10% just because of this inaccurate approximation! The amount of increase depends on the angle the player is trying to move, and sadly around 45 degrees (the most common angle for a void glide) it dips to a mere 6% or thereabouts, but this is still plenty.



There’s one more twist to add in order to make this useful. P_SlideMove basically works as follows:

  • Start with a counter of 1
  • Cast the corner traces and try and move the player using one of those
  • If there’s a slide remainder, calculate it and try and move the player to *that* position
  • If the attempted slide-remainder movement fails, go back to the beginning and increment the counter
  • If the counter gets to 3, give up, try to stairstep, and then bail out

The logic here is pretty sound: if a player is near to a corner, the first slide move could take them up to wall 1, and then the slide remainder could cause them to immediately impact into wall 2, so the algorithm restarts with the slide remainder to handle the second impact with wall 2 from scratch. The trick is that it’s possible to engineer a situation where P_SlideMove keeps failing to find a valid landing zone, and so the following happens:

  • Cast the corner traces
  • The shortest corner trace hits a wall at less than 3.125% of the way along its length
  • Immediately calculate the “slide remainder” using the whole current TAP
  • In doing so, the TAP inflates because of the poor approximation
  • The inflated slide-remainder landing zone fails and so it restarts
  • It gets inflated a second time via the same process
  • The algorithm gives up and tries a stairstep, which fails, and it bails out, having increased the player’s TAP twice

Furthermore, if the player’s TAP is heading north or east and is above 15, this gets doubled by the two halves of the movement code, resulting in four increases to the player’s TAP within a single tic!

void glide.gif

So from this you can see how the process can feed back on itself: once you get in the right position, you get a positive feedback loop. Each tic you gain two (or four) relatively small TAP boosts from the imprecise slide approximation. At the end of the tic this is, of course, reduced by friction, but as long as the overall boost within a tic is at least 10%, this will be more than the slowdown from friction and the overall trend will be to increase the TAP. Then it’s just a matter of keeping at it until your TAP is at least 32.

“But the game caps your maximum tap to within 30!” You say. Well, yes - so the last tic before the void glide needs to start with a TAP close to 30, and then within the 4 slide speedups, bump that TAP from below 30 to over 32. This isn’t too difficult, and you can even end up with an instantaneous TAP of 37 or 38.

One final note: this trick will only work if the wall you are sliding against is not axis-aligned. If it is, the engine takes a shortcut and just returns the XTAP or YTAP without going through the process of creating a new redirected vector. Since most walls in levels tend to be axis-aligned, this significantly limits the trick's usefulness.

 

Share this post


Link to post

ELASTIC COLLISIONS

If you thought void glides were weird and arcane, I have one final trick up my sleeve: elastic collisions. These are actually not super rare, but they happen so seemingly randomly and with some strange properties that I’ve never heard of a case of the trick being used in speedrunning.

djDUeWE.gif

(sample WAD of this behavior: https://www.doomworld.com/linguica/hax/launch.wad )

An elastic collision involves the player’s TAP instantaneously flipping from one direction to the exact opposite direction. This can be very dramatic and violent - one second you have a TAP of 15, and suddenly you have a TAP of -15, with no warning. It’s like you’ve just bounced off something hard and are suddenly headed the opposite way, and there is usually nothing to explain it.

To explain elastic collisions, we have to delve back into the low-level collision code. Remember in the momentum-preservation glitch, I talked about the algorithm for determining if two line segments intersect? Well, I left something out: there are actually *two* algorithms for determining if line segments intersect. They are largely the same, but there is one important difference we are concerned with here: one is used if the absolute value of XTAP or YTAP are larger than 16 units, and the other is used if they are equal or less than 16 units.

“OK, but what does that mean?” You ask. Well, even though the algorithms are mostly the same, they are used in different ways: for the long TAP traces, the algorithm uses the trace line and tests the two vertexes of the linedef in question. For the short TAP traces, the algorithm uses the linedef as the line and tests the two endpoints of the trace.

This might not sound like a big deal, but there’s another wrinkle: when the game uses the short-TAP algorithm, it doesn’t actually check the endpoints of the linedef against the trace. Remember that for the line intersection determination, you need to test line B against the endpoints of line A, and line A against the endpoints of line B, but in this case, Doom stops halfway through and calls it a day.

The result of this is that for short TAP traces, the Doom engine will believe that a trace hits a linedef when it doesn’t, if the trace happens to cross the infinitely extended line of the linedef. In normal gameplay this doesn’t come up very often because most of the time you are not sliding along walls at all - but if you’ve ever been sliding on a wall and suddenly get stopped short for no apparent reason, it’s probably because of this bug, and the engine believed you ran into a linedef that you’re not even close to.

But that’s not elastic collisions - that’s stopping! That’s the opposite of elasticity! Well, let’s go back to the line-sliding code, and notice something else.

When the engine is determining the direction the remainder of your TAP should slide along the line, it does so by comparing the line to your centerpoint to see which side of the line you’re on, and then calculating the difference in the angle between the way you’re headed and the way the line is headed. It assumes that the angle it’s using is between 0 (headed parallel in one direction to the line) to 180 (headed parallel in the other direction).

But here’s the kicker: what if it turns out the angle between the player’s movement and wall, for whatever reason, is *not* between 0 and 180 degrees?

if (deltaangle > ANG180)
        deltaangle += ANG180;

The game pretty much throws up its hands at this point and just flips the angle - and thus the final directional vector - entirely. Luckily, since this should never happen, it will never be a problem, right?

Well, what happens if the center point of the player is on one side of a line, but the *corner* of the player - from which their movement trace is emitted - is on the *opposite* side of the line? Then when using the movement trace to determine the slide angle, the algorithm would assume it’s on the wrong side, and flip the angle 180 degrees.

But wait - if the center of the player is on one side of a line, but the corner of the player is on the other side, the player is crossing the solid line and should be stuck in place or whatever, right? Well, usually, yes - but if the player’s movement trace is less than 16, and there’s a properly angled linedef nearby, the player’s corner trace will “hit” the distant linedef, try to calculate a slide angle, freak out because it’s out of the normal bounds, flip the angle, and then impart the new, flipped TAP to the player, who will suddenly be confused about their new direction.

elastic collision.gif

 

Share this post


Link to post

Excellent work, and great to have it all in one place. How long did this all take to put together, dare I ask?

Elastic collisions in particular are something I find quite annoying when moving. I'd be really impressed if someone managed to actually use them in a speedrun intentionally. But perhaps now that they're better documented, it could happen.

Share this post


Link to post

Awesome guide. Should be pinned imo.

plums said:

Excellent work, and great to have it all in one place. How long did this all take to put together, dare I ask?

Elastic collisions in particular are something I find quite annoying when moving. I'd be really impressed if someone managed to actually use them in a speedrun intentionally. But perhaps now that they're better documented, it could happen.


I personally have encountered this elastic jump several times(unintentionally ofc). Particularly while doing arch-vile jumps, i tend to hit the wall and bounce back to an incredible height/distance in the exact opposite direction. I did not give any special attention towards it though. By better understanding i guess this elastic jump could be used to reach higher platforms which is otherwise impossible to reach by normal means or single arch-vile jumps(especially while making TAS demos).

Share this post


Link to post

Thank you for this thread. I need to refer to it when developing my Doom bot.

Share this post


Link to post
SWDude said:

Awesome guide. Should be pinned imo.

I'll definitely link to this from one of the speedrunning stickies. It's invaluable to have all of the tricks explained by hard science!

Share this post


Link to post

Awesome work, L! I see that you also independently verified my older speed tables, at least for the most "vanilla" cases up to and including SR50 (the MPH metric however is based on an arbitrary interpretation of "Doom units" to "real world units"). N.B., what I mean by "Strafe-run" in that table, actually means a pure strafing movement while having RUN on, not combined strafe+forward movement "straferunning".

I know that my estimates of wallrunning (including what I call "Straferun-Wallruning") are flawed however. The speed I report as "Wallrunning" is actually what I obtained by performing a short N-S wallrun in MAP01 of Doom II, across linedefs 315-322, with a SR-40 input. I realize that with other orientations and different inputs, other speeds might be achieved.

Share this post


Link to post

Fantastic job, @Linguica!

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

Share this post


Link to post

I read the whole thread. Some things in Part 1 and nearly everything in Part 2 was new to me (or unclear up to now), and I'm glad to learn about those tricks and glitches. Thanks for writing all of this!

I have a question about "north/east line skipping": Start with an assumption that the player's movement is split into 2 parts, each of which calls P_SlideMove. You've implied (albeit not explicitly said) that only the final position of this 2-part movement matters when registering spechits. But actually, each P_SlideMove calls P_TryMove to do its movement. In fact, looking at the code, it seems that P_SlideMove won't return until P_TryMove is called successfully. P_TryMove itself registers spechits (in its subcall of P_CheckPosition), and if P_TryMove succeeds, it immediately executes those spechits right before returning true. So, the in-between position of the 2-part P_SlideMove movement should be able to trigger walkover linedefs! So, the fact that the movement is 2-part shouldn't actually matter, the effective linedef-skipping distance is the same as in south/west movement, and the conditions (and chance) to successfully skip a linedef are also the same. Am I right?

Share this post


Link to post
scifista42 said:

So, the fact that the movement is 2-part shouldn't actually matter, the effective linedef-skipping distance is the same as in south/west movement, and the conditions (and chance) to successfully skip a linedef are also the same. Am I right?

Yeah, for some reason I wrote the sequence of events incorrectly. What you essentially need is a wallrun of greater than 32 units / tic, so that each half of the movement check can act as a linedef skip of its own accord.

scifista42 said:

it seems that P_SlideMove won't return until P_TryMove is called successfully.

No, if the function falls back to the "stairstep" part and that fails, it returns anyway despite not having successfully moved, or having changed the player's TAP. That's key to how several of the tricks work.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×