10. Movement automation

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

10.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 $\theta$ between $v$ and $\hat{a}$ 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 $a$ in degrees, it is first converted at the client side to the 16-bit integer representing

$$\mathrm{int}\left(\frac{65536}{360}a\right)=\mathrm{int}\left(\frac{a}{u_d}\right)$$

where $\mathrm{int}\left(x\right)$ is the integer part of some real number $x$. When the server receives this integer, it is then converted back to the floating point number

$$\frac{360}{65536}\left(\mathrm{int}\left(\frac{65536}{360}a\right)AND65535\right)$$

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 $\vartheta$ in combination with $F$ and $S$.

By controlling $F$ and $S$, we can change the direction of the unit acceleration vector $\hat{a}$ (see Air and ground movements) without changing the yaw angle. To see why, recall that $a=F\hat{f}+S\hat{s}$, and even keeping $\hat{f}$ and $\hat{s}$ constant, we can change the “weights” $F$ and $S$ to make the vector sum point to any desired direction, and therefore realise any angle $\theta$ between $v$ and $\hat{a}$. 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 $\tilde{F}$, $\tilde{S}$, and $\tilde{U}$ (see Forwardmove, sidemove, and upmove for their definitions) will be truncated to 12 bits and integer precision. Since $2^{12}=4096$, and a signed integer transmitted across the network is not represented in two’s complement, each of these values will be clamped to $[-2047,2047]$.

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

10.1.1. Unconstrained compensation

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

$$\tilde{\hat{a}}=\hat{f}R\left(\theta \right)$$

where $\hat{f}$ is the two dimensional unit forward vector (see View vectors), and $R\left(\theta \right)$ is the rotation matrix. We may then define the “best” approximation such that the angle between $\hat{a}$ and $\tilde{\hat{a}}$ 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

$$\Pi =\hat{a}\cdot \tilde{\hat{a}}=\cos ϵ$$

Writing out the dot product and simplifying, we obtain

$$\Pi =a_x\cos (\vartheta +\xi )+a_y\sin (\vartheta +\xi )$$

where

$$\xi =\mathrm{atan2}(S,F)$$

Now, to minimise the angle $ϵ$ is to maximise $\cos ϵ$, and therefore maximising $\Pi$. We may compute the maximum point of $\Pi$ 1 by solving

$$\frac{d\Pi }{d(\vartheta +\xi )}=-a_x\sin (\vartheta +\xi )+a_y\cos (\vartheta +\xi )=0$$

yielding

$$\tan (\vartheta +\xi )=\frac{a_y}{a_x}$$

Note that $\vartheta =uY$ for some integer $Y\in [0,65535]$. Inverting the tangent function and computing the remainder when divided by $u$ (i.e. modulo $u$),

$$\xi -\lfloor \frac{\xi }{u}\rfloor u=\mathrm{atan2}(a_y,a_x)-\lfloor \frac{1}{u}\mathrm{atan2}(a_y,a_x)\rfloor u$$

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

$$\frac{\xi }{u}-\lfloor \frac{\xi }{u}\rfloor =\frac{1}{u}\mathrm{atan2}(a_y,a_x)-\lfloor \frac{1}{u}\mathrm{atan2}(a_y,a_x)\rfloor$$

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

(10.1)$$\tilde{\Phi }=\frac{\xi }{u}-\lfloor \frac{\xi }{u}\rfloor \Phi =\frac{1}{u}\mathrm{atan2}(a_y,a_x)-\lfloor \frac{1}{u}\mathrm{atan2}(a_y,a_x)\rfloor$$

Then, we want to find a $\tilde{\Phi }$ that is the closest to $\Phi$, subject to the constraints that $S$ and $F$ have. One way to do this is to brute force every possible combinations of $S$ and $F$ and computing the corresponding $\tilde{\Phi }$ 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 $(\tilde{\Phi },F,S)$, sorted by $\tilde{\Phi }$, where $\tilde{\Phi }$ is computed using (10.1) using the corresponding $S$ and $F$. To find the closest $\tilde{\Phi }$ to $\Phi$, we may use binary search to find entries corresponding to ${\tilde{\Phi }}_1$ and ${\tilde{\Phi }}_2$ such that 2

$${\tilde{\Phi }}_1\le \Phi \le {\tilde{\Phi }}_2$$

Then, the value that is closest to $\Phi$ would simply be one of ${\tilde{\Phi }}_1$ and ${\tilde{\Phi }}_2$. 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 $\tilde{\Phi }$ 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 $\Phi$ exists. In practice, computing $\mathrm{atan2}(a_y,a_x)$ may be slightly less efficient, because obtaining $\hat{a}$ requires computing the rotation matrix $R\left(\theta \right)$, which in turn requires computing $\sin$ and $\cos$ along with multiple addition and multiplication operations. An alternative method involves observing that $a_x=\cos (\beta +\theta )$ and $a_y=\sin (\beta +\theta )$, where

$$\beta =\mathrm{atan2}(v_y,v_x)$$

Therefore,

$$\mathrm{atan2}(a_y,a_x)=\beta +\theta +k\pi$$

for some integer $k$. This implies that

$$\Phi =\frac{\beta +\theta +k\pi }{u}-\lfloor \frac{\beta +\theta +k\pi }{u}\rfloor =\frac{\beta +\theta }{u}-\lfloor \frac{\beta +\theta }{u}\rfloor$$

as $u$ divides $k\pi$, and so the integer disappears, simplifying the expression. This method of computing $\Phi$ requires only one trigonometric computation, namely in obtaining $\beta$.

Footnotes

1

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

$$\frac{d^2\Pi }{d(\vartheta +\xi {)}^2}=-a_x\cos (\vartheta +\xi )-a_y\sin (\vartheta +\xi )=-(\frac{a_x^2}{\sqrt{a_x^2+a_y^2}}+\frac{a_y^2}{\sqrt{a_x^2+a_y^2}})$$

which is always negative.

2

A caveat is that when, for instance, ${\tilde{\Phi }}_1$ is already the largest $\tilde{\Phi }$ value in the VCT, therefore no ${\tilde{\Phi }}_2>{\tilde{\Phi }}_1$ exists. In this case, ${\tilde{\Phi }}_2$ may be chosen to be zero, and appropriate $\xi$ and $\vartheta$ would need to be found separately. Vice versa for when ${\tilde{\Phi }}_2$ is already the smallest value in the VCT.

10.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 $(\tilde{\Phi },F,S)$ sorted by $\tilde{\Phi }$, and that each entry must have a unique $Y$ and must satisfy $F^2+S^2\ge M_m^2$.

If we simply enumerate $F$ and $S$ by drawing each element from $[-2047,2047]$, then the resulting $\tilde{\Phi }$ will not be unique. So see why, suppose $M_m=320$, $(F_1,S_1)=(400,800)$, and $(F_2,S_2)=(800,1600)$. Then, obviously $F_1^2+S_1^2>M_m^2$ and $F_2^2+S_2^2>M_m^2$, but ${\xi }_1={\xi }_2$ and therefore ${\tilde{\Phi }}_1=\widetilde{{\Phi }_2}$.

To obtain a set of unique $\tilde{\Phi }$, we must therefore enumerate all unique coprime pairs $(F,S)$, but satisfying the constraint that $-2047\le F,S\le 2047$ and $F^2+S^2\ge M_m^2$. The most efficient way to enumerate this is by generating a Farey sequence. To reduce the generation time, we can exploit symmetries in $(F,S)$.

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

$$\xi =\mathrm{atan2}(S,F)=\mathrm{atan2}\left(\right|S|,|F\left|\right)+\frac{\pi }{2}k$$

for some integer $k$. Computing the $\tilde{\Phi }$,

$$\tilde{\Phi }=\frac{\xi }{u}-\lfloor \frac{\xi }{u}\rfloor =\frac{\mathrm{atan2}\left(\right|S|,|F\left|\right)}{u}+16384k-\lfloor \frac{\mathrm{atan2}\left(\right|S|,|F\left|\right)}{u}+16384k\rfloor$$

Obviously $16384k\in Z$, therefore this simplifies to

$$\frac{\mathrm{atan2}\left(\right|S|,|F\left|\right)}{u}-\lfloor \frac{\mathrm{atan2}\left(\right|S|,|F\left|\right)}{u}\rfloor =\frac{\mathrm{atan2}(S,F)}{u}-\lfloor \frac{\mathrm{atan2}(S,F)}{u}\rfloor$$

This implies that the $\tilde{\Phi }$s computed from $(F,S)$ and $\left(\right|F|,|S\left|\right)$ are the same.

Within a quadrant, we only need to consider $\xi$ in $[0,\pi /4)$. In other words, we only need to generate values within an octant. To see this, define sets

$$U=\left\{\tilde{\Phi }\right(\xi \left)\right|0\le \xi <\frac{\pi }{4}\}V=\left\{\tilde{\Phi }\right(\xi \left)\right|\frac{\pi }{4}\le \xi <\frac{\pi }{2}\}$$

Then we claim that $U=V$, and therefore only one of them needs to be computed. Consider $\xi \in [0,\pi /4)$ in the domain of $U$. Then clearly $\xi +\pi /4\in [\pi /4,\pi /2)$, which is the domain of $V$. Compute the corresponding $\tilde{\Phi }$, we have

$$\frac{\xi }{u}+8192-\lfloor \frac{\xi }{u}+8192\rfloor =\frac{\xi }{u}-\lfloor \frac{\xi }{u}\rfloor$$

This implies that $U\subseteq V$. Similarly, consider ${\xi }^{\prime }\in [\pi /4,\pi /2)$ in the domain of $V$, then ${\xi }^{\prime }-\pi /4\in [0,\pi /4)$ is in the domain of $U$. It can be similarly shown that the $\tilde{\Phi }$s computed using ${\xi }^{\prime }$ and ${\xi }^{\prime }-\pi /4$ are the same. This shows $V\subseteq U$, and we conclude that $U=V$.

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

$$P=\left\{\tilde{\Phi }\right(\xi \left)\right|0\le \xi <\frac{\pi }{8}\}Q=\left\{\tilde{\Phi }\right(\xi \left)\right|\frac{\pi }{8}\le \xi <\frac{\pi }{4}\}$$

Consider some $0\le \xi <\pi /8$. Then, we have

$$\tan (\frac{\pi }{4}-\arctan \frac{S}{F})=\frac{1-S/F}{1+S/F}=\frac{F-S}{F+S}$$

Computing $\arctan$,

$$\frac{\pi }{4}-\xi =\frac{\pi }{4}-\arctan \frac{S}{F}=\arctan \frac{F-S}{F+S}=\arctan \frac{S^{\prime }}{F^{\prime }}={\xi }^{\prime }$$

Let $\xi$ such that $\tilde{\Phi }\left(\xi \right)\in P$. Let integers $kp=k{S}^{\prime }$ and $kq=F^{\prime }$ for some $k$, where $gcd(p,q)=1$. Namely, $p/q$ is the completely reduced fraction of $S^{\prime }/F^{\prime }$. Then if $q\le 2047$ is satisfied, we have $\tilde{\Phi }\left({\xi }^{\prime }\right)\in Q$. In addition, we also have

$$\tilde{\Phi }\left({\xi }^{\prime }\right)=\frac{{\xi }^{\prime }}{u}-\lfloor \frac{{\xi }^{\prime }}{u}\rfloor =\lceil \frac{\xi }{u}\rceil -\frac{\xi }{u}$$

Namely, $\tilde{\Phi }\left(\xi \right)+\tilde{\Phi }\left({\xi }^{\prime }\right)=1$ if $\xi /u$ is not an integer.

10.2. Line strafing

10.3. Automatic actions