It's disparaging that you'd think we'd flame you simply because you're having trouble understanding something That's what we're here for; our only beef is against people looking for free homework answers. Grr.

Anyway, although it may seem as though this problem can be solved using triangles, you have to remember that you're working in two different scales - position, and change in position per unit time. As you know, the latter directly affects the former, so what happens is that your triangle changes shape as time goes on, and as you can imagine it becomes difficult to examine the problem from a purely geometric point of view because of this "shifty triangle" that can throw you off. Think of it this way. Let's say Bob travels 100 miles in 2 hours, Stan travels 200 miles in 4 hours, and George travels 350 miles in 7 hours. They all traveled different distances , but they all had equal average velocities (just assume they went the same direction since velocity is a vector quantity). As you can see, velocity can be very tricky. Rates of change tell you just that, how much something changes, but doesn't tell you anything about what the actual values were. Once you take Calculus this will all have a much more solid foundation.

Instead, what I've always liked to do is think of the problem in three dimensions. It may seem as though this only complicates the problem, however it really makes it tons easier to visualize, and eventually solve once the image is clear. The three axis are X, Y, and Time! All you need to do is then map the position and motion (since you have all the axis to do this) in 3D space, and it becomes amazingly clear what you have to do. Now, keep in mind that you have to know at least three of the variables in order to find the fourth (these four variables refer to the speed and angle of both projectiles. Velocity is implicit of two of these variables, so if you also have a speed, then you're set). From what I understand, you have the velocity of the player and the speed of the bullet. Great. What we have to do is map this into 3D space.

First the player. Remember that our XY plane is for position, while the Z axis is for time. As time goes on (i.e Z value increases), the XY position is going to change. In our 3D space, this would be a line. Now for the bullet. We have the speed, but no velocity. This means that we don't know what direction the bullet needs to travel in. What's the first shape that comes to mind that has a definite distance, but no definite direction? A circle. However, speed also changes the XY position of an object. So what you have is a circle that increases in radius as time (i.e Z value) increases. In the end, the shape is an inverted cone. Another way to think about this is the same way we thought of the the player. The bullet could also be represented by a line, however we don't know the angle. So it can be seen as a line that "swivels" around a vertical axis, also tracing the shape of a cone.

Your job now is to find the intersection point(s) between the cone and the line. I use the plural form because there are actually might be two different directions you can fire the bullet in and still hit the player, since a line can intersect a cone at two different points as well (once to go "in" and once again to go "out"). You'll probably want to use the first point, because it will have the lesser Z value, and hence would take less time to hit the player.

The only question that remains is how to find the intersection! This will require some slightly complicated 3D procedures, however the theory is nicely covered here. Code can also be found here (search for line cone intersection), however you may need to also download the support classes for the cone and line. You might be able to write your own version without the classes.

Once that is finished, you find the angle between the intersection point(s) and the bullet's starting location (just using the X and Y coordinates. The Z value tells you how long it will take, if you're interested in that). To find the angle from X and Y values, take the arc-tangent using the atan2 function so the signs of the coordinates are taken into account. Remember that the range of this function will be -PI to PI. You can transform this to a 0 to 2PI range by adding 2PI to all returns values less than 0.

And lastly, some information you'll need for the line/cone intersection code. The vector (Player_XVel, Player_YVel, 1) is the direction of the line. Normalize it for use. The document should explain everything else you need to know.

It may not all make sense, but this problem is complicated to solve explicitly. There is always a step-based algorithm you can use, but it won't perfect. Your results will depend on the step values, which affects the speed of the process.

If you want to hear about simpler but maybe slightly less accurate methods, then just say so and I'll see what I can do

[edited by - Zipster on August 7, 2003 5:39:42 AM]

quote:Original post by Siaon
I might have misunderstood your problem, but can''t you simply cook up the proper y=ax+b formula''s for both projectiles, then check if they collide?

f(x)=a*x+b
g(x)=a*x+b

f(x)=g(x)

to see if those lines cross.

(if the a*x parts are equal to eachother they will not cross)

[edited by - Siaon on August 7, 2003 5:51:46 AM]

Unfortunately, it isn''t that simple. Although I wish it was, because it certainly does seem like it should be

A step method would be a good choice. However, depending on whether or not the bullet''s speed is always greater than the player''s speed, you may or may not need to make extra considerations. The problem is that the line can intersect the cone at a maximum of two points, yet that still means it can either intersect at one point and skim the edge, or at zero points. If the bullet is always faster than the player, then that means that the player will never be able to escape, and the bullet will always hit the player even if he''s traveling at the maximum relative velocity (i.e straight away from you, not at an angle). You don''t have to worry then, as this implies the line will always intersect the cone. Otherwise, you have to worry that the step method will degenerate into an infinite loop if there is no collision, or begin to work improperly due to a single collision, at which point the line is inside the cone for only a infinitely small period of time (a point). Your line-in-cone checks would require higher precision to work correctly, which hurts the performance of the procedure.

In either case, your best bet it to develop constraints based on the contextual situation of the victim (and maybe the shooter). A good constraint is a wall, where the victim is forced to change direction. You look ahead along the victim''s velocity vector, and check for walls. Let''s say you find a wall 100 units ahead along the velocity of the victim. Knowing the speed (25 units/second say), you can calculate how long it will take before the victim is forced to change direction (4 seconds, lest he hit a wall and stop moving, making himself the ultimate target ). This time will be the greatest Z value you check when doing the line-cone collision, because any calculation made past that Z value is automatically invalid. If you have a perfectly closed world, where there is always a wall in front of a victim at any distance, then you will always have constraints. Naturally there is a direct relationship between the distance to this wall and the time it will take to find the firing angle with the step method, but there are ways to cut that time down as well.

I also took a closer look at that line-cone intersection code I linked to, and I''m quite confident that speed won''t be an issue. Large portions of it are mutually exclusive execution-wise (due to conditionals), there aren''t any loops, and since you don''t have to use any of their objects you can eliminate function calls (although I''m sure they were inlined anyway ). I saw a single square root, a few dot products and a cosine call.

I would suggest you use the code I provided, and see if it''s too slow. It seems like it''s optimized enough so it won''t be a speed issue, and it''s accurate. If it turns out to be too slow though, the go to the step method. However this can also take long depending on how far that wall distance is, and the size of your step. I''d venture so far as to say that it would be slower than the explicit solution in most cases. But worse come to worst, use a combination of both, using the step method for small distances and reverting back to the explicit method for larger distances (or vice versa, depending on your speed tests).

I found a better explanation here regarding the line/cone intersection test. It basically takes the parametric equation of the line and plugs it into the implicit equation of a cone, and solves for the parameter. A quadratic equation is made, and we can solve using regular formulas. All you have to do is accommodate for different cone angles and positions, but that's simple enough. Given the location of your cone (Cx,Cy,Cz), and the speed of the bullet S, then you can use the following implicit equation for the cone:

(x - Cx)2 + (y - Cy)2 = (z - Cz)2S2

The link will provide the rest of the information for the line. Plug in and solve. You might want to expand some of the math yourself on paper first. In the end though, I think that the code provided by Mr. Eberly will be the best, since it's probably makes use of mathematical shortcuts in the process we are unaware of. At least you will have a better understanding of one way this is accomplished.

quote:And I can guess how I would conver VelocityX and VelocityY into and angle, which was in my original question. Would it just be like checking the angle between point 0,0 and VX,VY with atan2?

That's exactly right (it's assume you are checking from the origin). However you have to keep in mind what atan2 returns, a radian angle in the range -PI to PI.

[edited by - Zipster on August 9, 2003 6:19:06 AM]

Actually, the triangle method works perfectly, but it takes a little more than subtracting an angle from 180 degrees.

Consider triangle A (shooter) - B (enemy) - C (intercept location) where C is unknown.

We know the vector A->B, and we know the direction of B->C (ie. we know the angle CBA). It''s fairly trivial to find an angle (BAC) such that |A->C|/bulletspeed = |B->C|/enemyspeed (for all "possible to hit" configurations; if the enemy is faster than the bullet, it may fail)

*If* I remember correctly, the entire thing simplifies down to something along the lines of:
sin(BAC) = sin(CBA)*enemyspeed/bulletspeed

I used this method in Strange Adventures (for the better battle computers) and it does hit the target every time if it''s stupid enough to go in a straight line: http://digital-eel.com/sais/

This question is the topic of one of the articles in Game AI Wisdom. If you don''t have the book and can''t afford it, you might be able to read it at a bookstore.