1. Game fundamentals

This page describes the notations that we will use throughout this documentation. We will also introduce some basic concepts that will be used and assumed in all our discussions.

1.1. Tracing

Tracing is one of the most important computations done by the game. Tracing is done countless times per frame, and it is vital to how entities interact with one another.

Note

expansion needed

1.2. Randomness

The Half-Life universe is full of uncertainties, much like our universe at the level of quantum mechanics. Randomness in Half-Life is sourced in two ways: by means of the shared RNG and the non-shared RNG. These are custom written pseudo-RNGs that are powered by vastly different algorithms. The shared RNG is so named because it is computed by the game server and shared with the game clients, while the non-shared RNG is computed independently by the game server and clients without any kind of sharing or synchronisation between them.

1.2.1. Shared RNG

The shared RNG code is open source and written in dlls/util.cpp in the Half-Life SDK. The shared RNG barely qualifies as an RNG given how it is used, and especially due to the fact that, given a fixed interval $[l,h)$, the RNG only returns 253 possible values within the bounds, as we will explain below. The only uses of the shared RNG in Half-Life are related to weapon behaviours and bullet spreads (see Bullet spread).

For some context, a typical pseudo-RNG must be seeded prior to use, for a pseudo-RNG needs to have its initial state defined. To put it differently, let $S_0$ be the initial state of a typical pseudo-RNG. To use this RNG, we must first call a seeding function $S_0\leftarrow \mathrm{Seed}\left(s\right)$ with some value $s$, which is often just the current unix timestamp. Then, the next pseudorandom number is given by $x_0$ where $(S_1,x_0)\leftarrow f\left(S_0\right)$. In general, the $i$-th pseudorandom number is given by $(S_{i+1},x_i)\leftarrow f\left(S_i\right)$.

However, the Half-Life shared RNG is used differently. A “seed” in this context refers to an integer that appears to increment sequentially every frame. This integer is stored as the class variable CBasePlayer::random_seed. This variable is set in CmdStart to the value of its random_seed parameter:

Listing 1.1 CmdStart, dlls/client.cpp

void CmdStart( const edict_t *player, const struct usercmd_s *cmd, unsigned int random_seed )
{
  entvars_t *pev = (entvars_t *)&player->v;
  CBasePlayer *pl = dynamic_cast< CBasePlayer *>( CBasePlayer::Instance( pev ) );

  [...omitted...]

  pl->random_seed = random_seed;
}

SV_RunCmd in the engine code supplies the value of the seed to CmdStart. The ultimate source of the seed value appears to be dependent on the latest incoming sequence number of the client-server channel. This part of the code is not open source, and therefore not well researched. Nonetheless, empirical and field evidence shows that the seed value obtained in CmdStart appears to be sequential from frame to frame, or at least, increments in a very predictable way.

The shared RNG may be denoted as $U_S(\sigma ,l,h)$, where $\sigma$ is an integer, while $l$ and $h$ are floating point numbers representing the lower and upper bounds of the output, forcing the function to give a value within $[l,h)$. The current shared seed value is typically given for $\sigma$, although there are exceptions, such as in the computation of bullet spreads as explained in Bullet spread. In the SDK code, $U_S$ is simply UTIL_SharedRandomFloat. 1

The most important aspect of the shared RNG is that it returns only 253 possible values for a given interval $[l,h)$. The reader is encouraged to read the SDK code for the implementation details. For a higher level overview here, when UTIL_SharedRandomFloat is called, it always initialises a global glSeed to one of the 256 possible values according to a 256-element lookup table. The previous value of glSeed prior to calling this function is completely discarded as a result. The index to the lookup table is computed by taking the lower 8-bits of the sum of the arguments of UTIL_SharedRandomFloat reinterpreted as 32-bit signed integers. What follows are computations involving glSeed and scaling of the output according to the bounds. Notice that because there are only 256 possible initial states, followed by deterministic and pure computations, there can only have a maximum of 256 possible output values. In reality, it is slightly worse than that: we counted the number of unique output values from $U_S$ (given fixed $l$ and $h$), and there are only 253 of them. It is therefore quite a stretch to describe the outputs of the shared RNG as “random”.

1.2.2. Non-shared RNG

The code for the non-shared RNG is not officially publicly available. Nevertheless, we do not need to resort to reverse engineering as the C++ code for the non-shared RNG is available in the Xash3D engine code, the ReHLDS project, and the leaked Half-Life 2 source code, all of which look almost identical. The non-shared RNG is considerably more complex than the shared RNG. The non-shared RNG is used much more in Half-Life than the shared RNG. Examples of the uses of the non-shared RNG include the randomisation of the player’s explosion target position, grenade tumbling velocities, delays between entity “thinks”, NPC talking sequences and general behaviours, the pitches of sounds, cosmetics and effects, and much more.

Given the complexity of the non-shared RNG algorithm, we will not attempt to describe how it works here. We can say that it appears to be seeded based on the current unix timestamp. This meant that, in principle, we can change the system clock and restart Half-Life to alter the random behaviours and phenomena in the game. There are two functions exposed to the users to obtain the next random value: the integer version $U_{NS}(S,l,h)$ and the floating point version $U_{NS}(S,l,h)$. Both of these rely on some global state $S$.

1.3. Frame rate

When we think of the concept of frame rate, or sometimes somewhat incorrectly referred to by its unit of measurement frames per second or fps, we think of the refresh rate of the screen when playing Half-Life. However, it is crucial to distinguish between three different types of frame rate:

rendering frame rate

This is the real-time rate at which graphics are painted on the screen, denoted as $f_r={\tau }_r^{-1}$. This definition maps to what is normally thought of as the frame rate. The rendering frame rate is usually limited by fps_max in normal gameplay, though if host_framerate is set, then fps_max is ignored. Other factors can also limit the maximum frame rate, including, but not limited to, the “vertical sync” setting (in-game or otherwise) and fps_override.

game frame rate

This is the virtual rate at which the majority (with player movement being the important exception) of the game physics are run, denoted as $f_g={\tau }_g^{-1}$. The game frame rate is typically in sync with the rendering frame rate, though not always. For example, suppose a computer is not able to render the graphics beyond a rendering frame rate of 500 fps, but host_framerate is set to 0.001. This forces the physics to run at a virtual 1000 fps, though because the screen does not update that frequently, the game appears to run twice as slow in real time.

player frame rate

The player frame rate is the virtual frame rate at which the majority of the player movement physics (see Player movement basics) are run, denoted as $f_p={\tau }_p^{-1}$. The player frame rate roughly corresponds to the game frame rate. Depending on the engine version, whether the game is paused, and the value of the game frame rate itself, the player frame time ${\tau }_p$ may oscillate between different values, stay at zero, or be rounded towards zero to the nearest 0.001.

1.3.1. Slowdown on older engines

Suppose the game frame rate is higher than 20 fps. On older game engines, roughly before build 6027, the player frame rate equals the game frame rate rounded towards zero to the nearest 0.001, as mentioned above. Namely, we have

$${\tau }_p=\frac{\lfloor 1000{\tau }_g\rfloor }{1000}$$

The slowdown factor is then defined as

(1.1)$$\eta =\frac{{\tau }_p}{{\tau }_g}=\frac{\lfloor 1000{\tau }_g\rfloor }{1000{\tau }_g}=\frac{f_g}{1000}\lfloor \frac{1000}{f_g}\rfloor =\frac{f_g}{f_p}$$

When the slowdown factor is less than one, the actual movement speed of the player will be lower. The player’s position update described in Position update uses ${\tau }_p$ but runs at the rate of ${\tau }_g^{-1}$ Hz. Indeed, the real velocity of the player is directly proportional to $\eta$:

$$\frac{r^{\prime }-r}{{\tau }_g}=\frac{r+{\tau }_p{v}^{\prime }-r}{{\tau }_g}=\frac{{\tau }_p}{{\tau }_g}{v}^{\prime }=\eta v^{\prime }$$

For instance, a trick known as the “501 fps slowdown” was implemented in Half-Life 21 (see Half-Life 21 (2014) by quadrazid et al.) to permit opening and passing through doors in the Questionable Ethics chapter without stopping dead by the doors before they could be opened fully. The slowdown factor at 501 fps is $\eta =0.501$, implying the real velocity is roughly half the intended player velocity. On pre-Steam versions of Half-Life and its expansions, the default frame rate is 72 fps (and some speedrunners believe it should not be exceeded), which would give a slowdown factor of $\eta =117/125=0.936$.

It is a well known fact that the slowdown factor $\eta =1$ if and only if $1000/f_g$ is an integer. This is because as seen in (1.1), if $\eta =1$ we must have

$$\lfloor \frac{1000}{f_g}\rfloor =\frac{1000}{f_g}$$

which is only possible if $1000/f_g$ is an integer.

1.4. Savestates

1.5. DELTA

The DELTA mechanism is one of the ways Half-Life uses to save bandwidth in client-server communication.

TODO

1.6. Walking through a frame

This section attempts to outline some of the major events relevant to speedrunning that happen in a frame. Extreme detail on how each part of the game engine works is beyond the scope of this documentation. In fact, some believe that code is documentation! Until Valve releases the source code of Half-Life, one can study the Xash3D engine source or the disassembly of Half-Life.

Footnotes

1

We omit any mention of the integer version of the shared RNG, UTIL_SharedRandomLong, because no code is calling this function in the SDK. It also behaves very similarly to the floating point version with only minor differences.