Predicting object position

[giblit]

So I have a static turret that will be shooting a projectile with a constant speed and direction at an object that moves along a predefined path at a constant speed. We are probably over thinking the problem and can't seem to find a viable solution. Here is one of the formula's that I came up with but doesn't work. I figured that the point that they intersect would would be the same as the moved positions. So P = position, V = Velocity(Direction and Magnitude) which would mean P1 + V1 = P2 + V2 so I = P2 - P1 + V2 - V1 but, there seems to be something wrong with the equation because it is aiming slightly behind the object. Does anyone have any suggestions that I could try please?

[LB]

You can use dead reckoning to predict the object's future location and shoot there. Thankfully, all the engineering behind this has been done for you - you just need to research how to implement it for yourself.

[giblit]

Thanks for the suggestion, I will try and give it a try and let you know how it works.

[helios]

The problem is incorrectly stated. You only know one of the velocities. You know: where the target is now, where it's going, where the turret is, and how fast its projectiles move. You need to figure out in which direction to point the turret to hit the target.

p1 + v1 dt = p2 + (cos(theta) s2, sin(theta) s2) dt

To find dt, you first need the distance from p2 to the intersection of the lines p1 + v1 t = p2 + (cos(theta) s2, sin(theta) s2) t, which is a system of linear equations (theta is a free variable, t is the bound variable):

{p1_x + v1_x t = cos(theta) s2 t
{p1_y + v1_y t = sin(theta) s2 t
(etc. for higher dimensions)

You'll probably get some horrible expression out of that. You evaluate either line on t and plug the vector into the Euclidean distance function (square root of sum of squares) and you get an even more horrible expression, which you divide by s2 to get dt expressed as a function of theta.
Then you solve for theta:

p1 + v1 dt = p2 + (cos(theta) s2, sin(theta) s2) <here be dragons>(theta)

which will give you the direction the turret needs to point to hit the target.
I recommend a computer algebra system.

EDIT: Well, there are some problems here and there, but that's in general lines what you need to do. In case it wasn't clear, at the end you'll get a function that takes p1, v1, p2, s2, and outputs theta.

[giblit]

Yeah I appreciate you trying to help but I am not exactly sure what you mean. Though since the time is on both sides anyways they would divide off so it would be like p1 + v1 = p2 + cos(theta)s2 ? sin(theta) s2?

[helios]

a + bc = d + ec is not equivalent to a + b = d + e

[giblit]

Oh sorry, for some reason I was thinking it said was (p1 + v1)t and not p1 + v1t

[ne555]

P = position of target
v = velocity of P
T = position of turret
w = velocity of bullet
C = point of intersection
\phi = angle PC with the horizontal
\theta = angle TC with the horizontal


Without loss of generality we can say that P=(0;0) and T=(T;0)
The equations then become
|v| t \cos \phi = T + |w| t \cos \theta
|v| t \sin \phi = |w| t \sin \theta

taking only the second equation results
\sin \theta = \frac{ |v| \sin \phi }{ |w| }
which can be easily solved (you'll get two results, need to discriminate which is valid)

[giblit]

Thanks for the help, but I am still having difficulties.

I think I may take the easy way out (even if it is a little bit less effective) since it will be more accurate I believe. Basically what I am going to do is since I have a list of the way points (nodes) I'll just check different time intervals say every 1/10 of a second and check where the object will be and if the time it takes for the bullet to reach it is less than the number of seconds to get there then that will be the location, otherwise check more places. I actually have it really close

Predicted:
0 = (-10.00143,9.955518)
0.25 = (-10.00125,7.455518)
0.5 = (-10.00107,4.955519)
0.75 = (-10.00089,2.455519)
1 = (-10.00072,-0.04448032)

Actual:
0 = (-10.00142,9.755518)
0.25 = (-10.00124,7.212272)
0.5 = (-10.00106,4.699645)
0.75 = (-10.00088,2.029775)
1 = (-10.0007,-0.4849186)

but I am slightly off between .2 and .5 units the only reason I can think of is because I am using deltaTime instead of a fixed time for the movement. Here is my prediction code (it's in c# but very similar to c++)

public Vector3 getPosAfterSec(float seconds)
{
	/* Predicting position after x seconds
	 * 1) check how many seconds it takes to reach
	 * the next waypoint.
	 * 2) if the time taken to reach next waypoint
	 * is <= the amount of seconds left then
	 * the current position is at that location
	 * if the time taken is > the amount of seconds left
	 * then move as far as you can towards the next waypoint
	 * 3) return predicted location */

	Vector3 position = transform.position; //the position will start at where it currently is
	int nextWaypoint = currentWaypoint; //the waypoint currently traveling to (next one to reach)

	while(seconds > 0) //there is time left
	{
		float timeToNextWaypoint = Vector3.Distance(position, waypoints[nextWaypoint]) / movementSpeed;

		if(seconds >= timeToNextWaypoint) //can reach the next waypoint
		{
			position = waypoints[nextWaypoint]; //move it to the waypoint
			seconds -= timeToNextWaypoint; //subtract time taken to reach the next waypoint
			if(++nextWaypoint == waypoints.Length) //get the next waypoint
			{
				nextWaypoint = 0;
			}
		}
		else //can't fully reach the next waypoint, move as close as possible
		{
			float magnitude = movementSpeed * seconds;
			position = Vector3.MoveTowards(position, waypoints[nextWaypoint], magnitude); //move towards the next waypoint
			seconds = -1.0f; //it went as far as posssible
		}
	}

	return position;
}

Do you guys see any logic errors?

*fixed slight bug but still not working 100%

[helios]

magnitude should be a unitless value.
speed * time == space/time * time == space
So magnitude actually contains a value in units of space.
You need to divide it by the distance between the waypoints.

[giblit]

I'm not sure I fully understand what you mean. Maybe I named it wrong, basically my "magnitude" is the number of units the object will move in the amount of time left. The MoveTowards function would be the same as position = position + direction * speed * time; If I divide it by the distance then it wouldn't be moving the right amount of units and would make the prediction even worse if what you mean on line 32 I put magnitude / distance.

AHH I just spotted an error. Line 32 it has "currentWaypoint" and it should be "nextWaypoint." Though it still seems to be slightly off.

[helios]

Well, that's unusual. I thought it was a simple vector interpolation (p0 + (p1 - p0) * x).

[giblit]

Yeah I think that is what a vector "magnitude" is but when I said "magnitude" I meant like size (amount) of units to move. Guess I could have named it something like "unitsToMove." I am thinking the problem is probably that I didn't use a fixed time for my update function. I think I'll try using a fixed delta time instead of arbitrary delta times.

Here's the moveTowards function by the way http://docs.unity3d.com/ScriptReference/Vector3.MoveTowards.html

[Disch]

I am thinking the problem is probably that I didn't use a fixed time for my update function. I think I'll try using a fixed delta time instead of arbitrary delta times.

I typically do logic updates 50 times a second, then interpolate movement between updates to allow drawing at any framerate.

Fixed time between logic updates makes a lot of things much easier, and keeps your code deterministic which makes bugfixing much easier.

[ne555]

Let me see if I understand.
You've got an object that moves along a cyclic path. The path is continuous and consist of piece-wise linear motions at constant speed.

You then try to compute (predict) the position where the object would be after t seconds,
but somehow the algorithm is incorrect and it misses the actual position of the object


¿how did you got the actual position of the object?
¿how is it possible that you have error for t=0?

[giblit]

@Disch That makes a lot more sense.

@Ne555 Yes, you are correct.

¿how did you got the actual position of the object?

Inside the "update" function I moved the object then got the position if x amount of time passed.

¿how is it possible that you have error for t=0?

I had something like if timePassed > 25 ...) instead of outputting t = 0 then doing that for the rest.

The predictions are spot on now. :)

Thanks for all the help.

If anyone else had a similar problem here is what I did for the predicting

public Vector3 getPosAfterSec(float seconds)
{
	/* Predicting position after x seconds
	 * 1) check how many seconds it takes to reach
	 * the next waypoint.
	 * 2) if the time taken to reach next waypoint
	 * is <= the amount of seconds left then
	 * the current position is at that location
	 * if the time taken is > the amount of seconds left
	 * then move as far as you can towards the next waypoint
	 * 3) return predicted location */

	Vector3 position = transform.position; //the position will start at where it currently is
	int nextWaypoint = currentWaypoint; //the waypoint currently traveling to (next one to reach)
	const float threshold = 0.002f;
	while(seconds >= Time.fixedDeltaTime - threshold) //fixedDeltaTime = 0.02 seconds
	{
		float timeToNextWaypoint = Vector3.Distance(position, waypoints[nextWaypoint]) / movementSpeed;

		if(seconds >= timeToNextWaypoint) //can reach the next waypoint
		{
			position = waypoints[nextWaypoint]; //move it to the waypoint
			seconds -= timeToNextWaypoint; //subtract time taken to reach the next waypoint
			if(++nextWaypoint == waypoints.Length) //get the next waypoint
			{
				nextWaypoint = 0;
			}
		}
		else //can't fully reach the next waypoint, move as close as possible
		{
			float magnitude = movementSpeed * seconds;
			position = Vector3.MoveTowards(position, waypoints[nextWaypoint], magnitude); //move towards the next waypoint
			seconds = -1.0f; //it went as far as posssible
		}
	}