Physics Predictions: Catching AI & Drag Forces

Description

This project was made as a final research project for a course called Gameplay Programming. As the title suggest this was about predicting the state of physics objects ranging from predicting how an AI should behave to catch a flying projectile to calculating how much different the trajectory of a projectile should be to hit a target while undergoing external drag forces. A few demos were made to showcase the different possibilities of physics and -predictions.

For a more in-depth description and explanation, you can view the GitHub page I’ve written at the time of handing in this project here.

Physics Prediction Results

Demo 1: Unity Simulations & Reflect Forces

This was the first demo made, in which I played around with the possibility of simulating a virtual physics scene to track the trajectory of a simulated projectile if it were to be launched and bounced around with additional reflect forces. This worked exactly as expected but isn’t optimal for a few reasons. Technically, this is more of a physics simulation than it is a prediction, and it is not very performant. Especially when you add more environments that your projectile has to be simulated in, you can start to feel the jitter in the smoothness of the demo. That being said, it’s a good example to compare my custom predictions to in order to make sure they’re accurate.

Demo 2: Physics Predictions & Runner AI

Physics Predictions (Geometric & Analytical Solution)

Here is where the sails finally start aligning with the wind. Based on the geometric solution in the physics prediction paragraph in the book AI For Games (see credits) I started creating additional functionality to my launcher that didn’t include Unity’s physics system. With the controls, you can rotate the launcher and adjust the speed/force you launch the projectile with. The result? A prediction of where the projectile will be landmarked with an orange cross, as well as a visualization of the trajectory of the projectile. I made it possible to swap between Unity’s simulation and my custom prediction physics as a comparison technique, and I’m glad to say the results are close to indifferent. Click here to view the code snippet down below!

Not only was a geometric solution found, but an analytical solution as well. This includes Lagrange interpolations to define the 2D trajectory using 3 points in space that define the polynomial we’re looking for. Since the demo is in a 3D world, it took some extra math to convert our 3D problem into a 2D problem first to solve for a direction, then finally bring it back to 3D and conclude the final predictions. The 3D to 2D conversion seemed a little cumbersome but is necessary to prove the analytical solution. Because of this reason, I do prefer the geometric solution, but it was nevertheless very interesting to research its limitations. I would like to mention here a close friend of mine introduced the math behind the Lagrange interpolations to me and was a huge contribution to the analytical solution (see credits).

Runner AI

The launcher obviously knows every variable given by the user to calculate and can predict these things with textbook formulas. That’s when I thought it would be interesting to see if a little AI with no knowledge of these given variables can somehow come to the same conclusion (spoiler alert, the answer is yes). All that the AI is given is the fact that a projectile has been shot. It has its own camera to observe the scene with and can track the time and positions of the projectile when it comes in its view. Based on this information the AI can estimate the direction the projectile moves in along with its speed. With this information calculated, it can further conclude its landing position, on which the AI calculates the optimal speed and velocity to catch the projectile before landing. 

Demo 3: Inverse Physics Predictions & Drag Forces

Inverse Physics Predictions

Instead of predicting where a projectile will land with a certain velocity, we now want to know the velocity to make a projectile land on a target position. This alone wasn’t rocket science based on what the other demos have showcased already and required a bit of re-ordering the formulas we already know to get to different variables. If there’s not enough force to make the shot the launcher will turn red.

Drag Forces

A stretch goal of mine was to implement drag forces at the time of creating this project but unfortunately ended in some research. Luckily in my free time, I made it possible to add this more complex addition to the physics predictions. It started with the inverse physics prediction to hit a given target and introducing an additional white cross to mark where the projectile would like due to the drag forces. Click here to view the code snippet down below!

It’s a start, and it’s cool to see the impact on the projectile, but the initial idea was to calculate the trajectory to actually hit the target. Due to aerodynamic drag and viscous drag being an extremely complex topic, a more programmer-inspired way can still be introduced to solve this problem. The answer: an algorithm based on a binary search between angles to rotate the initial direction within the case of under-or overshooting the target. An additional check I implemented is to adjust the speed/force in case of undershooting the target even with a perfect angle (45 degrees). I made sure it always used the smallest amount of force in case it is possible to still hit the target. To make this implementation a bit more flexible, it’s possible to change the iterations of how many times you want to refine or to what amount of force you’re willing to check as well as the margin of how accurate the shot has to be. What you see in the gif underneath is me picking a target (orange cross) and running the refine algorithm to see where the projectile would land after applying it with a margin of 1 unit off (white cross). Click here to view the code snippet down below!

Most Interesting Code Snippets

Predicting Landing Position (given direction and speed)
//Figure out when projectile will land (time to land)
//Solving for time
float plus = (-_direction.y * _speed + Mathf.Sqrt((_direction.y * _direction.y) * (_speed * _speed) - 2 * _gravityVector.y * (LaunchPos.position.y - 0))) / _gravityVector.y;
float min = (-_direction.y * _speed - Mathf.Sqrt((_direction.y * _direction.y) * (_speed * _speed) - 2 * _gravityVector.y * (LaunchPos.position.y - 0))) / _gravityVector.y;
_totalTime = Mathf.Max(min, plus);

//Calculate the future position (where the projectile will land)
Vector3 futurePos = new Vector3
(
    LaunchPos.position.x + _direction.x * _speed * _totalTime,
    0.01f,
    LaunchPos.position.z + _direction.z * _speed * _totalTime
);

//Set indicator sprite to that position to visualize
if (UseHitIndicator)
    HitIndicator.position = futurePos;

//Set physics settings for our predictor, so he can visualize the trajectory of our projectile
Predicter.SetPhysicsSettings(LaunchPos, _direction, _speed, _totalTime);
Predicting Velocity To Hit Target (given target and speed)
//Given a target pos, start pos and velocity speed -> we need to solve the direction in which to fire
//To solve this, we can start by solving for time given our knowns
Vector3 T = Target.position - LaunchPos.position;
float dotGT = Vector3.Dot(T, _gravityVector);
float sqrdSpeed = _speed * _speed;

//Quadratic equation to solve for two times
float a = _gravityVector.sqrMagnitude;
float b = -4 * (dotGT + sqrdSpeed);
float c = 4 * T.sqrMagnitude;

//Check if there will be an actual solution given our speed/force factor
float D = (b * b) - 4 * a * c;
if (D < 0)
{
    GetComponent<MeshRenderer>().material = InvalidShotMaterial;
    return new FiringData(false, 0f, Vector3.zero);
}
else
{
    GetComponent<MeshRenderer>().material = ValidShotMaterial;
}
    
//Solve for two times
float time0 = Mathf.Sqrt((-b + Mathf.Sqrt(D)) / (2 * a));
float time1 = Mathf.Sqrt((-b - Mathf.Sqrt(D)) / (2 * a));

//Find actual time to target
float time = 0f;
if (time0 < 0)
    if (time1 < 0)
        return new FiringData(false, 0f, Vector3.zero);
    else
        time = time1;
else
    if (time1 < 0)
        time = time0;
    else
        time = Mathf.Min(time0, time1);

//Return firing direction
Vector3 dir = (T * 2 - _gravityVector * (time * time)) / (2 * _speed * time);
FiringData firingData = new FiringData(true, time, dir);
Predicting Position In Time (with and without drag forces)
Vector3 CalculatePositionWithoutDragForce(float t)
{
    //Solving for Pt = p0 + u*s*t + (gt^2)/2
    return _launchPos.position + _direction * (_speed * t) + _gravityVector * (t * t) / 2f;
}

Vector3 CalculatePositionWithDragForce(float t)
{
    //EulerNumber
    float e = 2.718281828459f;

    //Solving the equation: Pt = g - kPt (simplified version for taking drag into account)
    //We can solve the following: Pt = (gt - Ae^-kt) / k + B
    //With A and B being constants found from the position and velocity of the particle at t = 0
    Vector3 A = _speed * _direction - (_gravityVector / _k);
    Vector3 B = _launchPos.position + (A / _k);

    //Position in time with drag force applied
    Vector3 Pt = ((_gravityVector * t - A * Mathf.Pow(e, -_k * t)) / _k) + B;

    return Pt;
}
Refine Algorithm to Hit Target through Drag Forces
//Only recalculate the refined drag direction when asked for
if (_isRefined)
    return _direction;

//Calculate firing solution, and get initial landing position guess
int sign = (_dragLandingPos.x < 0 || _dragLandingPos.z < 0) ? -1 : 1;
int signT = (Target.position.x < 0 || Target.position.z < 0) ? -1 : 1;
float distanceToDragLanding = (_dragLandingPos - LaunchPos.position).magnitude * sign;
float distanceToTarget = (Target.position - LaunchPos.position).magnitude * signT;
float distanceDiff = Mathf.Abs(distanceToDragLanding) - Mathf.Abs(distanceToTarget);

//If our initial guess isn't too far from the landing position with drag -> use initial direction and speed
if (Mathf.Abs(distanceDiff) < DragMargin + float.Epsilon)
{
    _isRefined = true;
    _speed = _speedBeforeRefinedDrag;
    return _direction;
}

//Binary search to ensure closer trajectory to target
float minBound = 0;
float maxBound = 0;

//Forward vector to target
Vector3 fwdDirection = _direction;
fwdDirection.y = 0;
fwdDirection = fwdDirection.normalized;

//Angle from forward vector to target to the direction vector in radians
float angle = Vector3.Angle(fwdDirection, _direction) * Mathf.Deg2Rad;
if (distanceDiff > 0)
{
    //Maximum bound -> use shortest possible shot as minimum bound
    maxBound = angle;
    minBound = -Mathf.PI / 2f;

    //Create new rotated direction
    Vector3 dirCopy = _direction;
    Vector3 newDir = Quaternion.AngleAxis(minBound * Mathf.Rad2Deg, fwdDirection) * dirCopy;

    //Calculate new landing pos and check if it's close enough in distance to target
    Vector3 landingPos = CalculatePositionWithDragForce(_totalTime, newDir);
    landingPos.y = 0.01f;
    float distanceToLandPos = (landingPos - LaunchPos.position).magnitude * sign;
    float diff = Mathf.Abs(distanceToLandPos) - Mathf.Abs(distanceToTarget);

    //If so, use this as direction
    if (Mathf.Abs(diff) < DragMargin + float.Epsilon)
    {
        _isRefined = true;
        return newDir;
    }   
}
else
{
    bool keepLoop = true;
    while (keepLoop)
    {
        //Need to check for maximum bound here
        minBound = angle;
        maxBound = Mathf.PI / 4f;

        //Create new rotated direction
        Vector3 dirCopy = _direction;
        Vector3 newDir = Quaternion.AngleAxis(maxBound * Mathf.Rad2Deg, fwdDirection) * dirCopy;
        
        //Calculate new landing pos and check if it's close enough in distance to target
        Vector3 landingPos = CalculatePositionWithDragForce(_totalTime, newDir);
        landingPos.y = 0.01f;
        float distanceToLandPos = (landingPos - LaunchPos.position).magnitude * sign;
        float diff = Mathf.Abs(distanceToLandPos) - Mathf.Abs(distanceToTarget);

        //If so, use this as direction
        if (Mathf.Abs(diff) < DragMargin + float.Epsilon)
        {
            _isRefined = true;
            return newDir;
        }

        //If not, check if we can get closer to the target with best possible angle we rotated with (45degrees)
        //By increasing the speed 
        if (diff < 0)
        {
            if (_iterationCounter == 0)
                SetSpeed(1f);

            //Need to increase the force in that case, and retry until we get it right
            SetSpeed(_speed + 1);
            ++_iterationCounter;
            if (_iterationCounter < _maxIterations)
            {
                continue;
            }
            else
            {
                //If it seems we can't even get it right even by increasing the force, just reset it and mark as invalid shot
                _iterationCounter = 0;
                SetSpeed(_speedBeforeRefinedDrag);
                _isRefined = true;
                success = false;
                return _directionBeforeRefinedDrag;
            }
        }
        else
        {
            keepLoop = false;
        }
    }
}

//We have a min and max bound -> so search for something inbetween that will fit the margin
Vector3 closestDir = _direction;
float rDist = DragMargin * 1000f;

_iterationCounter = 0;
while (Mathf.Abs(rDist) < DragMargin + float.Epsilon)
{
    _iterationCounter++;
    float a = (maxBound - minBound) / 2f;

    //Keep rotating the direction from min- to max-bound
    Vector3 dirCopy = _direction;
    closestDir = Quaternion.AngleAxis(a * Mathf.Rad2Deg, fwdDirection) * dirCopy;

    //Calculate new landing pos and check if it's close enough in distance to target
    Vector3 landingPos = CalculatePositionWithDragForce(_totalTime, closestDir);
    landingPos.y = 0.01f;
    float dist = (landingPos - LaunchPos.position).magnitude * sign;
    rDist = Mathf.Abs(dist) - Mathf.Abs(distanceToTarget);

    //Adjust boundaries of search
    if (rDist < 0)
        minBound = angle;
    else
        maxBound = angle;

    //Stop searching after an amount of tries and mark is invalid
    if (_iterationCounter > _maxIterations)
    {
        success = false;
        _isRefined = true;
        return closestDir.normalized;
    }
}

//Otherwise return successful direction
_isRefined = true;
return closestDir.normalized;

Contributors & Credits

On Predicting Physics/Drag Forces:

Millington, I. (2019). AI For Games. Boca Raton: Taylor & Francis.

On Lagrange Interpolations for 2D Predictions:

A close friend Lloyd Plumart for introducing/explaining the topic and bringing a huge contribution to the analytical solution for the landing prediction.

Amos Gilat, V. S. (2014). Numerical Methods For Engineers And Scientists (3rd Edition). Don Fowley.