Forgive me if I''m asking a common question, but the search feature seems to be broken for the forum. I am coding a missile command clone using SDL. It is pure 2D game where missiles fall from the top of the screen intent on destroying your cities (at the bottom of the screen). I have the code working so far (can launch SAM''s (surface to air missiles), displays them using bresenham''s(sic) method, destroying incoming missiles etc...) Here is what I would like to do. Add missile targeting. My idea is to be able to "select" a falling missile and click within a certain radius of that missile to fire a "fire and forget" tracking SAM. So here''s where I slept through trig class. I''m having conceptual trouble with finding the spot at which both missiles will detonate. I know the x,y,speed and vector_to_target of the incoming missile. I need to plot (knowing the speed, and launch point (x,y)) where the missile should travel to and explode in order to hit the incoming missile in the shortest ammount of time. I hope I''m being clear. I just need help figuring out how to solve for the optimal point of impact. So that when a user clicks on a missile, their SAM launches and nails it at the perfect spot. All help is appreciated! -Trey

The tricky part about this situation is that even though your world is only two dimensions, in order to solve problems where time is an issue, we have to take into account time as an extra dimension, so thus some mathmatics involving time need to be done in three dimensions.

I will ilustrate the problem. Imagine that the surface of your desk represents the 2D world, +/- X to the rigth and left, and +/- Y to the top and bottom. Now imagine time is a third dimension that rises away from the table - altitude. Higher altitudes mean more time has passed, and lesser altitudes mean less time has passed. The altitude of the table surface would be 0, and thus no time has passed.

Imagine the "bad guy" missile. It has an initial position and a definite velocity in both the X and Y directions. As time increases, it moves along the velocity vector. Now imagine this in three dimensions. The missile is at its initial location on the surface of the table, but as time increases (and thus as the altitude increases), the line begins to move in the direction of the velocity. So in your head you should see a 3D line rising up from the table, but at a slant in the direction of velocity.

Now imagine the SAM missile. We know how fast it is going, but don't have a direction. Speed is basically a measure of distance as a function of time. So as time increases, distance from the initial location should increase. However, we don't have a definite direction. When we have a distance but no definite direction, what shape do we get? A circle. The radius of this circle is the distance as a function of time. Since time increases as the altitude increase, the radius of the circle increases as time increases. If you can imagine this, it would be a cone in 3D. The initial point on the surface of the table is when no distance has been travelled, and increases as time increases.

Thus in a pure mathmatical sense, you need to calculate the intersection of a line and a cone. If you picture the intersection in your head, you can see that this point can potentially intersect the cone in two places - once on entry, and then again on exit. In some places, namely along the "base" edge of the cone, there is only one intersection. At any rate, since your goal is to chose the fastest time, this would mean the lowest altitude intersection in terms of our diagram.

I can't think of any equations to solve this off the top of my head, but I think you might be able to get away with a time step method instead. You have the initial points of both missile and SAM, so what you do is see if the position of the missile is within the distance travelled by the SAM at a given time. So start at time 1, see if the point is inside the cirlce. Go to time 2, calculate the circle radius and the point again, and check if the point is inside the cirlce. Repeat until the point is inside the cirlce. You can then narrow down the search inbetween the two times when the point was outside, and then inside the circle.

There are a few problems with this algorithm in general. If the missile is travelling too fast for the SAM to hit at all, then your check will get stuck in an inifite loop, because the point is moving away faster than the circle can grow. However, for a Missile Command type game, everything is moving relatively slow. But just keep in mind that this can happen. My suggestion (and probably the best way to fight this problem) is to calculate times until you know the missile hit the city. For example, if you calculate that after 7 seconds the missile will destroy the city, then don't check to see if the SAM can hit the missile after your time step goes beyond 7 seconds, because it's already too late And if you think about it, this happens a lot in Missile Command, so it's a good stratagy to fight those degenerate cases with.

[edited by - Zipster on January 6, 2003 4:05:26 AM]

Zipster,

Thank you for a great description of the problem. When I thought of the cone the way you described it, I instantly got it. Thank you for taking the time to explain it like that, it is truly appreciated.

Not to mention it works. After sitting down to code it up, I ended up using a for loop to check the distance from "bad" missile to some future point on its slope, and the distance from the SAM to that point. I divide both distances by their speeds (missile and sam have different speeds) to come up with the time to impact the said point. After subtracting the points and taking the absolute value you have the time difference for both projectiles to reach the same point. If the times are within a 10th of a second, then it launches at the future coordinates.

If you're interested in the code...




[edited by - chmod on January 7, 2003 1:14:53 AM]

It''s always a pleasure to help out!