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
DEFINE_DELTA( viewangles, 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 ),
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
Now, to minimise the angle is to maximise , and therefore maximising . We may compute the maximum point of 1 by solving
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
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 .
To verify that this is a maximum point, compute the second derivative and substituting,
which is always negative.
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
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.