Intercept prediction in a 2D game and teh maths...

I have a 2D, top down, Newtonian physics, space shooter in the works, something similar to Gravity Well if anyone of you remember that game, and I'm working on some of the AI. Currently an AI ship, using only linear rotation and rear thrusters, is able to move too, and come to a relative stop at a target location.

As of right now the intercept prediction, meaning where the AI thinks it needs to go to intercept the target, is just TargetPosition + TargetVelocity + TargetAcceleration ( all vector3s) and, while this works ("works"), it's not as clean and precise as I would like.

So, firstly, my main question is what is a better way to do intercept prediction when the position vector, velocity vector and acceleration vector of both the AI ship and the target are known?

My first thought was to use the kinematic equation d = vt + 1/2at^2 where v would be the velocity vector and a would be the acceleration vector but what would t be?

maybe we can solve for t first? Get the kinematic equation for distance for both the AI ship and the target, set them equal to each other and solve for t.

v(s)t + 1/2a(s)t^2 = v(t)t + 1/2a(t)t^2

Which becomes (according to my TI-89):

t = 0 or t = -2(v(t) - v(s))/(a(t) - a(s)) which essentially gives us t = -2V/A

Assuming this is an acceptable approach, this is where I'm getting stuck. t = -2V/A means we're dividing a vector3 by a vector3 and I don't know of an acceptable way to do that. Maybe use the magnitude of both V and A? t does have to be a scalar, after all. I don't really like the idea of frequent square root operations. And what happens when the magnitude of A is 0?

Thoughts anyone?

 

Ok, been a while since I posted this and zero responses...

I'll update with what I've gotten so far:

Determining t

Code (CSharp):

1.     private void UpdateTimeScalar()
2.     {
3.         t = 2f * (objTargetKinematics.v3Velocity - objKinematics.v3Velocity).magnitude;
4.         t = t / (objTargetKinematics.v3Acceleration - objKinematics.v3Acceleration).magnitude;
5.     }

Getting the distance/direction vector (used for both the ship and the target) using t with the kinematic equation:

Code (CSharp):

1.     public Vector3 GetDistanceVector(float t)
2.     {
3.         return (v3Velocity * t) + (0.5f * v3Acceleration * (t * t));
4.     }

Figuring out our new target direction (the commented code is the old method):

Code (CSharp):

1.     private void UpdateTargetDirectionVector()
2.     {
3.         v3TargetDirection = objTarget.transform.position;
4.  
5.         v3TargetDirection -= objKinematics.GetDistanceVector (t);
6.  
7.         v3TargetDirection += objTargetKinematics.GetDistanceVector (t);
8.  
9.         v3TargetDirection -= transform.position;
10.  
11.         //v3TargetDirection = objTarget.transform.position - objKinematics.v3Velocity - objKinematics.v3Acceleration;
12.  
13.         //v3TargetDirection += objTargetKinematics.v3Velocity + objTargetKinematics.v3Acceleration;
14.  
15.         //v3TargetDirection -= transform.position;
16.     }

This new method is more precise than the older one but creates a new problem. The AI ship will fly straight towards the intercept point until it reaches a certain distance then sporadically turns back and forth firing it's thrusters until it finally comes to a complete stop at the target. This last part is dreadfully slow.

So I'm missing something and not sure what it is.

Thoughts, anyone?

 

So! A day of firsts for me. First time recording something using Frags. First time uploading a video to Youtube. Welcome to the 21st century, right?

Anyways, the video shows the problem I'm having with the current code. Using Debug.DrawLine I'm showing the target prediction vector in red and the desired direction vector in blue. Everything seems to work properly until the AI gets within a certain distance of the target and then it gets the sporadic calculations that you'll see in the video.

 

I don't understand what your AI is supposed to do. It have to predict where the player will go or something?

 

Sorry, I should have showed more of the video...
The AI ship is trying to intercept the player ship. To do this it predicts an intercept point based on the player ships current velocity and acceleration vector and the AI ships current velocity and acceleration vector. With the old math, the math that is currently commented out, it was doing that much more cleanly but overshooting the target and having to go back.

 

Why the AI not simply follow the player? Like if he where chasing him.

 

Because intercepting the target is more efficient and part of the point.

 

Are you using kinematic rigidbodies for the ships?
I will try to find a solution, I think I have an idea.

 

No I am not.

 

I just come with this, maybe is not the most performance friendly solution but it works

As you can see in the video, the Enemies(Red) are predicting where the Player(Blue) will be at certain time and if they can reach that position at the correct time. Knowing only the enemy and player speed, I store and List of all posible positions for the player in the future, then choose the best time/position ration of all items in the list.

At the beginning all enemies point directly at the player, because it has 0 velocity and obviously his position will not change, as soon the player start to accelerate they will point more and more ahead of the player position, at the end they land exactly where the player was at that time.

The code used for this of course, the magic happens in ComparePositions().

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4.  
5. //Class to store position at time
6. [System.Serializable]
7. public class TimePosition{
8.     public float time;
9.     public Vector2 position;
10. }
11.  
12. public class PositionPredictor : MonoBehaviour {
13.  
14.     [SerializeField]
15.     private Rigidbody2D Body;
16.     [SerializeField]
17.     private float Speed = 1;
18.     [SerializeField]
19.     private Rigidbody2D Target;
20.     [SerializeField]
21.     private float SecondsAhead = 20;//Predict target position 20 seconds ahead, higher the value = less performance
22.     [SerializeField]
23.     private float SecondsRate = .5f;//Time between predictions, lower the value = more accurate = less performance
24.     [SerializeField]
25.     private Transform ThisTransform;
26.     [SerializeField]
27.     private Transform TargetTransform;
28.     [SerializeField]
29.     private Vector2 TargetPosition;//Where target is going
30.     //Debug
31.     public Transform DebugPoint;
32.     public List<TimePosition> debugthis;
33.     public List<TimePosition> debugtarget;
34.  
35.     // Use this for initialization
36.     void Start () {
37.    
38.     }
39.  
40.     void ComparePositions()
41.     {
42.         //This
43.         List<TimePosition> thispos = new List<TimePosition>();//Debug
44.         Vector2 currentpos = Body.position;
45.         debugthis = thispos;//Debug
46.         //Target
47.         List<TimePosition> targetpos = new List<TimePosition>();
48.         Vector2 currenttargetpos = Target.position;
49.         debugtarget = targetpos;//Debug
50.  
51.         //Calculate all posible positions ahead for target
52.         for (float i = 0; i < SecondsAhead; i += SecondsRate)
53.         {            
54.             TimePosition NextTimePositionTarget = new TimePosition();
55.             Vector2 NextPositionTarget = currenttargetpos + (Target.velocity * i);
56.             NextTimePositionTarget.time = i;
57.             NextTimePositionTarget.position = NextPositionTarget;
58.             targetpos.Add(NextTimePositionTarget);
59.         }
60.  
61.         int closestindex = 0;
62.         float shortesttime = float.MaxValue;
63.         float previoustime = shortesttime;
64.         bool shortestfound = false;
65.  
66.         //Find shortest path
67.         for (int j = 0; j < targetpos.Count; j++)
68.         {
69.             TimePosition thistargetPos = targetpos[j];
70.             if (shortestfound)
71.             {
72.                 break;//Stop looping if the ideal path have been found
73.             }
74.  
75.             float closestpoint = float.MaxValue;
76.             float previousclosestpoint = closestpoint;
77.  
78.             for (float i = 0; i < SecondsAhead; i += SecondsRate)
79.             {
80.                 //Calculate every time/position for this
81.                 Vector2 NextPositionThis = currentpos + (Body.velocity * i);
82.  
83.                 float timetoreach = Vector2.Distance(Body.position,thistargetPos.position) / Speed;//How much time it will take to reach this position
84.                 float timedifference = Mathf.Abs(timetoreach - thistargetPos.time);
85.                 if (timedifference < shortesttime)
86.                 {
87.                     shortesttime = previoustime = timedifference;
88.                     closestindex = j;
89.                 }
90.                 else if (timedifference > previoustime)
91.                 {
92.                     shortestfound = true;
93.                 }
94.             }
95.         }
96.  
97.         TargetPosition = targetpos[closestindex].position;
98.         if (DebugPoint)
99.         {
100.             DebugPoint.position = TargetPosition;
101.         }
102.     }
103.    
104.     // Update is called once per frame
105.     void Update () {
106.         ComparePositions();
107.         Body.AddRelativeForce(new Vector2(Speed, 0));//Move forward
108.         //Rotate to target
109.         Vector3 vectorToTarget = (Vector3)TargetPosition - ThisTransform.position;
110.         float angle = Mathf.Atan2(vectorToTarget.y, vectorToTarget.x) * Mathf.Rad2Deg;
111.         Quaternion q = Quaternion.AngleAxis(angle, Vector3.forward);
112.         ThisTransform.rotation = Quaternion.Slerp(ThisTransform.rotation, q, Time.deltaTime * 10);
113.     }
114. }

 

Doing those prediction loops looks pretty inefficient. Did you try, per fixed update, getting each enemy to just predict where the player will be next fixedTime (pos += velocity * fixedTime) and adjusting their own body to head towards that point in the current frame? If you want to intercept further in front then calculate the prediction by multiplying fixedTime by more than 1.

Also, Craig Reynolds is your friend for this stuff: http://www.red3d.com/cwr/steer/

 

Yeah, nested for loops = bad juju.

I'm fairly comfident that a mathematical approach will work, I'm just missing a crucial part of my equation.

Currently I've abandoned the use of the kinematic equations (unless someone can convince me they were the correct approach) and gone back to my original math. It's cleaner and less erratic.

 

Yes, I think your original idea works and is what Craig Reynold's seek algorithm is. I would question whether you would know the targetAcceleration and/or whether to bother with it.

As per my previous comment, you could try getting your AIs to predict slightly further ahead by obtaining a target position with:

targetPosition = currentTargetPosition + currentTargetVelocity * predictAheadTime

One thing that I have experienced and that seems to come across in your videos is how the orientation of the AIs can make them look pretty dumb, you may need to play with their speed of orientation to get them to look 'good'.

 

I'm not good at maths so this was the best solution that came to my mind.
If you haven't found this yet, here is an algorithm that may help you.

• http://danikgames.com/blog/how-to-intersect-a-moving-target-in-2d/
• http://danikgames.com/blog/moving-target-intercept-in-3d/

 

So, I was trying to be clever in my newer "predictAheadTime" approach. I just graduated from college and I have my math minor and I was all "I'm going to USE this s**t!!" so I threw in some algebra, some physics, some Linear algebra, etc.. "Let's use all the math I thought I'd never use again!" was my battlecry, and it turned into a sounded-better-in-my-head kind of situation.

As (I think) I stated before, I went back to my old approach and that works for the most part but it still suffers from the problems I was facing before; that it has a tendency to overshoot the target and in my game idea I REALLY need it to, you know, NOT do that.

I think I'll try taking a stab at doing a new video to better highlight the issue.

 

http://wiki.unity3d.com/index.php/Calculating_Lead_For_Projectiles could be of help, it's essentially the same problem.

But a much easier way is simply for you to aim at the transform.forward * fudge of the target while outside of the fudge range (too close). This could be randomly varied for inaccurate AI (if it's too smart, it's no fun).

 

Wooh, it's literally been 2 years and I'm coming back to this problem again. Life put that project on hold and now I'm back.

Recapping where I'm at:

I have two ships, A and B, both with position velocity and acceleration vectors.

B is trying to intercept A.

Currently I'm predicting A's position in t using Pf = Pi + Vi*t + 1/2*A*t, t being time.deltatime, subtracting B's position from that point to get the direction vector, pointing B in that direction and accelerating. It works but its clunky and inefficient and prone to problems.

What I think is a better approach is, instead of accelerating towards the prediction point, acceleration in a direction that brings B's velocity vector in line with that prediction point. Something like Vf = Vi + At; A = (Vf - Vi)/ t, where t is time.deltatime and Vf is the direction to the prediction point. But this more or less appears to do the same thing.

I've looked at the bullet prediction stuff but I can't figure out how to bend that to my needs. Help?

 

An excellent article on this sort of problem:
https://www.codeproject.com/Articles/990452/Interception-of-Two-Moving-Objects-in-D-Space