# 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

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.