Jump to content
XCOMUFO & Xenocide

Interception Methods


Maverick

Recommended Posts

It should be easier to understand if you read the attached PDF but it is pretty long and it isn't great quality. Essentially, I suggest we use a weighted projection function for interception path finding (explained in the PDF). I can write it in pseudo-code (I'm familiar with Matlab, which is similar to C) and there are a few other mathematical functions that would be necessary in order to implement it. On the whole it does nothing to eliminate the problem of fuel consumption. If I have not advanced the argument to you before, (Garo is the only one I've talked to) it is something like this (simply):

 

If we do not compute movement at the minimal clock tick even for faster game speed (that would be to compute movement in terms of 5 second intervals even when the game passes at 1 hour ticks) fuel consumption is less at the higher game speed and thus the effectiveness of the interceptor is increased for higher game speed. In other words, you have better chances of catching a ufo at 1 hour/tick vs 5 seconds/tick. Page 2 of the PDF attempts to show the general concept. The difference in fuel consumption can be very small, but depending on the path being traced it maximizes at the limit of the ratio of time frames considered -- that means that for 1 hour vs 5 seconds it would be 720 times greater fuel consumption at 5 seconds. This is an unrealistic case! However, the fact that it can be that high means that we have to think about some way to solve this problem -- after we implement it without a solution (that is, ignore the problem for now -- it is possible that it will not end up being a problem for the player, it all depends really on how the UFO's travel, so we might be able to "guide" them in such a way as to minimize this effect). If this does not work, the other alternative is to change the base time tick as far as directional correction is concerned. That is, craft only change direction every 1 minutes (so at 5 seconds it would travel in straight lines for 1 minute at a time) -- which would reduce the maximum possible consumption error from 720 to 60 -- with resulting consequences at low speeds during interceptions....let me know what you think.

 

-Maverick

path_find.pdf

Link to comment
Share on other sites

Side thought that resolves an issue -- if fuel consumption is only based on the time spent in the air (assuming that we agree to instant accel/decel and because lower than max speed will not be as frequent as at max speed) we can eliminate the discrepency between low speed clock ticks and high speed clock ticks -- since the same time will eventually pass at either time setting and the distance traveled is irrelevant to fuel consumption. It does not satisfy the difference in interception effectiveness, but it does reconcile the issue of fuel consumption.

 

-Maverick

Link to comment
Share on other sites

Side thought that resolves an issue -- if fuel consumption is only based on the time spent in the air...

 

I'm pretty sure that it isn't based just on that. Player can order interceptor to patrol at a certain point and I'm quite confident that the patrol (as the craft doesn't move) spends less fuel than chasing an interceptor with afterburners on.

 

We could, however, solve this by taking the current velocity into account when calculating fuel consuption: If the velocity was 100% when the tick rolls, the fuel amount is decreased (lets say) by x. If the velocity was 50%, the fuel is decreased 0.6x. If the velocity was zero (the craft patrols over a point), the fuel is decreased by 0.2x. I just took those numbers randomly, but you get the point :)

 

The other thing which I'm worried, is that if an ufo does evasive manoveurs, can we calculate the affect of these movements acurately enough when using faster gamespeeds (like 12h/tick or 1h/tick) so, that the interception of this ufo at faster gamespeeds are equally hard/easy than with slover gamespeeds.

 

- Garo

Link to comment
Share on other sites

Assuming the UFO does not change its course, then calculating the optimum intercept course for the human craft is as follows. (Dealing with a UFO that changes course is a different problem, that I will discuss in a later post.)

 

I will also assume Cartesian co-ordinates, rather than spherical ones.

 

So: Initial conditions are:

UFO at position Xu, Yu, speed Vu, and heading Hu.

Human craft Xc, Yc, max speed Vc. We want to find Heading Hc.

 

First thing we do is define our co-ordinates (to simplify the maths.)

We define Xc and Yc as origin (0, 0) and rotate our co-ordinates so that UFO is on the Y axis.

 

Rotation angle = 90 degrees + arctan( (Yu-Yc) / (Xu – Xc))

 

(This is all simple trig. And left as an exercise.) Giving us the values

 

Xu’ = 0, Yu’ = sqrt((Xu-Xc)^2 + (Yu-Yc)^2), and a new heading Hu’ = old heading + rotational angle.

 

We can now split the UFO’s velocity into two components Vx and Vy using the formulas

Vx = Vu cos(Hu’), Vy = sin(Hu’)

 

Giving us the following formula for the position of the UFO at any time t.

Xu(t) = t * Vx, Yu(t) = Y + (t * Vy).

 

From this, we can calculate the distance UFO will be from the Human craft’s origin from the formula

Du(t) = sqrt( Xu(t)^2 + Yu(t)^2).

But we ALSO know that because the human craft is flying away from the origin on a straight line its distance must be:

Dc(t) = t * Vc

Now at interception, Du(t) == Dc(t), so we just have to solve

(t * Vc)^2 = (t*Vx)^2 + (Y + t * Vy)^2 + (2 * t * Vy)

 

Which can be rewritten as the polynomial:

t^2 * (Vu^2 – Vc^2) + t * (2 * Vy * Y) + Y^2 = 0

and solving for t is a well known and trivial problem.

Which tells us WHEN a minimum time intercept will occur.

We then substitute this into the equations for the UFO’s position, and this tells us WHERE the intercept will occur. And from that, getting the craft’s heading Hc is simple trig.

 

(note, we also need to check to see if the UFO is going to reach its destination BEFORE the intercept point. In which case, the human craft heads for the UFO’s destination. – we may want to cheat, and allow the course plotting software can know the UFO’s destination, even if the user doesn’t.)

Link to comment
Share on other sites

Yes, all that is true dteviot, but let's start here - there are several mistakes in your math. Primarily, your method for rotation of the axis is not quite correct because you must account for the alien craft being in any of the 4 quadrants and even then, the basic form should be 90-arctan().

 

Giving us the following formula for the position of the UFO at any time t.

Xu(t) = t * Vx, Yu(t) = Y + (t * Vy).

 

From this, we can calculate the distance UFO will be from the Human craft’s origin from the formula

Du(t) = sqrt( Xu(t)^2 + Yu(t)^2).

But we ALSO know that because the human craft is flying away from the origin on a straight line its distance must be:

Dc(t) = t * Vc

 

Following this definition, wouldn't:

Xc(t) = t * Vcx, Yc(t) = t * Vcy

to give:

Dc(t) = t * sqrt(Vcx^2 + Vcy^2)

 

That is to say nothing of keeping track of the angle of travel.

 

If I have interpreted the meaning of your formula correctly, what you have actually described is a variation of solution 3 -- because I am interested in course corrections at each step, we try not to extrapolate future position of the craft beyond the weight function -- your model is invalid for any craft not traveling in a straight line forever. And even in the case of a craft traveling in a straight line, if the speed of the UFO is greater than the speed of the craft there will be no solution for your quadratic equation for t because the distances will never overlap. You have all the right math, but you have incorrectly defined the parameters of the problem.

Edited by Maverick
Link to comment
Share on other sites

  • 3 weeks later...
Yes, all that is true dteviot, but let's start here - there are several mistakes in your math. Primarily, your method for rotation of the axis is not quite correct because you must account for the alien craft being in any of the 4 quadrants and even then, the basic form should be 90-arctan().

There may be some minor errors in my algebra/trig, but I believe the basic principles are correct.

 

Giving us the following formula for the position of the UFO at any time t.

Xu(t) = t * Vx, Yu(t) = Y + (t * Vy).

 

From this, we can calculate the distance UFO will be from the Human craft’s origin from the formula

Du(t) = sqrt( Xu(t)^2 + Yu(t)^2).

But we ALSO know that because the human craft is flying away from the origin on a straight line its distance must be:

Dc(t) = t * Vc

 

Following this definition, wouldn't:

Xc(t) = t * Vcx, Yc(t) = t * Vcy

to give:

Dc(t) = t * sqrt(Vcx^2 + Vcy^2)

 

That is to say nothing of keeping track of the angle of travel.

Actually, we don't need the human craft's angle at this point in the cacluations.

As the human craft is flying in a straight line, at a constant (maximim) velocity, then it's DISTANCE from its starting point is a linear function of time, regardless of the angle of travel.

 

And we have a function for the Distance of the UFO from the human craft's starting point as a function of time. And for an interception, we know that the distance (for a given time) will be the same.

So we just need to find the value of t where Du(t) == Dc(t).

 

If I have interpreted the meaning of your formula correctly, what you have actually described is a variation of solution 3 -- because I am interested in course corrections at each step, we try not to extrapolate future position of the craft beyond the weight function -- your model is invalid for any craft not traveling in a straight line forever.

I did say that I'm assuming the UFO maintains a constant course.

 

And even in the case of a craft traveling in a straight line, if the speed of the UFO is greater than the speed of the craft there will be no solution for your quadratic equation for t because the distances will never overlap.

Sorry, I thought it was obvious that the quadric equation will have an imaginary solution when an intercept vector isn't possible (this is NOT the same case of UFO being faster than craft) So I didn't bother to add that qualification. And, of course,

I'll also note:

1. Checking if the quadratic's solution is imaginary is trivial.

2. The quadratic will usually have two solutions for t, so we want take the smaller one.

3. I did point out that we need to check if interception would occur after the UFO reached it's target.

 

Unfortunately, the approximation that we're dealing with cartesian co-ordinates is only valid over short distances. (My quick and dirty calcuations suggest the error will be about 120km over a distance of 4800km). However, a similar approach to solving the problem using spherical co-ordinates may be possible.

 

I.e. rotate the UFOs current and target positions so that UFO is travelling along the equator of the globe. (This simplifies the UFO's co-ordinates to a simple theta = t * V.) We then apply the same rotations to the human craft's origin, and derive the equation that position on the equator the human craft would reach at a given time (assuming minimum distance great circle routes at maximum velocity). We then equate the two equations, and solve for t.

 

You have all the right math, but you have incorrectly defined the parameters of the problem.

 

I did say that I would discuss the possibility of evasion courses later. Which is now.

For the sake of keeping the examples simple, I'm going to assume that a (Human) craft is trying to intercept a UFO.

 

The question I'm going to attempt to answer is "Do we need to worry about UFOs trying to avoid interception?" I believe the answer is NO. Here's my reasoning.

 

There are three cases we need to consider:

1. UFO is slower than craft.

2. UFO is faster than Craft.

3. UFO and craft have same speed.

 

UFO is slower than craft.

In this case, there is little point in the UFO trying to take evasive action. The UFO can either reach its destination, on a minimum time course, before its intercepted, or it can't. If it can, then there's no need for evasive action. If it can't then, an evasive course will at best delay the inevitable. OK, there is the possibility that the UFO might divert to an alternate base that it CAN reach before interception. But that means that the mission is a failure.

 

UFO is faster than craft.

(Firstly, I'm not sure if we ever run into this case, are any UFOs faster than any of the intercept craft?)

In this case, if UFOs CAN take evasive action, there is little point in the craft trying to intercept UFOs, as the UFO can always avoid contact. The only case where a craft could intercept is if the craft can reach the UFO's destination before the UFO, and then "staking out" the destination. (Or if the UFO lands, catching the UFO at the landing site.)

Either way, the only way for the craft to intercept the UFO is to head for the UFO's final destination, regardless of where the UFO is. It's going to make for a fustrating game for players.

 

UFO and craft have same speed

This can probably be regarded the same as the UFO is faster than craft case. If they're the same speed, then an interception (at any place other than the UFO's final destination) is not possible if the UFO doesn't want to co-operate.

Link to comment
Share on other sites

  • 2 weeks later...
sorry to break in here y'all, for the intercept screen would it be possible to place a small render window on it that would sho the currently select interceptor instead of doing a 2d bitmap of it(similar to xnet). If it is possible, can we go this route for the screen so it will accommodate changes of resolution better?
Link to comment
Share on other sites

sorry to break in here y'all, for the intercept screen would it be possible to place a small render window on it that would sho the currently select interceptor instead of doing a 2d bitmap of it(similar to xnet). If it is possible, can we go this route for the screen so it will accommodate changes of resolution better?

Someone's going to slap me down for asking this, but "Why are we creating 3D models of craft?"

So far as I can see, we can't do much with them.

1. They're not going to appear on the geoscape.

2. There's no aeroscape (at the moment.) And for the intercept dialog, could just be a schematic.

3. They're unlikely to appear on the battlescape. (The UFO and Craft models will need be be altered to be PART of the battlescape, like buildings.)

4. I don't think we're planning on drawing them in hangers in the basescape.

 

The only places I can see it being used are:

1. The equip craft dialog/screen (possibly)

2. X-Net.

Link to comment
Share on other sites

  • 10 months later...

I saw something on this topic on Numb3rs last night.

It's called "Pursuit curves" in mathematics.

Not sure it's useful to us, because it appears to require the hunter to always be pointing at the target's current location. We want to anticipate the target's location. However, this site has some cool animations.

And someone might like to google the topic and see if they can find anything more useful.

 

Edit: this. looks promissing.

Edited by dteviot
Link to comment
Share on other sites

×
×
  • Create New...