17. Movement automation

In this chapter we will discuss a few algorithms or implementations of movement automation in a typical TAS tool.

17.1. Vectorial compensation

In Strafing, we discussed various ways to “strafe” with differing objectives, most commonly maximum-acceleration strafing and speed-preserving strafing. In each of these methods, we must derive a formula or, at least, an implicit equation for the angle between and to realise the desired strafing objective. Unfortunately, Half-Life does not allow us to realise the angles to a very high precision. This is because Half-life uses the DELTA mechanism (see DELTA) to transmit information across the network from client to server and vice versa. Looking at the default delta.lst included in vanilla Half-Life, we see the following line defined under usercmd_t:

DEFINE_DELTA( viewangles[1], DT_ANGLE, 16, 1.0 ),

This shows that the yaw angle is somehow lossily compressed to 16 bits. This means that, to transmit some angle in degrees, it is first converted at the client side to the 16-bit integer representing

where is the integer part of some real number . When the server receives this integer, it is then converted back to the floating point number

This expression looks familiar! Indeed, this entire operation is equivalent to the anglemod function, first described in Anglemod. Given our understanding of anglemod, we know that there are only exactly 65536 possible angles. Although this is already very precise, in the sense that any angle can be realised with only about 0.0015% absolute error, it is possible to do better by controlling the yaw angle in combination with and .

By controlling and , we can change the direction of the unit acceleration vector (see Air and ground movements) without changing the yaw angle. To see why, recall that , and even keeping and constant, we can change the “weights” and to make the vector sum point to any desired direction, and therefore realise any angle between and . Unfortunately, again, looking at the file delta.lst, we see the following lines:

DEFINE_DELTA( forwardmove, DT_SIGNED | DT_FLOAT, 12, 1.0 ),
...
DEFINE_DELTA( sidemove, DT_SIGNED | DT_FLOAT, 12, 1.0 ),
DEFINE_DELTA( upmove, DT_SIGNED | DT_FLOAT, 12, 1.0 ),

Here, the 12 indicates that the client side , , and (see Forwardmove, sidemove, and upmove for their definitions) will be truncated to 12 bits and integer precision. Since , and a signed integer transmitted across the network is not represented in two’s complement, each of these values will be clamped to .

Nevertheless, despite each of , , and being truncated, we can still combine them to obtain a more accurate angle realisation method than possible using only the yaw or the FSU.

17.1.1. Unconstrained compensation

Suppose we have computed the desired angle between the velocity and the ideal unit acceleration vector . To “realise” this angle is to strafe such that the ideal unit acceleration is attained by changing the , , and . However, due to the slight imprecision in each of these values, the ideal can never be attained exactly. Instead, we compute the “best” approximation to it, which may be written as

where is the two dimensional unit forward vector (see View vectors), and is the rotation matrix. We may then define the “best” approximation such that the angle between and is minimised. In the ideal case, the angle between the two vectors is zero, meaning the desired unit acceleration vector is attained exactly. However, in practice, there will be a small difference in angle such that

Writing out the dot product and simplifying, we obtain

where

Now, to minimise the angle is to maximise , and therefore maximising . We may compute the maximum point of [1] by solving

yielding

Note that for some integer . Inverting the tangent function and computing the remainder when divided by (i.e. modulo ),

Notice that the yaw is gone, and so is the integer yaw . This is because the yaw is always divisible by , and therefore its remainder is always zero. To slightly simplify implementation, write

That is, if this equality is satisfied, then the (and an appropriate ) will maximise , achieving the best approximation. In practice, however, this equality is rarely satisfied, due to the imprecision in and mentioned previously. Denote

(17.1)

Then, we want to find a that is the closest to , subject to the constraints that and have. One way to do this is to brute force every possible combinations of and and computing the corresponding values. However, this is very inefficient and can take millions of iterations. Doing it once on a fast computer may not consume a noticeable amount of time, but when implemented in game, these computations need to be done every frame, and there could be thousands of frames per second.

A better approach is to build the vectorial compensation table (VCT). The details in how to compute such a table will be described in VCT generation. But here, we will assume that it contains 3-tuples , sorted by , where is computed using (17.1) using the corresponding and . To find the closest to , we may use binary search to find entries corresponding to and such that [2]

Then, the value that is closest to would simply be one of and . This algorithm is very fast because even if the VCT contains millions of entries, it takes at most about 20 iterations to find the two entries. The downside is that there will be a small but noticeable delay in generating the VCT.

As a side note, an alternative way to compute exists. In practice, computing may be slightly less efficient, because obtaining requires computing the rotation matrix , which in turn requires computing and along with multiple addition and multiplication operations. An alternative method involves observing that and , where

Therefore,

for some integer . This implies that

as divides , and so the integer disappears, simplifying the expression. This method of computing requires only one trigonometric computation, namely in obtaining .

Footnotes

[1]

To verify that this is a maximum point, compute the second derivative and substituting,

which is always negative.

[2]A caveat is that when, for instance, is already the largest value in the VCT, therefore no exists. In this case, may be chosen to be zero, and appropriate and would need to be found separately. Vice versa for when is already the smallest value in the VCT.

17.1.2. VCT generation

The algorithm described in previous sections rely on a lookup table called the vectorial compensation table (VCT). As a reminder, this is a table containing entries of 3-tuple sorted by , and that each entry must have a unique and must satisfy .

If we simply enumerate and by drawing each element from , then the resulting will not be unique. So see why, suppose , , and . Then, obviously and , but and therefore .

To obtain a set of unique , we must therefore enumerate all unique coprime pairs , but satisfying the constraint that and . The most efficient way to enumerate this is by generating a Farey sequence. To reduce the generation time, we can exploit symmetries in .

Firstly, we can restrict generation in just one quadrant, namely by considering only positive and . This is because for all and , we know that

for some integer . Computing the ,

Obviously , therefore this simplifies to

This implies that the s computed from and are the same.

Within a quadrant, we only need to consider in . In other words, we only need to generate values within an octant. To see this, define sets

Then we claim that , and therefore only one of them needs to be computed. Consider in the domain of . Then clearly , which is the domain of . Compute the corresponding , we have

This implies that . Similarly, consider in the domain of , then is in the domain of . It can be similarly shown that the s computed using and are the same. This shows , and we conclude that .

One observation may be made regarding the relationship between different elements in the -table. Define sets

Consider some . Then, we have

Computing ,

Let such that . Let integers and for some , where . Namely, is the completely reduced fraction of . Then if is satisfied, we have . In addition, we also have

Namely, if is not an integer.

17.2. Line strafing

17.3. Automatic actions