Timkin, thats exactly what i suggested. except i suggested using vector math and merely applying adding the scaled difference of the vectors. the yeilds exactly the same result except you dont need to deal with angles thus no need to use any trig functions which can be slow. the actual missle drawing could be done simply be using the current vector. it may not be perfect visually, but it will be close enough and players are not likly to notice. you could also just have it always face the target. though that may cause an undesirable look.

maybe my explaination was not clear enough.

some psudeo code:



you may want to normalize the target and missle vector before doing the subtraction. not sure which would give a better accuarcy or look that you want. try both ways out. this system uses the idea that there is a three axis thrust system. so actual angles are not required, so there is no gimble lock problem.

being that you are using pecentages of change. you should be able to use the percentage of change in the vectors and apply it for the different angles you require (ie the normalized difference of the target vector from the missile vector).


Gyzmo, good catch. i guess i should have suggested using everything reletive to the origin of the universe (whcih every one knows is at 0,0,0 ), heh.

[edited by - a person on June 30, 2002 7:04:00 PM]

quote: Original post by a person
maybe my explaination was not clear enough.

some psudeo code:

targetVector = shipPos-targetPos;desiredVector = normalize(missleVector-targetVector);newVector = missleVector +(desiredVector*missileAcceleration); 

That''s not what I was suggesting though...

I was talking about the relative velocity vector , which is

target.velocity - missile.velocity 

rather than a displacement vector

targetVector = shipPos-targetPos; 

Additionally, your method suggests that the missile can turn any finite angle in an infinitesimal time step. That''s not very realistic.

What I was suggesting above was in fact a homing behaviour, based on a proven technique of decreasing angle and/or distance to goal with each action. No need to constrain it any further than that.

You might also need to check your computation. I could be wrong (since you don''t explicity state what each vector is) but it appears that you are subtracting a displacement vector from a velocity vector in your second line. If this is the case, then you need to multiply the missiles velocity vector by the time it would take to travel the displacement distance, or divide the displacement vector by this amount to determine a velocity.

As for the use of trig... you don''t need trig to compare the magnitudes of angles!

Cheers,

Timkin

but you need trig to get the angles.


i think the part you are getting confused on is the defination of a vector. a vector contains two things. a direction and magnitude.

thus:
missleVector is the direction of the missile and its speed.
targetVector is the distance and direction to teh target from the ship.

thus subtracting the missile direction from the target direction gives the required change of thrust in each angle.

now you normalize this so its purley a direction (since the magnitude will be encompass the entire journey). you then multiple this normalized vector by a acceleration value, ie the turning velocity. you then add this to the missiles current vector. this will apply acceleration in that direction. thus the ship will turn only slightly. if the ship is going in the correct direction, it will accelerate the ship as normal.

there is no instant lockon like you suggest since we are scaling the vector required to be in perfect alignment with a smaller value that is less then the current speed. this ensures it takes time for the missle to make turns.

i suggested it may be more accurate to compare the normalize vectors (ie so its only direction and velocity dont matter). i have not tried each method out. i probably should, just to make sure things work 100% correctly.

the nice thing about vectors is that you get the magnitude in there for free so you can use it for nice optimizations of some of the calculations. for instance the desiredVector obtained before normalization is the EXACT thrust required to hit the target instantly. notice, this is thrust that we would add to our missile''s current movement vector. so scaling it to a reasonable value (ie normalize then apply the acceleration constraint) it works out nicly.

even yoru method requires the constraint of limiting the turning speed, just like mine. the only difference is that my method requires no angle calculations and automagically handles normal acceleration/deceleration through the desired vector. for instance you could change the system so that the ship accelerates at x velocity per time unit. you would then calculate the desired vector (ie scaled to the correct velocity and point where you want to go). you then take the difference of this vector and your current vector which you normalize. you multiple that vector by the x/time unit acceleration then add it to the currect vector.
viola the ship now accuartly handles movement in space with slower turning at higher speeds (ie inertia plays a role). though you will have to do a check on the magnitude of the difference between the desired and current vector and make sure its not smaller then your acceleration. if it is, then you should not "dirty" the magnitude through the normalize and and acceleration muitlply. instead use it as is, or have the system slow reduce the thrust gardually. in either case, if the cuurent velocity ever gets greater then the desired vector velocity, the ship will automatically slow down. though it may cause a stutter scenario (ie speed up slow up, then slow down, then repeat).

quote: Original post by Timkin
No offense intended to anyone, but going by what has been written, you all seem to have forgotten something rather basic about this problem! The only (abstract) action required of the missile is to decrease the magnitude of the relative velocity vector each time step.

Timkin, the OP didn''t ask how to turn the ship, see:

quote: I have coded a method which can turn the ship to face a point (given as a vector3); what I need is to use this, and the other info, to get it to fulfill A and B.

He asked how to move the ship towards the target. Both myself and ''a person'' have given him simple answers that solve his problem. Furthermore, the Reynolds paper I directed the OP to shows how turning rates may be implemented (if I remember correctly). It doesn''t get any more basic than ''seek''

Thanks for all the responses guys! Wow, its going to take me a long time to reply to them all.

Ill start with earliest first.


A person:
>well first off, a missile will have a max velocity due to limited fuel
Yes, this is indeed true. However, this max velocity is unlikely to be achieved during the missiles journey from the launching ship to the target, and as such is irrelevant to the calculations in question.


>5. you have a max velocity becuase of fuel limitations, you may ignore fuel limitations
>like most games, but even so you should still have a max velocity based
> on this, else your physics calculations will come crashing down on you as objects
>exceed a particular speed (since collision will get funky, overflows will start
> to occer, etc).

It is true, there is a max velocity due to the physics engine. But again, its so much greater than the velocity that a missile can achieve over the course of a normal flight (espeically when you consider were not much interested in missiles doubling back on thier path to hit a target theyve missed) that it is irrelevent, as it will not occur during the period we''re trying to deal with. Any calculations thus based on it will be erronoius.

>missiles will pick there target by selecting the closest target within a particular fov.
>laser guided missiles are have their target chosen by what the ship is locked
> on to (though the ship must keep the lock). thus the ship must make its initial shot
>facing the target.

Again, Im not sure this is strictly relevent to the question I asked, but anyway ships and missiles have full access to the positions of all other objects in the game state. Sure, you can argue its unrealestic, but thats the way it is. We can also posulate the idea of a targeting laser which is on a pivot, so it doesnt neccessarily have to point in front of you. So the ship doesnt have to shoot facing the target.

>you dont care about the targets trajector
It will be very hard to predict its position otherwise. We could have a missile that always just homes on the targets current position (and indeed, Id be happy if I got the maths to do that) but this would result in missiles always flying curves to their targets in, and would be inefficient. But Ill still be happy with it, so lets continue...

> instead you will find the delta vector from your vector to the target vector. this vector
>will represent the exact thrust
>change required to hit the target the next time step

Im a little confused by exactly what you mean here? when you say "thrust change" do you mean displacment? Ie, that it will give you the difference between your current position and the targets current position, as a vector relative to you? if so, I understand.

>since the missile has limited acceleration abilities, you would scale this vector to the
>amount of thrust the
>missile can use to turn. this is then added to the current missile vector to come up with
>the new vector in which the missile is now turned towards the target
>within the limits of the missile acceleration ability.

Ah, Im afraid youve lost me here? Id be really grateful if youd explain this again somehow, as im totally confused...

> the missile should have a max velocity
>similar to a ships max velocity to prevent the ship from escaping the missile if the firing
>ship is traveling at the same velocity as the target.

Velocity? things dont really have a max velocity in the game, at least none that counts for
interactions like this. As a result, acceleration, not velocity is the key factor.
Missiles have acceralations very much greater than ships to ensure they can hit them.
(smaller mass, higher thrust).

>if your game has real physics, it should be able to handle the vector math required. it
> also should be able to handle mulitple vectors per object. since you will
> have a current vector, desired vector, acceleration vector. the acceleration vector
> represents the difference of the desired and current vector. which is then
>normalized and scaled to the acceleration the object can handle. this makes the homing
> missile ai trivial to implement. since you only need to update the
> desired vector, and the physics engine should take care of everything else automagically.

Its quite seperate to the physics engine, but we do indeed have a vector3 utility class.
Multiple vectors per object are quite easy, the aicontroller class can instantiate them as it needs.
The phyiscs eng does need to know anything about them, apart from the ones that physical objects actually have due to their position/motion in space.

The engine, however, is not responsible for steering things. This is left to their AI. Which has to deal with things like desired vector and stuff. The physics engine is only
told that a given space ship is trying to thrust more or less, or roll pitch or yaw by an
amount.

thebolt00:
>speed of light which cannot be broken (according to
> Einsteins theory of relativity).
This is indeed true. And such an upper limit exists, however as discussed, it is irrelevent to the calculations in question, as it can not be formed before any practical time to target is exceeded.


Gyzmo
>AFAIK in real physics, there is no ''certain point in space'' everything is relative
Thats a big of an abstract comment! Dont see much relevence.. however, I disagree. You can
of course specify certain points in space - you just cant do it in absoulte terms. But you
can specify them relative to other points. So they are certain, given that the other point
is certain. And anything you can point to, if you like, has indeed got a certain point
(lets not go into too much detail here, but you see what I mean. Anyone mentioning heisenberg is in deep trouble.)


Timkin:
>The only (abstract) action required of the missile is to decrease the magnitude of the
>relative velocity vector each time step.

Correct me if Im wrong, and Im not 100% sure what you mean by relative velocity vector, but
assuming I understand, wouldnt trying to decrease it each time just lead to both things
sitting in space? No movement? (relative to one another) I dont see how this leads to
homing behaviour.

You talk a bit more about reducing the RVV, but I dont see how it is supposed to solve the
problem? I imagine youd want a relative velocity vector which always points from
the missile to the target, and try maximise it instead. Which is substaintally more
involved than minimising one, no?

a person:
> the actual missle drawing could be done
> simply be using the current vector. it may not be perfect visually, but it will be close >enough and players are not likly to notice. you could also just have it
> always face the target. though that may cause an undesirable look.

The actual missile is actually drawn by the quaternion representing its orientation,
how else would it be drawn correctly? Anyway, thats a graphics engine issue...


>targetVector = shipPos-targetPos;
> desiredVector = normalize(missleVector-targetVector);
> newVector = missleVector +(desiredVector*missileAcceleration);

When you say ship pos, I am assuming your talking about the vector representing the missiles current location.
surely you mean targetVector = targetPos - shipPos?
That will yield the vector of the target relative to the ship/missile, which I assume
is what your going for? This is important to get right, so please correct me if Im wrong.
Also, when you say Vector, Im going to assume you referring to velocity vectors.

> desiredVector = normalize(missleVector-targetVector);

targetVector is a position vector now. Which you subtract from a velociy vector.
Im assuming your using ship and missile interchangably. (!)
Im not sure exactly what desiredVector now contains, I dont understand the subtraction of
a position vector from a velocity vector well enough. It doesnt make sense to me,
and Id be grateful if youd explain it.
>newVector = missleVector +(desiredVector*missileAcceleration);

Could you also explain this line in a little more depth? You are multiplying the
vector, which is a velocity, times the acceleration. I see what your getting at here
a little bit, but isnt it a bit arbitrary to just multiply by acceleration to make it
bigger??
What am I supposed to do with "newVector"? is this the one I should now turn to face?
Im very confused with this solution.


Timkin:

Again, I still fail to see how attempting to reduce that vector will lead to a homing
behaviour.
I also do not understand fully how you mean to decrease the angle/distance, as you dont
give any method of doing that, or say which way a missile should turn in order to do that.
Obviously, the missile is trying to decrease the distance to its target. What I am seeking
is a _way_ of mathematically determining the vector it should follow in order to best
decrease that distance.
I suppoes it could try turn various ways, and attempt to see which ones give the best
results over time, but this would be difficult, as a missile moving with momentum in
the wrong way could try turn towards the correct vector it should follow, thrust, and be
even further from the target.
I guess you could implement a solution which deals with decreasing momentum/velocity in
an undesirable direction, however there is no advantage to that over just turning to face
the right direction - namely we still have to work out what that direction is, the original
question asked!

a person:

>but you need trig to get the angles.
what angles, please? Also bear in mind I already _have_ a turn to face vector method,
which Im very proud of, it having taken hours of work. I need an intercept target method,
which relies on discovering which direction to turn and face, based on velocities and positions.





>i think the part you are getting confused on is the defination of a vector. a vector
>contains two things. a direction and magnitude.
>thus:
>missleVector is the direction of the missile and its speed.
>targetVector is the distance and direction to teh target from the ship.

>desiredVector = normalize(missleVector-targetVector);

Yes, but that doesnt mean it makes sense any time you automatically subtract one
vector from another! If I represent population growth as a vector, and
raspberry jam density as a vector, it doesnt mean the resulting quantity makes sense!
And I believe thats a bit like what youve done.
You take a velocity vector, "missileVector" and a position vector (relative to the missile)
and just subtract them... thats fine, but in the context of your method I cannot see
how it leads to a desired vector.
Again, I may be utterly wrong here, I would glady be corrected, as I just want a solution...
I would be indebted if you could please explain it a little more detail so I can understand.

>thus subtracting the missile direction from the target direction gives the required change
>of thrust in each angle.

Change of thrust in each angle? huh? What angles!? where did we get the angles from?
>acceleration value, ie the turning velocity.
I dont understand how acceleration in this context has anything to do with "turning velocty"
In fact I dont even understand "turning velocity" do you mean the angular velocity at which a ship can turn?
Ill be happy to assume that its infinite (as the constant correction of
course neccessary due to finite turning speeds should have a minimal impact on trajectory.
ie, the missile should be facing mostly the rigth way most of the time anyway, and corrections
need be small compared to the disance covered.)

I dont really understand your method; Im not bad at this sort of thing, please bear with
me and explain it in a little more detail.


fup :



> He asked how to move the ship towards the target. Both myself and ''a person'' have given
>him simple answers that solve his problem. Furthermore, the
> Reynolds paper I directed the OP to shows how turning rates may be implemented (if I >remember correctly).
> It doesn''t get any more basic than ''seek''

I still dont think ive seen a solution that deals with my particular problem, for the
reasons stated.
Your right, the problem is just to move towards the target. But a major part of that is dealing with your own intial momentum as you attempt to move towards it. And the optimum vector to reduce your momentum, and
move you towards the target at the same time, will depend on the distance to the target.
Which will depend on the vector. Im still stuck here...


Think about this:
If you always try turn to fact the target, and the target moves _at all_, or you arent point towards it at the start, and you dont have a way of dealing with your own momentum, your going to miss.
Not good homing code.
I still need to solve this problem.

Feral.

One thread that you may find useful is an old one entitled "How to lead a target?" Applying some of the equations there (specifically check the last post; I gave a solution there by solving simultaneous parametric equations and then putting them back into vector form) will help you to "cut corners" off your target's path to close the distance.

Your first goal in order to do this seems, realistically enough, to be designing a MoveToPoint function.

For your MoveToPoint function, you could use a variation on Timkin's idea: Just reduce the missile AI to a discrete set of actions, and build a search tree to find the best sequence of n actions to perform in a given timestep. By "best" I meant the set that points the missile in the desired direction, compensating for momentum. This forms your MoveToPoint function.

I understand, however, that you want a closed-form solution to the MoveToPoint problem, and I understand the feeling. So I'll give it a shot.

Your "goal vector," V , for your MoveToPoint function is a force. It has two components. The first, R cancels the momentum. We know the direction of R (just negate the current velocity), and the magnitude: divide the current speed by the length of a timestep; then multiply by the mass of the missile. The second component, T , moves toward the "target point." Therefore, the "goal vector" can be expressed as T +R The missile can thrust, exerting a force of magnitude k . The "goal vector" must be of this magnitude. Therefore, |T +R | = k . What we then need to do is first solve for the magnitude of T (since we know its direction - towards the "target point") using this last equation, and then add T to R to find V . I'll give these equations a shot in a little bit; I figured I'd post my gameplan in case somebody else wanted to save me the trouble!



[edited by - TerranFury on July 1, 2002 5:39:00 PM]

There's a fairly decent chance that I screwed this up somewhere, but here goes: Solve for variables sequentially and plug into the next equations.

O is the initial position, P is the target point, V is the "goal vector," and k is the missile's thrust magnitude. Everything else is either a variable used simply in an intermediate step or should (I hope) be self-explanatory.

R = (-Velocity *Mass )/timestep
A = normalize(P -O )
Z = (R * R ) - k 2
Y = R * A
X = A * A
M = (-Y +/- sqrt(Y 2 - 4XZ ))/(2X )
T = A * M
V = R + T

(Crossing fingers and hoping there were no math errors)



[edited by - TerranFury on July 1, 2002 5:37:55 PM]

[edited by - TerranFury on July 3, 2002 11:56:58 AM]

quote: Original post by a person
i think the part you are getting confused on is the defination of a vector. a vector contains two things. a direction and magnitude.

ROFLMAO

'a person', I've been teaching mathematics to university students for a long time now, so I'm fairly confident that I understand vector mathematics.

quote: Original post by a person
missleVector is the direction of the missile and its speed.
targetVector is the distance and direction to teh target from the ship.

thus subtracting the missile direction from the target direction gives the required change of thrust in each angle.

As feral kindly pointed out, your subtracting apples from oranges and what you're getting is lemons! You yourself noted that vectors (in one representation) have a magnitude and direction. That magnitude has units... and you have to preserve units when performing mathematical operations... your equations don't do that. You have the right intent... to determine a direction in which you should produce thrust... but you go about it in the wrong way.

quote: Original post by a person
but you need trig to get the angles.

No, you don't need to know the specific values of the angles to compare their magnitudes. Have a think about how angles are defined and if you still cannot see the answer, I'll happily explain for you.

quote: Original post by fup
Timkin, the OP didn't ask how to turn the ship, see:

No, he asked in what direction. I noted that and gave an answer that reflected the question.

quote: Original post by feral
Im not 100% sure what you mean by relative velocity vector

I gave a definition in my last post. Relative velocity is the velocity of 1 object relative to the other. So, the velocity of the ship relative to the missile would be given by:

Vtm = TargetVelocity - MissileVelocity  

quote: Original post by feral
wouldnt trying to decrease it each time just lead to both things
sitting in space? No movement? (relative to one another) I dont see how this leads to homing behaviour.

You're limiting your mind! Decreasing the velocity means decreasing its magnitude... and negative numbers are less than zero. If the relative velocity is negative then the target is moving toward the missile, in the missiles frame of reference!

Take a look at the predator-prey simulation I did a long time ago. It is this exact same problem... trying to catch a moving target. The thing you can ignore about the simulation is that it is an example of machine learning... where the predator had zero knowledge of how to catch the prey before it started moving. The predator used just two measures to drive its pursuit: decrease angle to prey/decrease relative velocity of prey.

Now, you don't need to do machine learning to implement this behaviour. It could be coded in a closed loop form with pre-coded rules, which is what you seek. I merely suggested the quantities (in this case angle to target and relative velocity of target) that you should seek to minimise in choosing your actions.

You suggested that I didn't provide a method to do this... I did.

You could solve analytically the required direction to apply a limited force to change the direction of the missiles motion... or you could simply perform a quick search of the possible directions and return (the) one that decreases the angle to target and relative velocity of the target. This was the whole point of my original post: a novel alternative to the analytic solution.

Regards,

Timkin

[edited by - Timkin on July 1, 2002 8:13:23 PM]

i am so glad i actually tested my code this time (it is an interesting topic).

just because you teach vectors dont mean you can "see" some of the more "obsecure" ways of using them. i thought my method was straight forward. i will give another go at an explaination, hopefully it will make sense.

yes i i accidently used ship and missle interchangably. typing ship is shorter and in the back of my mind i was thinking of how to implement this in the small space demo thing i implemneted a while back. basically some ships (well triangles) in space that just sit there. one ship can be moved by the player and collision detection (uses bound boxes) is handled. the physics part of the code allowed ships to collide, and accept force in a somewhat realistic fashion (i cheated since it does everything based on points so the angle of the hit wont change the ships orientation). i figured since i was moving the ship via vectors i would try my technique. amazingly it works perfectly. so fortunatly for feral, he wil have some homing missiles that he can tweak.


here we go again:



understand yet?

its quick and simple. missile behavior is quite nice as well. if the user turns, the missile will choose the shorter path automagically. it is IMPOSSIPLE to shake the missle if it accelerates beyond the ship speed. remeber the missile is always try to go the shortest distance between the target and itself (ie the straight line) making the target who using turns quickly killed by even a missile moving at half the targets speed.

this could be upgraded by just figuring out a better target position and using the same exact technique. you could try and lerp the targets nect position using linear or spline extrapolation. so instead of targeting the target, you target a point on the targets path. thus it could be more optimal. in either case the guts of the actual caclulation (ie the important part) of the missiles desired vector is the same.

[edited by - a person on July 2, 2002 2:04:47 AM]

quote: Original post by a person
just because you teach vectors dont mean you can "see" some of the more "obsecure" ways of using them.

There''s no need for this sort of remark in this forum. You seem to have taken offense that I found fault with your mathematics and some how have inferred that I don''t understand what you are trying to do because of that!

I understand what you are trying to do perfectly and at no time did I say your method would not work... only that the maths you showed to achieve this was incorrect. Perhaps you should go back and re-read my posts if you think this is not the case. Indeed, I even provided the correction in my first post to make your method work.

This is a point for everyone reading... people make mistakes... I''ve made mistakes in the past... and I''m always happy to have them pointed out and to apologise for them.

Just because someone points out a mistake doesn''t mean they''re putting you down, or suggesting that you don''t know what you''re on about. They''re merely assisting by ensuring that others are not given incorrect information.

Please everybody remember this when posting.

Thank you,

Timkin