Archived

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

jack_1313

The old intercepting projectile problem...

Recommended Posts

jack_1313    536
Hi all, I need help with the old ''fire projectile to intercept target'' (2d) problem... Wait!, before someone flames me for bringing up a repeated topic, know that I have read up about 5 other posts asking similar questions, and to put it simply... I dont understand this triganometory stuff. I have worked on this problem for several days, and it would be highly apreciated if someone can explain it to me in English! Even better, it would be GREAT if someone can offer some code, ie a C++ function that calculates a velocity sight based on the known variables, and considering that so many people have had this problem so many people must have code to solve it... Just to report what exactly I have come up with: float D=distance(thisSPC->x,thisSPC->y,player->x,player->y); float BS=4.5; vx=player->x + (player->VelX*0.3*(D/BS)); vy=player->y + (player->VelY*0.3*(D/BS)); float DD=distance(thisSPC->x,thisSPC->y,vx,vy); DD=DD/D; D=D*DD; vx=player->x + (player->VelX*0.3*(D/BS)); vy=player->y + (player->VelY*0.3*(D/BS)); int A3=angle(thisSPC->x,thisSPC->y,vx,vy); BS being the bullet speed. But this doesn''t work. The other thing that I thought was a triangle - I know one angle and the length of one side, and that one of the unknow sides equals TARGETSPEED/BULLETSPEED of the other unknow side. I thought that I could take the known angle away from 180 (180 degrees in a triangle) and multiply the result by TARGETSPEED/BULLETSPEED, but that didnt seem to work (could have just coded it wrong), so I gave up on that train of thought. Anyhow, got side-traked, but yeah... code would be great if anyone has any (which I am sure that they do). I''m doing yr9 at school and we havent started on sin and cos and tan although I have been using them a fair bit in programming at home, not that I could say what they do exactly. The only other question I have is given X and Y velocity values, how can I convert them into an angle... that one should be simple. I know how to convert an angle to velocity. Any help would be appreciated, and yes, I know that by bringing up this topic again I risk flaming.

Share this post


Link to post
Share on other sites
Zipster    2358
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]

Share this post


Link to post
Share on other sites
Nerusai    103
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]

Share this post


Link to post
Share on other sites
Zipster    2358
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

Share this post


Link to post
Share on other sites
jack_1313    536
Zipster, that was great, a good way to think about the problem. So how exactly would this work in code: a loop that expands the radius of a circle (center being ShooterX,ShooterY) by a small number every pass and checks if the target''s line intercepts? Unfortuantly, speed is a huge consideration, as I am running a bad machine.
Fortunatly, however, acuracy is not a big consideration, given that the opponents and allies in my game are designed to simulate human behaviour, and obviously humans are not that acuarate. Sopose I did use perfect acuracy, I would only have to use random numbers to de-acurise it. So yeah, a simpler, faster and less accurate method would be fantasic. Thanks for the help.

Share this post


Link to post
Share on other sites
Zipster    2358
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).

Share this post


Link to post
Share on other sites
jack_1313    536
Because I am doing a realistic (if there is such a thing when talking about science-fiction) space-combat 2d simulator it will not be nesicary to include walls - at least it is not part of the plan. I took a look at that explination of the line/cone intersection and after reading the first paragraph I was thinking ''...ok, what the hell does that mean?'' - it is way to compex for my uneducated self.
I am just downloading the code now, and hopefully I can understand how it comes up with the proper result, then I can make a custom function out of it all.
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?

Share this post


Link to post
Share on other sites
Zipster    2358
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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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/

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
jack_1313    536
Thanks for the help ppl. I tried the "sin(BAC) = sin(CBA)*enemyspeed/bulletspeed" and likewise I tried "sin(BAC) = sin(CBA)*(enemyspeed/bulletspeed)" but it did not work, possibly because my code is all messed up. The cone method sounds good, and I''ll go for that one, but I couldn''t get that code you (Zipster) linked me to work cause of all the files you have to download (support headers and such). So that brings me to my next question: Where can I find cone/line iterception code for download or a good expenation that I can actually understand?

Share this post


Link to post
Share on other sites
Zipster    2358
I think the AP has a good method involving sines, you just need to do some more googling. It does make a lot of sense. As for the line/cone method, no need to download all their headers, just take a look at the algorithm and replace all their classes with your own equivalents.

Share this post


Link to post
Share on other sites
Fingers_    410
(the AP post was mine, before I finally registered the other day..)

The sine system should work... I just did some back-of-an-envelope calculations and it seems to work in the cases that I can do without a calculator

You do need to insert some logic into it to weed out failures like sin>1, and since the equation actually returns two angles you have to pick the right one (always the one that goes toward the target.. the other one shoots backwards so it''s pretty easy to cull). Also, trying to shoot a slow bullet at a faster target moving away from you can produce a valid angle but if you calculate the intercept time/location it''s in the past, so discard it!

OTOH I can''t find a situation where there is a possible shot but the system fails to find it. It''s nice and deterministic. I don''t have my old SAIS source code at hand (I''m at work), otherwise I''d cut''n''paste from it...

Share this post


Link to post
Share on other sites