Well, I''m not sure it this really belongs in AI but it seems to fit the bill close enough. Ok, so, you have two objects in space moving about and one wants to shoot at the other, only the projectile doesn''t have an infinite, or even relatively large velocity. If you simply point a barrel of a gun straight at the target and shoot, the projectile will miss the target because the target has moved since the time the projectile was shot and when the projectile gets to where the target was. We as humans understand "leading" a target from intuition and experience. Throught the football ahead of the reciever so he doesn''t have to stop running etc. I was wondering what people here thought the best method was in order to tell the computer/allow the computer to know where to point it''s guns. While I''m by now means, a proficient programmer, I do have a substantial background in math and I''ve come up with a couple of methods of doing this. These are at: http://www.students.uiuc.edu/~mjaworsk/Article.html I would greatly appreciate feedback, critique, insight etc on these methods and others that people here at GameDev might have. Thanks in advance. -Division-By-Zero

The AI is going to have to determine two things about the moving target: the direction it's moving and the velocity. It already knows the starting x,y position when it's time to decide to shoot.

The AI would then make a (linked-)list of x,y positions over time(with increments of 0.5 seconds for example).

Now comes the tricky part -
the AI has to know the velocity of its projectile. So at each point on the list, it has to calculate the time of flight of the projectile to that point(subtract the time to rotate the AI figure for the correct angle). Go thru the list and find the closest match.

1) if the error is too great between 1 point and the next decrease the increments with increments of 0.2 seconds
2) if the times don't match you are going to have to move your guy up especially if it's a low-velocity missile.

When it comes to a more mathematical approach with exact formulas, you're probably going to be looking at velocity vectors and working out the angles between the target and AI.


ZoomBoy
Developing a 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor, diary, 3D Art resources at
Check out my web-site


Edited by - ZoomBoy on August 14, 2000 2:33:32 AM

Thanks for the input on that method, I was looking for more than one solution, however, that method seems a bit CPU intensive and memory expensive having a list like that.

I had already worked out an iterative method and an exact solution, I was hoping someone out there could look at it and double check my work, etc. Perhaps even point out errors or improvements.



"The most merciful thing in the world, I think, is the human mind's inability to correlate all of its contents."
-H.P. Lovecraft, "The Call of Cthulhu"

You might want to post links to your code or post some pseudo-code to get some feed-back.

ZoomBoy
Developing a 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor, diary, 3D Art resources at
Check out my web-site

I have been working on something like this.

they way I am attempting this is have the AI identify the target and wait a bit and retarget and then the points in the space form a line. The projectile is also a line (and/or parabola). Find the intersection of the rates, and that should be all.. other factors exist like gravity and if it is blocked or not

Can I write in html code into this reply field? So I can make links and whatnot here. Just wondering.

Well, I'll see if I can show the methods I have here in a presentable format so that the equations are understandable.
Both methods assume a local coordinate system which has zero velocity and you are shooting from the origin of that coordinate sys.

Ok, first the iterative method, here are the two main equations:

DeltaT[n] = abs(R_target + V_target*DeltaT[n-1])/abs(V_projectile)

ê_projectile=norm(R_target+V_target*DeltaT[n])

Where V_target is the target's velocity (vector)
R_target is the target's initial position.
V_projectile is the velocity of the projectile (scalar actually)
ê_projectile is the unit vector describing the projectiles direction
and DeltaT is the time it takes to reach the target.

Now, basically, these two equations work in the following manner. The computer "guesses" an initial time to impact (DeltaT[n]) by looking at the initial distance plus the distance it will have moved by DeltaT[n-1] (the last "guess") and divide that whole distance by the speed of the projectile you're firing. If you initialize DeltaT[0]=0 then you start from nothing but, if you iterate this equation enough, eventually it will converge provided there is a solution ( V_target / V_projectile )<1 is the main constraint I've found that will let you know if there is a solution. After iterating several times (the amount of iterations depends upon the above ratio heavily and to a lesser extent, the angle between the position and velocity vectors of the target), you can then apply the ê_projectile equation to determine where to point the gun. A lot of the side information on the behavior of these equations is on the page I put in my first post.

That's one method of iteratively solving the equations.

The other method is an analytical solution which is the following:

(V_target / V_projectile)* sin(theta) = sin(phi)

where V_target is the absolute value of the speed of the target and V_projectile is the speed of the projectile. Theta is the angle between R_target and V_target (obtainable from the dot product relationship between vectors) and Phi is the angle from the R_target vector along the direction of V_target that one must fire in order to hit the target. (proof and diagram again, on that page I listed above). In this case, if the left hand side is > 1, there is no solution. If you wanted to convert this Phi angle into a normalized vector in a cartesian coordinate system, this can be acheived by using the cross product of R_target and V_target as an axis of rotation for Phi with R_target corresponding to 0 degrees rotation and the component of V_target perpendicular to R_target being the direction of positive rotation. These define a new coordinate system and a simple transformation matrix would provide the new vector in whatever coordinate system you are working in, though, I haven't worked out the exact math for that one yet.

These are the methods I worked out. Like I said, I'm not really a programmer but I have math in my blood. It was something I was thinking about so I thought I'd get feedback here. HOpe this helps.

Ok, found out that I can put html in here, so, here's the figures and proof:





and now I can give a link to the Page that has all this info already.



Division-By-Zero

"The most merciful thing in the world, I think, is the human mind's inability to correlate all of its contents."
-H.P. Lovecraft, "The Call of Cthulhu"


Edited by - Division-By-Zero on August 15, 2000 4:23:36 PM

I'm not sure about your formula but there should be 4 answers in the correct formula to calculate the angle where to shoot. And it will not need any quessing nor iterating.
There are not 4 angles that actually hit the target, because 2 of the angles are in negative time. So 2 real angles in most cases.

If you're interested in the formula, I can send it here.
Or just solve this:

{Turret_particle_velocity*sin(a)*t+x_turret=Target_velocity_x*t+x_target
{Turret_particle_velocity*cos(a)*t+y_turret=Target_velocity_y*t+y_target

Just solve the a (=alpha) to get the angle you need to shoot.
Or solve t to know the time that will last to the target (if t is negative, the angle is no good).

-Hans

Edited by - Hans on August 17, 2000 11:39:04 AM