July 28, 2016 at 22:47Bible of Doom movements. Part 1
- Transfer
- Recovery mode
Hello and welcome to the Doom Movement Bible! In the article, all the quirks and vagaries of the code of movements in Doom are sorted and sorted into categories, including intricate tricks with a description of their work.
Let's start with the basics. The engine code for the player’s movements in Doom is as follows:
Let's consider all in more detail.
Thanks only to this and a couple of variables, we can determine the possible maximum speed of the player’s character.
For obvious reasons, the maximum speed of the player is achieved when the acceleration specified by the player is the same and opposite to the deceleration from friction.
For each tick, the player receives a push equal to 0.03125 units, based on the value of the entered team. Since teams (usually) are limited to a maximum of 50. This gives us a maximum friction acceleration of 1.5625 units / tick ^ 2.
After calculating the movement per tick, the player slows down using the coefficient of friction. The specific value is 0.90625 - in other words, each player’s movement slows down by 90.625% of his current speed.
For the equivalence of acceleration and deceleration of each tick, at a speed of 50, we need to find "x" at (1 - 0.90625) x = 1.5625. This leads us to the theoretical peak of the progressive speed of 16.666 units per tick. (Please note that the actual empirical maximum speed, for certain reasons, is slightly less than this value. But still, it is quite close to the indicated indicator).
Also note that the player has a constant maximum speed specified by the code. Even before actually calculating the player’s movement, at the beginning of the code, the game checks if the X- and Y-coordinates do not exceed a speed indicator of 30 units / movement ^ 2 (or less than -30). If they exceed, then the game reduces the speed to 30 (or to -30, respectively). We will not focus on the speed limit, but it should be noted that this happens only before the start of the movement code and does not prevent the speed from reaching more than 30 within the movement code itself.
To summarize, I should note the following. The player’s collision box is actually square, and, more importantly, the bounding box is always aligned along the coordinate axes, regardless of which path the player follows. Subsequently, this detail becomes very important for many things.
Another quirk of the Doom engine (as in the essence of many other game engines) is that the X- and Y-coordinates are stored and calculated separately. This leads to one small but funny effect. When a player simultaneously moves forward and to the side, both motion vectors are used in the calculation and the direction of the general movement gets a larger value than in the vectors separately.
In normal Doom gameplay, the strafe has a maximum driving force of 50 units, and with lateral movement - 40. Thus, when straining, the driving force per tick reaches 1.25 units, and the maximum speed is 13.333 units / movements. If we consider the vectors of lateral and direct motion as the sides of a right triangle, you will find that the maximum theoretical speed during strafe is 21.34 units per movement. And this is 28% higher than normal speed, which is not very bad.
But there is a way to move even faster. According to some features of the code, it is possible to simultaneously hold down several keys at once in such a way as to get a driving force when straining at 50 units, instead of 40. Thus, you have the opportunity to accelerate to a maximum speed of 23.57 units / movement (that is, 41% higher normal speed with normal running and 10% with a straight run).
For a variety of mysterious reasons, such a wide variety of running strains is usually associated with the abbreviation SR50. Game speed professionals have created various tools used to analyze demos. And with some tools you can parse every tick. Actually, one of the creator teams was called “SR” - strafe right, followed by the argument of the team. Since this technique made it possible to achieve a running strain of 50 instead of 40, the instruments showed SR50 instead of SR40. It was the SR50 that began to be widely used as a synecdoch for this technique.
Oh, and also, so to speak, for future generations - let's calculate the maximum running speed in the "real world":
23.57 units / movement * 35 movements / second = 825 units / second
825 units / second / 16 units / foot (total conversion factor) = 51.5 feet / second
51.5 feet / second = 35 mph (about 56 km / h).
trick at 0:02
Now let's move on to specific tricks. The first of them is considered the most difficult to implement in practice. But at the same time, it is easiest to explain from the position of the engine. I call this trick “skip glide” (sometimes a slide jump), although sometimes it is also called “bar glide”, which can be confusing because there is another trick with the same name.
To understand this trick, you first need to understand the basic way in which Doom tries to handle movements. In each tick, DoomGuy has a specific x- and y-coordinate of the momentum (direction of inertia). However, I will not call this an “impulse”, since a similar term implies certain properties that Doom does not have (you can move beyond the limits of the “impulse”, or vice versa, you can have an “impulse” even if there is no movement at all) . Instead, I will talk about the “momentum” in terms of a potentially new position that the player wants to move to and refer to as the “Teleport Attempt Position” or SPT. (From now on, meeting the abbreviation “SPT” in the text, you can mentally replace it with “impulse.” But I hope that using another term will help you remember
The reason is that the player is essentially inactive during the tick. Instead, the game simply removes the player from one point on the map and instantly places it in another. This kind of discrete movement is probably universal for games. But at the same time, a reasonable question arises: how to determine that you are faced with something in front of you?
This feature helps to understand how “skip glide” works. Consider the canonical example from Doom 2 when passing Map 21. The player takes a completely natural position right in front of the diagonal screen that closes the gap. At the next tick, the engine conducts a test to determine whether it is possible to teleport the player to a position immediately * behind * the diagonal screen. With a careful choice of direction, you can designate a position that will not contradict the conditions of the "teleport" and the engine will transfer the player to the desired point without any problems.
trick at 0:25
Also in the arsenal there is another, even more common trick, which is associated with the reception of “bar glide”, because it is also based on the movement between the screeners located at a distance of 32 units. For me, the term “squeeze glide” (gliding with “squeezing”) seems more adequate for memorization and less confusing.
For squeeze glide, the player should perfectly align with the gap, the same size as the character (32 units). Then, after a series of unsuccessful attempts, lasting, it seems, for ages, he finally manages to squeeze into this gap!
In theory, “squeeze glide” should be quite simple and straightforward: the player has a width of 32 units (along the axes). And that means if you find a space that is clearly aligned along the axes and with a width of 32 units, you should be able to go through it. But with the Doom engine, it is rarely that simple.
The main problem is that the movement in the Doom engine is quantized and, moreover, it is not fully quantized. I will not go into details and tell how the player’s motion vector was calculated. But in short, the vector uses sines and cosines to combine the player’s direction with the motion vectors to compare with the final X- and Y-vectors of the driving force. For example, when a player pushes a key forward and heads north, the X-coordinate of the motion vector should be a value multiplied by cosine 90, which is necessary for zeroing. Unfortunately, Doom is not good at preserving angles and cosines, it uses calculation tables of values and, as it turned out, the sine / cosine table does not actually include 0 as a value (the closest ± 0.0002).
Thus, even with a maximum approach to the north, a value appears that is still too small for a step to the east or west.
So, knowing how SPT works for players, you can see what happens:
Understanding how to make squeeze glide work smoothly is not a science, but a real art. Speedrunners study hour after hour the intricacies of movement in order to complete it in a reasonable amount of time.
19:06 trick
Understanding how the engine uses SPT players to test a new position will only bring us a little closer to understanding line skip. It may seem that the player does the impossible when he performs a line skip: he runs directly across the border line without actually activating it.
To understand how this works, you need to look at the order of events in the engine:
Thus, as you can see, there are two possibilities for crossing a special border line: 1) touching the border line at the point of the updated position, and 2) the border is crossed by the line connecting the old and updated positions.
So, the algorithm is given. How can you get around it? Something like that.
Tick 1: SPT players seek to move them to a point where their center practically, but still not quite, crosses the border.
Tick 1: the engine determines that this new point touches the border and adds it to the list.
Tick 1: after successful movement, the engine throws the intersection line, but it does not cross the border, so it doesn’t matter
Tick 2: SPT players move them far enough that they move completely * behind * the border line and do not touch it anymore
Tick 2: the special border line is not even in the newly compiled list of crossed borders, as a result of which it cannot be activated.
So you see that while moving faster than half the player’s width per tick (having a good location and a bit of luck), there is nothing improbable in slipping through the border line without activating its special actions. However, remember that the player’s bounding box is always aligned with the coordinate axes. In other words, this technique is easier to perform along the axes, where the “radius” of the player is 16 units. However, even on a diagonal of 45 degrees, where the “radius” of the player is 22.6 units, the SR50 strafe run with its 23+ units per movement is still feasible.
I want to draw your attention to the fact that the above describes only the movement to the “south / west”. For reasons that we have not yet discussed, this technique WILL NOT WORK when moving north or east.
0:16 trick
Here's another absurdity due to a strange and bizarre Doom test of a potentially new player position. The algorithm is arranged as follows:
Do you see the problem? The player will pick up items relating to the potential landing area of the SPT, even if the move ultimately does not occur. This means that if you rush at full speed to an impassable border with an object located directly on the other side of it, the engine (at the moment of collision with the border) will attempt to move the player (SPT) to the other side of the wall. This will give you the opportunity to pick up any things that come across at the site of a potential landing.
trick at 0:09
Despite the fact that this paragraph does not apply to the direct movement of the player, he is nevertheless notable and is largely guided by the same principles. For the most part, the engine considers the movement of the monster identical to the movement of the player. In other words, it monitors the monster’s SPT, and then uses this SPT to test the potential landing zone for the monster’s further movement.
In this case, the reception is triggered if the door was created in a way where one side, for example, is locked with a key, and the other side is a “normal” door. While a fast monster (like archvile) is walking near the door, its huge SPT indicates the engine’s attempts to place this monster at a considerable distance from the open side of the door. And so the monster is able to open it.
Metrics
Let's start with the basics. The engine code for the player’s movements in Doom is as follows:
- Player baseline data collection
- Applying driving force vectors to a player based on raw data
- Squeezing a player’s speed if it’s too high
- Verification, calculations and movements
- Using friction acceleration for next player move
Let's consider all in more detail.
Thanks only to this and a couple of variables, we can determine the possible maximum speed of the player’s character.
For obvious reasons, the maximum speed of the player is achieved when the acceleration specified by the player is the same and opposite to the deceleration from friction.
For each tick, the player receives a push equal to 0.03125 units, based on the value of the entered team. Since teams (usually) are limited to a maximum of 50. This gives us a maximum friction acceleration of 1.5625 units / tick ^ 2.
After calculating the movement per tick, the player slows down using the coefficient of friction. The specific value is 0.90625 - in other words, each player’s movement slows down by 90.625% of his current speed.
For the equivalence of acceleration and deceleration of each tick, at a speed of 50, we need to find "x" at (1 - 0.90625) x = 1.5625. This leads us to the theoretical peak of the progressive speed of 16.666 units per tick. (Please note that the actual empirical maximum speed, for certain reasons, is slightly less than this value. But still, it is quite close to the indicated indicator).
Also note that the player has a constant maximum speed specified by the code. Even before actually calculating the player’s movement, at the beginning of the code, the game checks if the X- and Y-coordinates do not exceed a speed indicator of 30 units / movement ^ 2 (or less than -30). If they exceed, then the game reduces the speed to 30 (or to -30, respectively). We will not focus on the speed limit, but it should be noted that this happens only before the start of the movement code and does not prevent the speed from reaching more than 30 within the movement code itself.
To summarize, I should note the following. The player’s collision box is actually square, and, more importantly, the bounding box is always aligned along the coordinate axes, regardless of which path the player follows. Subsequently, this detail becomes very important for many things.
Strafe running
Another quirk of the Doom engine (as in the essence of many other game engines) is that the X- and Y-coordinates are stored and calculated separately. This leads to one small but funny effect. When a player simultaneously moves forward and to the side, both motion vectors are used in the calculation and the direction of the general movement gets a larger value than in the vectors separately.
In normal Doom gameplay, the strafe has a maximum driving force of 50 units, and with lateral movement - 40. Thus, when straining, the driving force per tick reaches 1.25 units, and the maximum speed is 13.333 units / movements. If we consider the vectors of lateral and direct motion as the sides of a right triangle, you will find that the maximum theoretical speed during strafe is 21.34 units per movement. And this is 28% higher than normal speed, which is not very bad.
"SR50" strafe running
But there is a way to move even faster. According to some features of the code, it is possible to simultaneously hold down several keys at once in such a way as to get a driving force when straining at 50 units, instead of 40. Thus, you have the opportunity to accelerate to a maximum speed of 23.57 units / movement (that is, 41% higher normal speed with normal running and 10% with a straight run).
For a variety of mysterious reasons, such a wide variety of running strains is usually associated with the abbreviation SR50. Game speed professionals have created various tools used to analyze demos. And with some tools you can parse every tick. Actually, one of the creator teams was called “SR” - strafe right, followed by the argument of the team. Since this technique made it possible to achieve a running strain of 50 instead of 40, the instruments showed SR50 instead of SR40. It was the SR50 that began to be widely used as a synecdoch for this technique.
Oh, and also, so to speak, for future generations - let's calculate the maximum running speed in the "real world":
23.57 units / movement * 35 movements / second = 825 units / second
825 units / second / 16 units / foot (total conversion factor) = 51.5 feet / second
51.5 feet / second = 35 mph (about 56 km / h).
Skip glide
trick at 0:02
Now let's move on to specific tricks. The first of them is considered the most difficult to implement in practice. But at the same time, it is easiest to explain from the position of the engine. I call this trick “skip glide” (sometimes a slide jump), although sometimes it is also called “bar glide”, which can be confusing because there is another trick with the same name.
To understand this trick, you first need to understand the basic way in which Doom tries to handle movements. In each tick, DoomGuy has a specific x- and y-coordinate of the momentum (direction of inertia). However, I will not call this an “impulse”, since a similar term implies certain properties that Doom does not have (you can move beyond the limits of the “impulse”, or vice versa, you can have an “impulse” even if there is no movement at all) . Instead, I will talk about the “momentum” in terms of a potentially new position that the player wants to move to and refer to as the “Teleport Attempt Position” or SPT. (From now on, meeting the abbreviation “SPT” in the text, you can mentally replace it with “impulse.” But I hope that using another term will help you remember
The reason is that the player is essentially inactive during the tick. Instead, the game simply removes the player from one point on the map and instantly places it in another. This kind of discrete movement is probably universal for games. But at the same time, a reasonable question arises: how to determine that you are faced with something in front of you?
This feature helps to understand how “skip glide” works. Consider the canonical example from Doom 2 when passing Map 21. The player takes a completely natural position right in front of the diagonal screen that closes the gap. At the next tick, the engine conducts a test to determine whether it is possible to teleport the player to a position immediately * behind * the diagonal screen. With a careful choice of direction, you can designate a position that will not contradict the conditions of the "teleport" and the engine will transfer the player to the desired point without any problems.
Squeeze glide
trick at 0:25
Also in the arsenal there is another, even more common trick, which is associated with the reception of “bar glide”, because it is also based on the movement between the screeners located at a distance of 32 units. For me, the term “squeeze glide” (gliding with “squeezing”) seems more adequate for memorization and less confusing.
For squeeze glide, the player should perfectly align with the gap, the same size as the character (32 units). Then, after a series of unsuccessful attempts, lasting, it seems, for ages, he finally manages to squeeze into this gap!
In theory, “squeeze glide” should be quite simple and straightforward: the player has a width of 32 units (along the axes). And that means if you find a space that is clearly aligned along the axes and with a width of 32 units, you should be able to go through it. But with the Doom engine, it is rarely that simple.
The main problem is that the movement in the Doom engine is quantized and, moreover, it is not fully quantized. I will not go into details and tell how the player’s motion vector was calculated. But in short, the vector uses sines and cosines to combine the player’s direction with the motion vectors to compare with the final X- and Y-vectors of the driving force. For example, when a player pushes a key forward and heads north, the X-coordinate of the motion vector should be a value multiplied by cosine 90, which is necessary for zeroing. Unfortunately, Doom is not good at preserving angles and cosines, it uses calculation tables of values and, as it turned out, the sine / cosine table does not actually include 0 as a value (the closest ± 0.0002).
Thus, even with a maximum approach to the north, a value appears that is still too small for a step to the east or west.
So, knowing how SPT works for players, you can see what happens:
- The player is trying to move in space directly between the obstacles
- The engine uses an SPT having a certain quantized elongation coefficient, and determines the possibility of moving to a particular position
- Since the gap has the same width as the player, the latter must EXACTLY correspond to the space traveled (inaccurate angle values make the task really difficult). This means that for a successful passage you need to be located to the west of the place between the obstacles with perfect accuracy of 0.0002 units
Understanding how to make squeeze glide work smoothly is not a science, but a real art. Speedrunners study hour after hour the intricacies of movement in order to complete it in a reasonable amount of time.
Line skipping (south / west)
19:06 trick
Understanding how the engine uses SPT players to test a new position will only bring us a little closer to understanding line skip. It may seem that the player does the impossible when he performs a line skip: he runs directly across the border line without actually activating it.
To understand how this works, you need to look at the order of events in the engine:
- It uses the player’s SPT to test it in a potentially new position.
- As part of the process, the engine makes a list of any overlays for a potentially new line item
- If possible, move them to the position in question.
- Draws a connecting line between the centers of the player’s old and new positions, and then checks each border in the already compiled list to see if any of them crosses the connection line
- If it crosses, it checks these lines for special actions with their further activation
Thus, as you can see, there are two possibilities for crossing a special border line: 1) touching the border line at the point of the updated position, and 2) the border is crossed by the line connecting the old and updated positions.
So, the algorithm is given. How can you get around it? Something like that.
Tick 1: SPT players seek to move them to a point where their center practically, but still not quite, crosses the border.
Tick 1: the engine determines that this new point touches the border and adds it to the list.
Tick 1: after successful movement, the engine throws the intersection line, but it does not cross the border, so it doesn’t matter
Tick 2: SPT players move them far enough that they move completely * behind * the border line and do not touch it anymore
Tick 2: the special border line is not even in the newly compiled list of crossed borders, as a result of which it cannot be activated.
So you see that while moving faster than half the player’s width per tick (having a good location and a bit of luck), there is nothing improbable in slipping through the border line without activating its special actions. However, remember that the player’s bounding box is always aligned with the coordinate axes. In other words, this technique is easier to perform along the axes, where the “radius” of the player is 16 units. However, even on a diagonal of 45 degrees, where the “radius” of the player is 22.6 units, the SR50 strafe run with its 23+ units per movement is still feasible.
I want to draw your attention to the fact that the above describes only the movement to the “south / west”. For reasons that we have not yet discussed, this technique WILL NOT WORK when moving north or east.
Item bumping
0:16 trick
Here's another absurdity due to a strange and bizarre Doom test of a potentially new player position. The algorithm is arranged as follows:
- Used by player’s SPT to determine a potential new position
- It is checked if there are any obstacles in the landing zone in order to occupy this point.
- At the same time, a check is carried out for the presence of any other things that overlap the landing zone
- And also, if one of these things can be reached, the player selects them
Do you see the problem? The player will pick up items relating to the potential landing area of the SPT, even if the move ultimately does not occur. This means that if you rush at full speed to an impassable border with an object located directly on the other side of it, the engine (at the moment of collision with the border) will attempt to move the player (SPT) to the other side of the wall. This will give you the opportunity to pick up any things that come across at the site of a potential landing.
Monsters opening doors
trick at 0:09
Despite the fact that this paragraph does not apply to the direct movement of the player, he is nevertheless notable and is largely guided by the same principles. For the most part, the engine considers the movement of the monster identical to the movement of the player. In other words, it monitors the monster’s SPT, and then uses this SPT to test the potential landing zone for the monster’s further movement.
In this case, the reception is triggered if the door was created in a way where one side, for example, is locked with a key, and the other side is a “normal” door. While a fast monster (like archvile) is walking near the door, its huge SPT indicates the engine’s attempts to place this monster at a considerable distance from the open side of the door. And so the monster is able to open it.