• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
noobnerd

Advanced motion prediction ( 2D ) help

26 posts in this topic

[size="2"]advanced motion prediction:[/size]

[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"]Please help[/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]
0

Share this post


Link to post
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.
1

Share this post


Link to post
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?
1

Share this post


Link to post
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.
1

Share this post


Link to post
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
0

Share this post


Link to post
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]
0

Share this post


Link to post
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]
1

Share this post


Link to post
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
0

Share this post


Link to post
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".]
1

Share this post


Link to post
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.
1

Share this post


Link to post
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]
0

Share this post


Link to post
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
1

Share this post


Link to post
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]
0

Share this post


Link to post
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?
1

Share this post


Link to post
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]
0

Share this post


Link to post
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.]
1

Share this post


Link to post
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?
0

Share this post


Link to post
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.
1

Share this post


Link to 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?

well here is a download link for a .rar containing a test app that i made. [url="http://forumfiles.thegamecreators.com/download/2276186"]HERE[/url]

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
r# = radius
v# = velocity
x1#,y1# = coordinates of target
g# = radiuss initial angle
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 ...
1

Share this post


Link to post
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.
1

Share this post


Link to post
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]
0

Share this post


Link to post
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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0