Half-life game-engine model for move

Introduction

The following simplified model has been build from the Half-life 1 SDK source code. It is meant to study opportunities for bot 2D-move control. Definitions & notations are in "Bot navigation".

Model pseudo-code

This is derived from bot move code for a bot on ground and not in water.
AccelCoeff= sv_accelerate, Friction= sv_friction, Stopspeed= sv_stopspeed are Half-life cvars; the values currently used here are respectively 5, 4, 75.
mVel_n-1= modulus(vVel_n-1);/*modulus of velocity*/
if( mVel_n-1 > 0)
{
mVelTmp= max( 0.0f, mVel_n-1- T* Friction* max( mVel_n-1, Stopspeed)); /* ie a proportional decrease if mVel_n-1 > Stopspeed, and a constant deceleration=Friction* Stopspeed (= 300) below */
vVelTmp= vVel_n-1* mVelTmp/ mVel_n-1;/* ie velocity is reduced along the velocity direction */
}
if( UE_mVel!=0)/*modulus of wished velocity*/
{
VelProj= vVelTmp • UE_uvVel /* ie projection of new velocity on wished speed direction; VelProj can be negative*/
DeltaVel= UE_mVel- VelProj;/* with UE_mVel ≥ 0 */
DeltaVelMax= AccelCoeff * UE_mVel; /* ie acceleration bound is proportional to the wished velocity */
DeltaVel= minmax( DeltaVel, -DeltaVelMax, DeltaVelMax);
vVel_n= vVelTmp+ DeltaVel* UE_uvVel;/* ie speed increase is along the wished direction*/
}
else
{
vVel_n= vVelTmp; }
M_n= M_n-1+ T * vVel_n;/* ie integration uses the updated velocity */
From this, we can extract some characteristics as follows.

Stopping Distance

On a stop command, ie the player releasing the speed button or the bot setting UE_mVel to zero; Assuming a constant Timestep T, straight move and computing distance as distance_n= distance_n-1+ T* Vel_n like the engine does, one can "integrate" velocity piece-wise; this gives a formula for stopping distance as a function of the initial velocity modulus mVel_Initial and Timestep T.

float getStopDistDetailed( float mVel_Initial, float T/*timestep*/)
{
float NumStopSpeed= mVel_Initial;
float StopDist=0.0f;
if( mVel_Initial> StopSpeed)
{
float K= 1.0f- Friction* T;
//_ exponential speed decay portion
float z= log( StopSpeed/mVel_Initial)/log( K);
z= ceil(z);
int N1= (int)z;
NumStopSpeed*= (float)pow(K,N1); // last reached speed value above Stopspeed
StopDist= ( mVel_Initial- NumStopSpeed)* (1.0f/Friction- T);
}
//_ constant speed decay portion
float z= NumStopSpeed/(Friction*StopSpeed*T);
int N2= (int)z; // corresponding to last reached speed value above zero
if( N2> 0) StopDist+= N2* T* ( NumStopSpeed- 0.5f* T* (1.0f+ N2)* Friction* StopSpeed);
return StopDist;
}

This piece of code correspond to exact computation; in particular, the curve of StopDist as a function of mVel_Initial is a bit "jumpy", due to quantization for N1 and N2. For practical purpose, a far simpler computation which returns a very good match and is continuous ( ie one can compute the reciprocal function) is the following:

float getStopDist( float mVel_Initial, float T/*timestep*/)
{
if( mVel_Initial> StopSpeed) return (mVel_Initial- 0.5* StopSpeed)* (1.0f/ Friction- T);
else return max(0, 0.5f* mVel_Initial*( mVel_Initial/(StopSpeed* Friction)-T));
}

StopDistDetailed() returns a value applying when a moving bot/player sets the speed to zero.
Another faster way to stop - referred to as "emergency stop" herunder- is for a player to depress the "backwards" button ie commanding a velocity in a direction opposite to the current velocity ; it should ideally be depressed until speed is zero then released to avoid moving back; players obviously cannot do it and depress a little bit before, or a bit after when they can see that a backwards move is initiated. This can also be done for a bot, with the advantage that it can be more accurate.
emergStopDist() returns the distance at which actual speed changes sign, ie the max distance value reached before starting to move the opposite way.

float getEmergStopDistDetailed( float mVel_Initial, float OppositeVelCmd, float T/*timestep*/)// OppositeVelCmd must be negative
{
float NumStopSpeed= mVel_Initial;
float StopDist= 0.0f;
float Decel= Friction* StopSpeed- AccelCoeff* OppositeVelCmd;
if( mVel_Initial> StopSpeed)
{
float Coeff;
float K= 1.0f- Friction* T;

float EquivSpeed= OppositeVelCmd* AccelCoeff/ Friction;
float Ratio= (StopSpeed- EquivSpeed)/(mVel_Initial- EquivSpeed);
float N1=log(Ratio)/log(K);
N1= ceil( N1);
N1= (int)N1;
Coeff= pow(K, N1);
NumStopSpeed= Coeff*(mVel_Initial- EquivSpeed)+EquivSpeed;
StopDist= ( mVel_Initial- NumStopSpeed)* (1/ Friction- T);
StopDist+= N1* T* EquivSpeed;
}
int N2= (int)(NumStopSpeed/(Decel*T));
if( N2>0) StopDist+= N2*T*(NumStopSpeed- 0.5*T*(1+ N2)*Decel);
return max(0,StopDist);
}

Approximate, but continuous version:

float getEmergStopDist( float mVel_Initial, float OppositeVelCmd, float T/*timestep*/)// OppositeVelCmd must be negative
{
float Decel= Friction* StopSpeed- AccelCoeff* OppositeVelCmd;
float StopDist;
if( mVel_Initial> StopSpeed)
{
StopDist= ( mVel_Initial- StopSpeed)* (1/ Friction- T);

float K= 1.0f- Friction* T;
float EquivSpeed= OppositeVelCmd* AccelCoeff/ Friction;
float Ratio= (StopSpeed- EquivSpeed)/(mVel_Initial- EquivSpeed);
float N1= log(Ratio)/log(K);
StopDist+= N1* T* EquivSpeed;

StopDist+= 0.5f* StopSpeed*( -T+ StopSpeed/ Decel);
}
else StopDist= 0.5f* mVel_Initial*( -T+ mVel_Initial/ Decel);
return max( 0, StopDist);
}

The largest discrepancy between the last 2 functions is for T=0.2 seconds, where the error is less than 1.5 "unit"( the bot is 32 "units" wide). Comparing the 2 "continuous" simpler functions with tests on the real game-engine for T= constant= 0.014 shows very good match( less than 2% error).
One should not forget though that a point cannot be targetted with an accuracy better than T*speed.

Turns

On a step change in wished velocity direction from an initial straight move, the bot ends up moving on a line that crosses its initial trajectory at a distance depending only on the initial velocity modulus :
dist = (-T+ 1/friction)*mVel (= (-T+ 0.25)*mVel).

Assuming the next line is a given, this gives an easy way to predict when and how to turn so as to move close to the next line ( as a nav-path segment) , or to avoid crossing it( as a nav-path corridor bound).
One can notice that the 90 degrees turn is the "least efficient one", as the distance between the starting point and the final direction is the greatest.

Low speed commands

A very annoying behaviour for bot move control is that if velocity modulus U_mVel is set below Stopspeed*Friction/AccelCoeff(=60), assuming a straight move, the engine output in steady state is a different and lower actual velocity mVel= AccelCoeff* T* U_mVel. This precludes the use of simple speed controls ( like proportional control) for position control.