26 replies to this topic

[noobnerd]

advanced motion prediction:

Heloo there, I am making a 2D space shooter and have come quite far already. I have the problem now that the enemy AI doesnt aim well enough using my current functions.
I therefore would need a better motion predicting function than the one i am currently using. I thought of a system that tell the ai where to aim if i am moving with constant speed and if i turn with a constant turn rate.

Like this:




where : the blue line represents the targets current motion vector
the green line is the bullets velocity vector, it can be directed in any direction
the black line at the player is the players current motion vector
and the curving black line represents the targets future positions. ( it will be a circle )


So i have a target at a position a,b with a motion vector c and a constant turn rate of d
i also have the player at a position e,f with a motion vector g and a bullet velocity of h the bullet will have the combined vector of the ship and its own vector


What i want to know is the coordinates where i should aim considering that all the values are constant.
I have been able to do this without the turning but i have not been able to solve this one.

Please help

OH i am programming basic so please do not post C++ ansvears as i will not understand them

[Álvaro]

I would first change the frame of reference to one where the shooter is at the origin and currently has a speed of 0. The basic idea for these problems is always the same: Find a time t in the future (t>0) such that the distance from the target to the origin is t*bullet_speed. Then shoot in the direction of where you expect the target to be at time t.

You can either solve the problem analytically or numerically. In the case of constant turning, I don't think you'll find an analytic solution, but doing it numerically shouldn't be too hard.

[noobnerd]

Wow thanks for a fast reply!
yes that is what i did in the case without turning, but i cant seem to find a way to get this done numerically. My problem is, that the only way i manage to describe the motion of the target is with a function containin Sin and Cos both with an unkown inside... i dont know how to extract those

Could you possibly help me with this?

[Álvaro]

Wow thanks for a fast reply!
yes that is what i did in the case without turning, but i cant seem to find a way to get this done numerically. My problem is, that the only way i manage to describe the motion of the target is with a function containin Sin and Cos both with an unkown inside... i dont know how to extract those

Could you possibly help me with this?

What you are trying to do (extracting the unknown from inside the trigonometric functions) is finding an analytical solution, which is probably impossible. If you write the equation as F(t) = 0, you can start with some guess t[0] (say t[0] = current_distance/bullet_speed) and then apply a few iterations of the Newton-Raphson method,

t[1] = t[0] - F(t[0])/F'(t[0])
t[2] = t[1] - F(t[1])/F'(t[1])
t[3] = t[2] - F(t[2])/F'(t[2])
t[4] = t[3] - F(t[3])/F'(t[3])

where F'(t) means the derivative of F at t.

t[4] will probably be a very good approximation to a solution. If your target's speed is relatively small compared to the bullet's speed (say, less than half), this process will pretty much always work.

[noobnerd]

Wow, i have just recently done derivata in school "newton-raphson method" sounds fancy!

i will definitely give it a try. Thank you

[noobnerd]

okay so im stuck again

these are the equations i have been able to get

x = (sin(g+h*k)*r+a-e-i*k))/k
y = (cos(g+h*k)*r+b-f-j+k)/k
x²+y² = z²
x²+y²-z²= 0


where g is the initial angle of the "radius" that the ship will turn around ( it will fly in a circle if it has constant turnrate )
h is the turnrate in angles/frame
k is the amount of turns or frames
r is the radius of the circle
a,b are the x,y coordinates of the center of the circle
e,f are the x,y coordinates of the player ship
i,j are the x and y components of the ships motion vector
z is the bullet velocity
x,y are the bullets x and y motion vector components

i dont have a clue about how to derivate the last function ( not the x^2+y^2-z^2 = 0 but the one where you insert the sin(g+h*k.... ) stuff )

help?

and thanks for helping me out this far

[Emergent]

So which variables are your unknowns? x,y, and z? (Also, your last two equations are equivalent.)


The following answers your question if the unknowns are x,y, and z: The Jacobian (matrix of partial derivatives) of the function

h(x,y,z) = (h1(x,y,z), h2(x,y,z), h3(x,y,z))

where

h1(x,y,z) = x - (sin(g+h*k)*r+a-e-i*k)/k;

h2(x,y,z) = y - (cos(g+h*k)*r+b-f-j+k)/k;

h3(x,y,z) = x^2+y^2 - z^2;

is

Dh(x,y,z) =


[ 1, 0, 0]
[ 0, 1, 0]
[ 2*x, 2*y, (-2)*z] .

The idea is that you're trying to find x,y, and z such that h(x,y,z)=(0,0,0), using the Newton-Raphson method.

It'd probably be a good exercise to work this out on your own, or to compute additional derivatives if you have additional unknowns. To do this, you'll need,

1.) The Chain Rule (just wiki it)
2.) The Product Rule (ditto)
3.) Some trig. derivatives. Namely, (d/dx)(sin(x)) = cos(x) and (d/dx)(cos(x)) = -sin(x).

[Álvaro]

Just try to express the position of the target at time t. Can you do that?

[noobnerd]

@ Emergent, x and y and k are unknown. I undestand know that it was somewhat misleading to have bullet velocity as z.
I dont really understand how to use the [1,0,0] [0,1,0] [2*x,2*y,(-2)*z] which you have provided. I assume it is a matrix, but i dont know much about them. I get the last line of the ansvear, it is the derivative of the last function?

I will do as you say and wiki theese things and perhaps even learn how to do that
Thank you.

@Alvaro

yes i can

x = a+sin(g+h*t)*r
y = b+cos(g+h*t)*r

where x,y are the future coordinates
a,b is the center of the "circle"
g is the angle of the original "radius"
h is the turnrate per frame
r is the radius of the "circle"

the radius can be obtained like this:

r = (180*v)/(h*pi)

where v is the velocity of the target
h is the turnrate
pi is pi

a and b can be obtained like this:

a = cos(m+90)*r
b = sin(m+90)*r

where m is the initial angle of the target ( compared to a line pointing upwards on the screen )

and the angle of the "radius" is

g = m-90

[Álvaro]

@Alvaro

yes i can

x = a+sin(g+h*t)*r
y = b+cos(g+h*t)*r

That's great! Now define

F(t) := x^2 + y^2 - bullet_speed^2*t^2 = (a+sin(g+h*t)*r)^2 + (b+cos(g+h*t)*r)^2 - bullet_speed^2*t^2
F'(t) = 2*(a+sin(g+h*t)*r)*cos(g+h*t)*h - 2*(b+cos(g+h*t)*r)*sin(g+h*t)*h - 2*bullet_speed^2*t

I might have made a mistake in taking the derivative, so check it. Then apply what I posted earlier about Newton-Raphson.

[EDIT: Indeed, I had made [at least] one mistake, which noobnerd detected. I had "F(t) := x^2 + y^2 - bullet_speed*t" where it should have said "F(t) := x^2 + y^2 - bullet_speed^2*t^2".]

[Emergent]

I dont really understand how to use the [1,0,0] [0,1,0] [2*x,2*y,(-2)*z] which you have provided. I assume it is a matrix, but i dont know much about them. I get the last line of the ansvear, it is the derivative of the last function?

Yeah, it's a matrix. The point is mostly just that, you need to take a partial derivative of each function with respect to each variable, so arranging them in a rectangular array is just a convenient way to keep track of them all.

The matrix is called the Jacobian of the function h. This means the following:
1.) The rows correspond to the elements of h -- i.e., h1, h2, and h3, respectively (from top to the bottom). In other words, each row corresponds to one scalar equation.
2.) The columns correspond to the variables. In this case, these are x, y, and z respectively (from left to the right). (Sorry I used the wrong variables, but I'll stick with them for the duration of the post just to explain what a Jacobian is)
3.) The entry in the i-th row and j-th column is the partial derivative of the ith function (hi) with respect to the jth variable.

For instance, the (3,2) entry is 2*y. This is (d/dy)h3.

I hope that explains at least the surface level of things.

It sounds like you're working with a different function now, so this particular Jacobian won't be too useful to you. Still the idea will be the same for whatever function you do end up working with.

I think alvaro will take it from here, but I'm always happy to help.

Peace.

[noobnerd]

@ alvaro :

nice! But some questions, there doesnt seem to be any reference to the shooters location or motion vector in the functions you have defined, are they useless? also, why is the function f(t) := x²+y²-bullet_speed*t ? Im probably just wrong but shouldnt it be bulletspeed^2 ?

But Thanks you very much for taking the time to ansvear my questions so far!

@ Emergent :

Oh okay i think i get it now, Thank you very much for your assistance in this matter

[Álvaro]

@ alvaro :

nice! But some questions, there doesnt seem to be any reference to the shooters location or motion vector in the functions you have defined, are they useless?

That's was covered in the first sentence of my first post in this thread.

I would first change the frame of reference to one where the shooter is at the origin and currently has a speed of 0.

also, why is the function f(t) := x²+y²-bullet_speed*t ? Im probably just wrong but shouldnt it be bulletspeed^2 ?

Ooops! Big mistake. Actually, we are both wrong. It should be
F(t) := x^2 + y^2 - bulletspeed^2 * t^2

[noobnerd]

Oh damn i missed that!

oh okey so the a and b in your function are the center of the circle, but relative to the players position?
but how do i get the players speed to zero? It should affect the bullets vector somehow?

Damn i feel dumb now

[Álvaro]

I'll use vector notation for briefness and clarity. If the target's position at time t is T(t), the attacker at time 0 is at A, with a velocity v, then F(t) is

F(t) = (T(t) - (A + t * v))^2 - bullet_speed^2 * t^2

Does that make sense?

[noobnerd]

well yes i think i do now that makes sense

[noobnerd]

hmm while i was doing the newton method i noticed that my calulator ( which is symbolic ) can do derivates. so i checked what the derivate of
F(t) := (a+sin(g+h*t)*r)^2 + (b+cos(g+h*t)*r)^2 - bullet_speed^2*t^2
which was
F´(t) = r*((a*h*π*cos(h*t+g))/90 - (b*h*π*sin(h*t+g))/90)-2*t*bullet_speed^2


i guess my calculator would be right? (not that i know how it came to that ansvear )

[Álvaro]

I don't know where those factors of pi are coming from. However, once you have it in code, it's easy to verify if F'(t) is likely to be correct: Pick some value of t and compute (F(t+h)-F(t))/h for some small value of h (say, 1e-4). The result should be very close to F'(t).

[EDIT: Actually, I do know what your calculator is doing. It's using degrees instead of radians, so funny factors pop up everywhere. Just use radians.]

[noobnerd]

oh true , now it says:

F´(t) = 2*a*h*cos(h*t+g)*r-2*b*h*sin(h*t+g)*r-2*t*v^2

which seems to be exactly the same as yours

indeed when i tried to code my version, it just gave freaky numbers
ill try yours now

thank you. and btw, how do you "rate" posts here? it says that i should take my time to rate any posts?

[Álvaro]

thank you. and btw, how do you "rate" posts here? it says that i should take my time to rate any posts?

I think the only thing you can do now is click the "I Like This" button at the bottom-right corner of each post.