Archived

This topic is now archived and is closed to further replies.

a1studmuffin

Vector prediction

Recommended Posts

a1studmuffin    122
I''m in the midst of a 3D Asteroids game (http://www.4bitterguys.com/michael/asteroids - source available) and am working on a heads-up-display for my cockpit which places a green rectangle around an object and a red rectangle where the pilot should aim for if he wants to hit the asteroid with a laser, like this: Now, when a laser is fired, its speed is set as the ship''s current speed + 2 units. So, I have the following variables at my disposal: sS - Speed of the spaceship (scalar) vS - Vector of the spaceship''s movement (unit length vector) pS - Position of the spaceship in world coordinates (vector) sA - Speed of the asteroid (scalar) vA - Vector of the asteroid''s movement (unit length vector) pA - Position of the asteroid (vector) What I want to find is: pT - Predicted position of the asteroid by the time a laser arrives to that point. Currently I''m using a simple "distance = speed / time" ratio multiplier but this makes the assumption that the asteroid is not getting closer or further from your ship, which is bad. I can almost *taste* the calculus involved (the force tells me it will involve a derivative) but I just can''t quite get my head around it - it''s been awhile since I did maths at university! Any help would be greatly appreciated!

Share this post


Link to post
Share on other sites
koji187    122
in case you didnt know distance=speed*time

with proper substituion(not sure about speeling) u can solve equations to get the time and hence the distance (desplacemt from postion to new)

Share this post


Link to post
Share on other sites
a1studmuffin    122
Hahaha, sorry. d=s/t was a typo, I''ve meant d=s*t

But the problem I have still stands.

Things are easy if you assume that the asteroid is travelling in a perfect orbit around the spaceship, because then you can calculate the time it will take the laser to travel to the asteroid (seeing as it will be the same value no matter how far the asteroid travels, since it will always be the same distance from the ship) and then you can substitute it back in to find out how far the asteroid actually will have travelled in that time.

The tricky part is if you allow the asteroid to be moving on any straight-line trajectory, since to calculate the laser''s travel time, you need to know how far the asteroid will have travelled, and to calculate how far the asteroid will have travelled, you need the laser''s travel time

I think it''s a simultaneous equation but I can''t work out how to solve it. Again, any help from anyone would be greatly appreciated!!!

Share this post


Link to post
Share on other sites
Cedric    158
There was a similar thread about a month ago that was about shooting a moving target, and knowing at what angle you must shoot. Look at the archives.

Here's my take on the problem:

First of all, the speed of the ship is not really useful, because all we really care about is the speed of the laser (btw, isn't setting the speed of the laser, ie.: a light beam, to speed of the ship + 2 in contradiction with relativity? whatever)

Speed of the laser: sL (vector)

We want to know the position where the laser and asteroid will collide, and when: (I'm using only vectors: sA is also a vector --- don't use your conventions/optimizations when posting here)


P = pS + sL * t
P = pA + sA * t

pS + sL * t = pA + sA * t (first equation)
pS - pA = (sA - sL) * t
t = pS - pA
-------
sA - sL

You have to express sL's direction as a function of pS, pA and sA.

Hmm... I'm sorry, but I should be working now and I don't feel like finishing this problem (I didn't think it would be that long), although I can outline what I think is the solution. This may look like a 3D problem, but it really is 2D because you only have to solve a triangle. Its sides are pA - pS, P - pS and P - pA. You can find the angle between P - pA and pA - pS with the dot product. Using this angle and the law of cosines, you can find a second equation. Since you have two unknowns in sL' vector (remember, it's a 2D problem; you have to toy with the equations), then you should be able to solve your problem with these two equations.

If I have more time today, I'll finish it myself, but right now, I don't. Sorry.

Cédric

[edited by - cedricl on May 2, 2002 9:45:25 AM]

Share this post


Link to post
Share on other sites
a1studmuffin    122
Thanks a lot Cédric. I've spent some time going over the problem.

I'm still confused, but your post DID clear a lot up.

Since what we're dealing with is a triangle in 2D, we can work out the length of line pA - pS, and also the angle between lines pA - pS and p - pA. From here we still have 2 unknowns (as you mentioned in your post). How do we go from here to a solveable equation? The law of cosines?

Sorry to bring it back on you again, I'm tearing my hair out trying to figure it out!

[edited by - a1studmuffin on May 2, 2002 10:26:14 AM]

Share this post


Link to post
Share on other sites
Cedric    158
No problem! Actually, if you can solve the problem by yourself, all the better! I'd rather answer short questions than write the answer completely.

Again, I'm not sure that you will be able to solve analytically with my approach, but we can try

When I wrote my original post, I thought that the x and y components of the vector would be our two unknowns. That was wrong. Our two unknowns are theta (the angle between pA - pS and P - pS) and t. There are two useful laws to deal with scalene triangles:

If A,B,C represent the angles of a triangle and a,b,c its sides (a is opposed to A), then


a² = b² + c² - 2bc*cosA
(similar for b and c)

and

a / sinA = b / sinB = c / sinC


Using these two laws, try having nothing but known quantities and the variables theta and t in your two equations. The law of cosines is useful if you know only one of the angles of your triangle. In your problem, you know the angle between P - pA and pA - pS. If you have problems solving, post again and we might be able to find a solution.

I think you might have misunderstood me when I said that the problem was 2D (and what I said wasn't entirely clear either). We're not going to deal with vector components here. The reason why the problem is "2D" is that the vector P - pS is in the same plane as sA, pA and pS, so it's kinda 2D because we're in a plane.

Cédric

[edited by - cedricl on May 2, 2002 11:10:51 AM]

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by a1studmuffin

So, I have the following variables at my disposal:

sS - Speed of the spaceship (scalar)
vS - Vector of the spaceship''s movement (unit length vector)
pS - Position of the spaceship in world coordinates (vector)
sA - Speed of the asteroid (scalar)
vA - Vector of the asteroid''s movement (unit length vector)
pA - Position of the asteroid (vector)

What I want to find is:

pT - Predicted position of the asteroid by the time a laser arrives to that point.



If you write the asteroids motion as a set of parametric equations, of the form x = A(t-t0) + B, (A is a column vector (matrix) of velocities and B a column vector of intial displacements (at t0) then you can predict the position of the asteroid at any time t by simple substitution.

Furthermore, if you write out a similar set of equations for the bullet (based on the spacecrafts motion) then you can solve the system for the time of intersection of the two paths.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Timkin    864
Oh, one tiny aesthetic point about your HUD. You might consider adding a thin line between the centre of the green box and the centre of the red diamond. Why? Because this line represents the projection of the objects path into the 2-D visual plane of the viewer and helps with targeting when the object is not moving linearly (i.e., the line moves as well). Combat HUDs use this method to give additional information to the pilot.

Of course, if your asteroids are always moving linearly, then you could ignore it.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
_SHO_NUFF    122
I don''t think that simple substitution will work.

In the soluitnos above, ppl use the laser vector like they know what it is, when all you know is its magnitude.

There''s about 10 different solutions on an old thread called "leading a target". Just go there. look it up right now.

Share this post


Link to post
Share on other sites
a1studmuffin    122
Thanks Timkin and _SHO_NUFF, I've just looked up the older thread (http://www.gamedev.net/community/forums/topic.asp?topic_id=88047) and was reading through it, and it almost looks to me like the recursive approximation function that was suggested there will be as fast (if not faster) and a lot easier (from a programmer's perspective) than calculating the exact intersection point.

The solution in that thread that looked the most fitting to my situation was this one:

quote:
Original post by TerranFury
Here it is (A = target; B = bullet; k = bullet speed). Just solve for each variable sequentially and plug it into the next equation.

D = Ainitpos-Binitpos
E = D * D
F = 2(Avelocity * D)
G = k2 - (Avelocity * Avelocity)
t = (F + sqrt(F2 + 4GE))/(2G)
Bvelocity = D/t + Avelocity


What I don't understand about this solution is what is a vector and what is a vector length? There's no indication of |Ainitpos| for length of the vector and Ainitpos for the actual vector, so it makes it a little confusing to interpret. Any demystification would be appreciated :-)

Also Timkin, in regards to your suggestion of a thin line between the green and red rectangles, while my asteroids are travelling in a straight line, I think your suggestion is still a worthy idea and I'll probably implement it since when the screen has about 4-5 asteroids and a few martian spaceships on it, things can get a bit cluttered Not to mention the martian ships, just realised they move all over the place. Is the connecting line normally curved to indicate the projected trajectory of the targetted object? Time to do some military research

[edited by - a1studmuffin on May 3, 2002 3:53:20 AM]

Share this post


Link to post
Share on other sites
a1studmuffin    122
I''ve just implemented a recursive approximation function for DirectX, which takes as input:

bpos = Bullet position
bvec = Bullet vector
tpos = Target position
tvec = Target vector
iterations = The number of iterations to calculate (a higher number increases calculation time linearly, but only adds increasingly smaller corrections to the result - a good number to use from experimentation is 6. For more accuracy, increase the number. For faster calculations, decrease it.)

This function returns as output the predicted position of the target by the time a laser would reach it.


  
D3DXVECTOR3 targetLead(D3DXVECTOR3 bpos, D3DXVECTOR3 bvec, D3DXVECTOR3 tpos, D3DXVECTOR3 tvec, unsigned int iterations)
{
D3DXVECTOR3 distance;
D3DXVECTOR3 solutionpos;
float time;
solutionpos = tpos;
while (iterations > 0)
{
distance = solutionpos - bpos;
// Protect from divide-by-zero errors:

if (D3DXVec3Length(&bvec) == 0) return tpos;
time = D3DXVec3Length(&distance) / D3DXVec3Length(&bvec);
solutionpos = tpos + tvec * time;
iterations--;
}
return solutionpos;
}


Hope that helps anyone who''s having a similar problem, it''s working an absolute treat for Asteroids.

Thanks to everyone for their help

Share this post


Link to post
Share on other sites
a1studmuffin    122
On a side note, this function is working *excellent* to use for the AI''s aiming. And the best thing is the iteration variable makes implementing difficulty levels incredibly easy, as one can just set the iterations to a lower value for an easier skill level so that the AI has worse aim. Brilliant

Share this post


Link to post
Share on other sites
Timkin    864
Good to hear everything is working well for you!

As for the line between the object box and targeting box... just make it a straight line. This line then represents the 2D projection (in the plane of the viewer) of the linearly approximated trajectory of the object. If the object is moving non-linearly, then successive applications of your targeting AI will show the line to be moving (changing slope as it moves across the screen). This tells the pilot that the object has a non-linear trajectory and he/she can factor this in to the likelihood that shooting at the targeting box will hit the target (i.e., don''t shoot there until the line stays constant).

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by _SHO_NUFF
I don't think that simple substitution will work.

In the soluitnos above, ppl use the laser vector like they know what it is, when all you know is its magnitude.



Except that you do know the direction in this problem _SHO_NUFF... the missile has a linear trajectory along the direction of the ships velocity vector at the instant of firing... so the targeting problem is not the same as the one tackled in the 'turret targeting' problem that you are referring to.

quote:
Original post by _SHO_NUFF
There's about 10 different solutions on an old thread called "leading a target". Just go there. look it up right now.



... and in one form or another, they're based on the solving (or approximating the solution) of simultaneous parametric equations (be they in vector form or not).

Cheers,

Timkin

[edited by - Timkin on May 3, 2002 11:42:45 PM]

Share this post


Link to post
Share on other sites
TerranFury    142
quote:
Original post by a1studmuffin
What I don''t understand about this solution is what is a vector and what is a vector length? There''s no indication of |Ainitpos| for length of the vector and Ainitpos for the actual vector, so it makes it a little confusing to interpret. Any demystification would be appreciated :-)


I''ve been trying to find that thread! Thanks for the post!

Now to try to answer your question... I don''t take the absolute value of any vectors. Also, when I write a vector, I never mean its magnitude; I mean its vector. I end up with scalars like t because I use dot products (aka the scalar product).

For example, I''ll quote one part of my old post:
quote:

G = k2 - (Avelocity * Avelocity)


Although Avelocity is a vector, the quantity (Avelocity * Avelocity) is a scalar. The bullet speed, k, is also a scalar. In case it helps, here''s one tidbit: (V * V)=|V|2.

Just to make sure that everything is clear, I''ll add some notes to my old post and put it here:

quote:

Here it is [again!] (A = target; B = bullet; k = bullet speed). Just solve for each variable sequentially and plug it into the next equation.

Vector D = Ainitpos-Binitpos
Scalar E = D * D
Scalar F = 2(Avelocity * D)
Scalar G = k2 - (Avelocity * Avelocity)
Scalar t = (F + sqrt(F2 + 4GE))/(2G)
Vector Bvelocity = D/t + Avelocity



There you go. That, I hope, should make things clearer.

Share this post


Link to post
Share on other sites
a1studmuffin    122
Ahhh, excellent. Thanks a lot for that! If anyone wants to see this targeting in action, I''ve just posted the latest version of Asteroids (v0.94) on my website. You''ll also notice in later missions that the AI uses it, works a treat.

Interesting side note: one of my friends also mentioned that, since all my collisions are just sphere checks, I could use that same function to do collision detection.

Share this post


Link to post
Share on other sites
_SHO_NUFF    122
Timkin, what are you talking about. It''s the same problem.

And if you''d READ the posts, the one that *I* suggested, is the iterative one. The one that studmuffin used. There''s no solving equations on that. You just wrote a rant criticizing me for pointing him to the solutiong that worked for him, that I suggested.

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by _SHO_NUFF
You just wrote a rant criticizing me for pointing him to the solutiong that worked for him, that I suggested.



Firstly _SHO_NUFF, I did not write a rant. Nor did I criticise you.

Yes, they are in fact the same problem. I mistakenly looked at a different thread (not seeing the link in al studmuffin''s post). For that you have my apologies. That doesn''t change what I said though.

You are mistaken when you say that substitution will not work. Clearly if the asteroids position is given by a parametric function of time, then substituting in a value of time (which is what I said) will give you its position at that time. How can this not work?

Furthermore, what I said after that was that you can do the same for the bullet/missile and solve for the time of intersection. Of course I should have said solve for position, which is what al studmuffin was asking (of course, solving for the time necessarily gives the position and hence firing angle as well, by substitution!).

Yes, this is what your iterative method approximates. However, you should realise that for linear systems, the actual (general) solution to this problem is a trivial matter of vector calculus, which provides the bearing to the target point given the speed of the bullet and the trajectory of the object. I held off posting the solution since al studmuffin indicated he had a viable solution and hence there was no need. If however people really want to see the result (and the two line derivation... well, okay, 2 line derivation for the 2D case, and about a half dozen lines for the 3D case)) I would be happy to post it...

Cheers,

Timkin

Share this post


Link to post
Share on other sites
declspec    126
oh you got this one solved. darn i downloaded the source too.

this one wasnt so bad. once in a quake mod i tried to right the code for shooting a rocket at a falling object. that was nasty.

seems the same cept you got a constant rocket velocity but a constant acceleration on your target. the rocket is slow enough that the acceleration causes you to miss if you dont take it into account. never did solve the problem.

you have to picture being at the bottom of dm1 from q2 and shooting at someone that just jumped from the top. real life people know to shoot somewhere near the bottom. bots have to be told that. one way might be just average starting velocity and resultant velocity and guess. but i wanted exact numbers! got to remember if they are falling over you a small change of position can be a big change in firing angle.

basically i was going to redeem myself on this prob but its solved... shoot.

oh side message there is no meshes in the latest source. guess i should have known to download the game too.



Share this post


Link to post
Share on other sites
declspec    126
oh wait your using interations. mountain dew time there is still work here.. ill try to debug it myself then get back to ya =)

Share this post


Link to post
Share on other sites
declspec    126

ok i think i outlined a solution but i will need to test it cause its out there. no interations.

the idea is draw a line from the ship to the target call it R. now draw the targets velocity vector. mark the angle between the velocity vector "a".

now draw the missle vector as yet unknown but intercepts the target vector at some point. mark the angle between the missle vector and the R vector "b"

    
now note that
sin "a" sin "b"
----- = ----------
misslespeed targetspeed

thats according to the law of sines. all known cept for sin "b"

easy enough to solve for. then once you have it you do the rotation and your done. noting this all happens in a plane regardless of where its at in space.

but the math will be messy and i want to test it myself.

edit: got the files now they are fine. bad download.


[edited by - declspec on May 7, 2002 7:29:53 AM]

Share this post


Link to post
Share on other sites
_SHO_NUFF    122
I never said that parametric solutions wouldn''t work, you implied that in your post.

Also, did you read my first post? I said that you don''t know your firing direction. You said we do know it? I thought that''s what we''re trying to solve here? At the very least the time it takes..

I''d love to see a derivation of a trivial solution.

Share this post


Link to post
Share on other sites
Timkin    864
Actually, not quite declspec... since you drew a line between the ship and the object, that side of the triangle represents a distance... and the other two represent speeds... you need to scale the other two lengths by the time interval it takes the object to move from its position at t0 to its point of collision at time tc, if you want to apply the law of sines. Call this interval dt = tc-t0.

Then


sin(a) sin(b)
------ = ------
VBdt VAdt


Thankfully the dt's drop out and you get the same result... that

VA
sin(b) = sin(a)---
VB


This is the two line derivation I alluded to in my last post.

The time of intersection can be obtained by solving the law of cosines on the same triangle... giving
tc = t0 + P +/- sqrt(P2-|R|2)

where


VB|R|cos(b)
P = ------------
VB2 - VA2


and |R| is the length of the line R, between the ship and the object at t=t0.

Take the +ve solution for tc.

Now, in 3D, the problem is just as simple, since the lines VA dt, VB dt and R form a plane. Hence the bearing b is still valid as an angle of rotation in that plane.

At the time of collision, the asteroid will have a z coordinate given by

z(tc) = z(t0) + (VA .k )(tc - t0)


You can now either determine the x and y coordinates of the point of intersection in exactly the same way (substituting obviously the i and j basis vectors for k respectively) or you can determine the angle of elevation (gamma) of the target point, relative to the ship, from...


z(tc) - z(t0)
sin(gamma) = -------------
VBdt


Hope this helps,

Cheers,

Timkin

[edited by - Timkin on May 7, 2002 9:59:10 PM]

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by declspec
you have to picture being at the bottom of dm1 from q2 and shooting at someone that just jumped from the top. real life people know to shoot somewhere near the bottom.


Of course in real life, you aim directly at the falling object, because your bullet will fall the correct distance due to gravity that the target is falling and thus hit the target as planned!

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by _SHO_NUFF
I never said that parametric solutions wouldn''t work, you implied that in your post.




You said that substitution wouldn''t work. As to me implying it wouldn''t work, where on Earth did you get that idea? Could you find the line please and quote it so I can see what you''re talking about?

As to the issue of knowing the bearing, I already apologised for my misinterpretation of what you were saying. If you want to belabour the point go ahead... but I don''t see anything positive coming from it... and I wont join in.

Timkin

Share this post


Link to post
Share on other sites