Linear constant speed Projectiles

Predicting a targets position when firing a linear projectile

Overview

Ranged AI are common in games, and in an effort to make it a more enjoyable player experience we want them to predict the players movement (making it believable) but not hitscan so the player has some chance for outplay.

This post is based off the following GDC talk

The project can be found here: Github link

The GDC talk does an exceptional job of explaining the details, which I may re-explain and recount later but for now here a UE implementation of the logic talked about for predicting a linear projectile.

.h

// Given a constant speed, and a targets movement, determine how far to lead the target in order to hit it
bool PredictTargetLocation(const float ProjectileSpeed, FVector& OutPredictedLocation);

.cpp

/*
	Algorithm Summary:
		Based off (https://shellsphinx.github.io/images/PredictableProjectiles.pdf)

		Find the targets future position, at time (t), given:
			- projectile constant velocity
			- targets current instantaneous velocity (will account for average of history later) 
			and position

		Equation for target's movement
			X'	= Targets future position
			Xot = Targets current position (origin)
			Vt	= Targets instantaneous velocity
			t	= time

			Linear equation:
				X' = Xot + (Vt * t)

		Equation for projectile's movement
			X'	= Projectiles future position
			Xop	= Projectiles current position (origin)
			Sp	= Projectiles constant speed
			t	= time

			Linear equation:
				X' = Xop + (Sp * t)  
			Or better the equation of a circle
				(X' - Xop)^2 = (Sp * t)^2

		Both equations have X' and t.
		So combine via X' and solve for t which gives us a quadratic that we can solve 
		to get polynomial expansion: a^2 + b + c = 0
			
		a = (Vt^2 - Sp^2)
		b = (2 * (Xot - Xop) * Vt)
		c = (Xot - Xop)^2	

		then just solve the quadratic which gives (t) and plug back into 
		Equation for target's movement to find X'

	Note: Any vector multiplies are just dot products
*/
bool AZCLinearAI::PredictTargetLocation(const float ProjectileSpeed, FVector& OutPredictedLocation)
{	
	if (TargetChar == nullptr)
	{
		return false;
	}

	const FVector Xot = TargetChar->GetActorLocation();	// Targets current position
	const FVector Vt = TargetChar->GetVelocity();		// Targets current velocity (speed * direction)

	const float Sp = ProjectileSpeed;			// Projectile constant speed
	const FVector Xop = GetActorLocation();			// Projectile current position (spawed at AI's position)

	// a = (Vt^2 - Sp^2)
	float a = FVector::DotProduct(Vt, Vt) - (Sp * Sp);

	const FVector XotDiffXop = Xot - Xop;

	// b = (2 * (Xow - Xop) * Vw)
	float b = 2 * FVector::DotProduct(XotDiffXop, Vt);

	// c = (Xow - Xop)^2
	float c = FVector::DotProduct(XotDiffXop, XotDiffXop);

	float t = 0.f;

	// Solve for Time (t) using quadratic
	if (a == 0.f)
	{// divide by 0 early out
		t = -(c / b);
	}
	else
	{
		// determinant: b^2 - 4ac
		float det = (b * b) - (4 * a * c);
		if (det < 0)
		{// invalid, just use target current position
			OutPredictedLocation = TargetChar->GetActorLocation();
			return true;
		}
		else if (det == 0)
		{// t = -b/2a
			t = -b / (2 * a);
		}
		else
		{
			// (-b + sqrt(b^2 - 4ac)) / 2a
			float tPlus = (-b + FMath::Sqrt((b * b) - (4 * a * c))) / (2 * a);

			// (-b - sqrt(b^2 - 4ac)) / 2a
			float tMinus = (-b - FMath::Sqrt((b * b) - (4 * a * c))) / (2 * a);

			if (tPlus > 0 && tMinus > 0)
			{
				t = FMath::Min(tPlus, tMinus);
			}
			else if (tPlus > 0)
			{
				t = tPlus;
			}
			else if (tMinus > 0)
			{
				t = tMinus;
			}
			else
			{
				ensureMsgf(false, TEXT("This should be mathematically impossible for both solutions (if we got this far) to be invalid"));
				return false;
			}
		}
	}

	// Now that we have Time (t) plug it back into Equation for target's movement
	OutPredictedLocation = Xot + (Vt * t);
	return true;
}