# Advanced motion prediction ( 2D ) help

This topic is 2255 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

[size="2"]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.[/size]
[size="2"]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.[/size]

[size="2"]Like this:[/size]

[size=2][attachment=6027:show.jpg][/size]

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

[size="2"]So i have a target at a position[b] a,b [/b]with a motion vector [b]c[/b] and a constant turn rate of [b]d[/b][/size]
[size="2"]i also have the player at a position [b]e,f [/b]with a motion vector [b]g[/b] and a bullet velocity of [b]h [/b]the bullet will have the combined vector of the ship and its own vector[/size]
[size="2"][b]
[/b][/size]
[size="2"]What i want to know is the coordinates where i should aim considering that all the values are constant.[/size]
[size="2"]I have been able to do this without the turning but i have not been able to solve this one. [/size]

[size="2"]OH i am programming basic so please do not post C++ ansvears as i will not understand them [/size][img]http://public.gamedev.net/public/style_emoticons/default/huh.gif[/img]

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
[quote name='noobnerd' timestamp='1320853178' post='4882147']
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?
[/quote]

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 [url="http://en.wikipedia.org/wiki/Newton-Raphson_method"]Newton-Raphson method[/url],

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.

##### Share on other sites
Wow, i have just recently done derivata in school "newton-raphson method" sounds fancy!

i will definitely give it a try. Thank you

##### Share on other sites
okay so im stuck again [img]http://public.gamedev.net/public/style_emoticons/default/mellow.gif[/img]

these are the equations i have been able to get

[size="3"]x = (sin(g+h*k)*r+a-e-i*k))/k[/size]
[size="3"]y = (cos(g+h*k)*r+b-f-j+k)/k[/size]
[size="3"]x[sup]2[/sup]+y[sup]2[/sup] = z[sup]2[/sup][/size]
[size="3"]x[sup]2[/sup]+y[sup]2[/sup]-z[sup]2[/sup]= 0[/size]
[size="3"][sup]
[/sup][/size]
where [b]g [/b]is the initial angle of the "radius" that the ship will turn around ( it will fly in a circle if it has constant turnrate )
[b]h[/b] is the turnrate in angles/frame
[b]k[/b] is the amount of turns or frames
[b]r[/b] is the radius of the circle
[b]a,b[/b] are the x,y coordinates of the center of the circle
[b]e,f [/b]are the x,y coordinates of the player ship
[b]i,j [/b]are the x and y components of the ships motion vector
[b]z [/b]is the bullet velocity
[b]x,y[/b] 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 ) [img]http://public.gamedev.net/public/style_emoticons/default/huh.gif[/img]

help?

and thanks for helping me out this far [img]http://public.gamedev.net/public/style_emoticons/default/biggrin.gif[/img]

##### Share on other sites
[size="2"][font="Arial"]So which variables are your unknowns? x,y, and z? (Also, your last two equations are equivalent.)[/font]

[font="Arial"]The following answers your question if the unknowns are x,y, and z: The Jacobian (matrix of partial derivatives) of the function[/font]

[font="Arial"]h(x,y,z) = (h1(x,y,z), h2(x,y,z), h3(x,y,z))[/font][/size]

[font="Arial"][size="2"]where[/size][/font]

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

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

[size="2"]h3(x,y,z) = x^2+y^2 - z^2;[/size]

[size="2"] [font="Arial"]is[/font]

[font="Arial"]Dh(x,y,z) = [/font]

[font="Arial"]
[ 1, 0, 0]
[ 0, 1, 0]
[ 2*x, 2*y, (-2)*z] .[/font][/size]

[size="2"][font="Arial"]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,[/font][/size]
[size="2"] [/size]
[size="2"][font="Arial"]1.) The Chain Rule (just wiki it)[/font][/size]
[size="2"][font="Arial"]2.) The Product Rule (ditto)[/font][/size]
[size="2"][font="Arial"]3.) Some trig. derivatives. Namely, (d/dx)(sin(x)) = cos(x) and (d/dx)(cos(x)) = -sin(x).[/font][/size]

##### Share on other sites
Just try to express the position of the target at time t. Can you do that?

##### Share on other sites
@ 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 [img]http://public.gamedev.net/public/style_emoticons/default/blink.gif[/img]
Thank you.

@Alvaro

yes i can [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

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

##### Share on other sites
[quote name='noobnerd' timestamp='1320872087' post='4882271']
@Alvaro

yes i can [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

x = a+sin(g+h*t)*r
y = b+cos(g+h*t)*r
[/quote]

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".]

##### Share on other sites
[quote name='noobnerd' timestamp='1320872087' post='4882271']
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?
[/quote]

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 [i]Jacobian[/i] of the function [i]h[/i]. 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.

##### Share on other sites
@ 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[sup]2[/sup]+y[sup]2[/sup]-bullet_speed*[b][u]t [/u] ? [/b] 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 [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

##### Share on other sites
[quote name='noobnerd' timestamp='1320937658' post='4882604']
@ 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?[/quote]

That's was covered in the first sentence of my first post in this thread.
[quote name='alvaro']I would first change the frame of reference to one where the shooter is at the origin and currently has a speed of 0.[/quote]

[quote name='noobnerd']also, why is the function f(t) := x[sup]2[/sup]+y[sup]2[/sup]-bullet_speed*[b][u]t [/u] ? [/b] Im probably just wrong but shouldnt it be bulletspeed^2 ?[/quote]
Ooops! Big mistake. Actually, we are both wrong. It should be
F(t) := x^2 + y^2 - bulletspeed^2 * t^2

##### Share on other sites
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 [img]http://public.gamedev.net/public/style_emoticons/default/blink.gif[/img]

##### Share on other sites
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?

##### Share on other sites
well yes i think i do now that makes sense

##### Share on other sites
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
[color=#1C2837][size=2]F(t) := (a+sin(g+h*t)*r)^2 + (b+cos(g+h*t)*r)^2 - bullet_speed^2*t^2 [/size][/color]
[color=#1C2837][size=2]which was[/size][/color]
[color=#1C2837][size=2]F´(t) = r*((a*h*[/size][/color][b]?[/b][color=#1C2837][size=2]*cos(h*t+g))/90 - (b*h*[/size][/color][b]?[/b][color=#1C2837][size=2]*sin(h*t+g))/90)-2*t*bullet_speed^2 [/size][/color]
[size="2"][color="#1c2837"]
[/color][/size]
[size="2"][color="#1c2837"]i guess my calculator would be right? (not that i know how it came to that ansvear )[/color][/size]
[size="2"][color="#1c2837"]
[/color][/size]
[size="2"][color="#1c2837"]
[/color][/size]
[size="2"][color="#1c2837"]
[/color][/size]

##### Share on other sites
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.]

##### Share on other sites
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 [img]http://public.gamedev.net/public/style_emoticons/default/biggrin.gif[/img]

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?

##### Share on other sites
[quote name='noobnerd' timestamp='1321286260' post='4883804']
thank you. and btw, how do you "rate" posts here? it says that i should take my time to rate any posts?
[/quote]

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

##### Share on other sites
Wooohoo it works!

mostly...[img]http://public.gamedev.net/public/style_emoticons/default/dry.gif[/img]

i managed to code it down, and just as you said, IT WORKS!
but sometimes it will give me negative values which obviously dont work. Also sometimes it gives me quite normal values which dont work???

i dont seem to be allowed to attach .exes nor .rar files?

leftclick to place the shooter, press space to "drive" the target forward, press enter to shoot and press space to return from shooting.

the value in the topleft corner is the value of [b]t[/b] after 25 iterations of the Newton rahson method. i tried others but 25 seemed to be fine and very accurate for this quick test. ( 4 wasnt accurate enough)

oh and the litle white dot is where you should aim ( with the mouse)

the code of the newton calculation :

a# = rx#-x2# : b# = ry#-y2# : p# = pi()
v1# = 2*a#*h#*r# : v2# = 2*b#*h#*r# : v3# = -2*v#^2 : v4# = r#^2+a#^2+b#^2 : v5# = r#*2*b# : v6# = r#*2*a# : t0# = sqrt((x1#-x2#)^2+(y1#-y2#)^2)/v#
for i = 1 to 25
t0# = t0# - (v4#-t0#^2*v#^2+v5#*cos(h#*t0#+g#)+v6#*sin(h#*t0#+g#))/(v1#*cos(h#*t0#+g#)-v2#*sin(h#*t0#+g#)-v3#*t0#)
next

its DarkBasic code. might be quite unclear as it is so stacked.

rx#,ry# = coordinates of the center of the targets "circle"
x2#,y2# = coordinates of the shooter
h# = turnrate of target
v# = velocity
x1#,y1# = coordinates of target
t0# = the value of t#

any ideas of how to avoid negative and wrong values? i would rather it gave a blank than giving wrongs ...

##### Share on other sites
well then im just gona "like" all the posts here

##### Share on other sites
[quote name='noobnerd' timestamp='1321289553' post='4883829']
any ideas of how to avoid negative and wrong values? i would rather it gave a blank than giving wrongs ...
[/quote]

Yes, you should capture a specific case where the code doesn't do what you want, write down all the inputs and work step by step through the computation, verifying that your understanding of what's going on matches what the program is doing.

Feel free to post a specific example (a, b, g, h, r and bullet_speed) where the code does the wrong thing and I'll help you understand the situation.

##### Share on other sites
while hunting down an example for you, i noticed that changin it to 250 iterations results in all invalid t# values beeing reported as -1.#IND which is what i want it to do... although it would be quite a problem if i would have to do 250 iterations just to get this ansvear [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

##### Share on other sites
ok i have an ansvear for you. EVERY location that is "behind" the target will miss.

you can picture it like this :

if the radius is a line going on a graph from 0,0 to 0,2
the targets direction is negatively along the x axis
then every location inside the aproximately 135 degrees between that and a line between 0,0 and 1,-1 will miss.

and, the higher the number of iterations the smaller the amount of degrees becomes.

@ 25 its like about 110
@ 50 its almost 90
@ 100 its like 10 or somethin
and @ 250 there is nothing wrong left. only negative numbers and correct ones

##### Share on other sites

This topic is 2255 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account