Author Topic: A Dilemma on Interception Mechanics  (Read 4014 times)

0 Members and 1 Guest are viewing this topic.

Offline sloanjh

  • Global Moderator
  • Admiral of the Fleet
  • *****
  • Posts: 2703
  • Thanked: 53 times
Re: A Dilemma on Interception Mechanics
« Reply #30 on: December 12, 2011, 08:57:52 AM »
The problem isn't that ships move before missiles or vice versa. It's the length of the increments. Imagine a ship and a missile on are an intercept course and both are moving at 100 km/s. The ship has a heading of 90 degrees and the missile has a heading of 180 degrees. They are both 200 km/s from the intercept point at the start of a five second increment. Which ever moves first will move 300 km/s past the intercept point and then the other will move behind it and also end up 300 km/s past the intercept point.

The problem with #1 is (I suspect) that you might be able to generate a "dodge" if the corrections by the missile in accounting for target accelleration aren't quite right (then again you might not).

A simple thing to do is to look for a "crossing" by calculating before and after (the time step) cross-products of the missile's relative velocity Vr = Vmissile + Vtarget with the displacement from the missile to the target.  If the dot product of the two cross products (i.e. (Vr0xD0)dot(Vr1xD1)) is negative, that means the displacement (roughly) reversed itself and the missile crossed the target's track.  You can then calculate the (approximate) intercept time by simply taking t0 = |D0|^2/|D0 dot Vr0| or t1 = t_step - |D1|^2/|D1 dot Vr1| (they should only differ by acceleration terms).

John
 

Offline 3_14159

  • Registered
  • Warrant Officer, Class 1
  • *****
  • ?
  • Posts: 84
Re: A Dilemma on Interception Mechanics
« Reply #31 on: December 12, 2011, 09:14:39 AM »
Quote from: Elouda link=topic=4452. msg44583#msg44583 date=1323700547
Of course, the optimal designs then becomes a 2 stage with a high-efficiency booster and high-acceleration warhead.

Actually, it would probably be the other way around.  The example warship has an acceleration of half a g, and accelerating a missile with that to, let's say, 2000km/s will take only 120 days ;-).  A small, but very efficient engine can reach an acceleration of easily half a g, making it possible to correct for quite a long time.
So it'd probably be more like "accelerate as quickly as possible, correct as efficient as possible".
I spent some time calculating this a bit ago, here: aurora2. pentarch. org/index. php/topic,4019. msg44254. html#msg44254 (well, that's quite unreadable, but you can find it unter Newtonian Aurora, Page 42. )
 

Offline Elouda

  • Registered
  • Lieutenant
  • *******
  • Posts: 152
  • Thanked: 4 times
Re: A Dilemma on Interception Mechanics
« Reply #32 on: December 12, 2011, 09:19:14 AM »
The problem is that if the target has a higher acceleration than the missile, then it will be impossible to hit it; thus the missile you proposed with a second stage acceleration of ~5m/s would not be able to hit any designs that had an acceleration greater than that, which I could easily see being the case for faster warships, like the ADC in the first post of that thread, which could do over 2g.

Remember that 'high efficiency' is relative, so I dont necessarily mean using a freighter efficiency level drive for it. Also, missiles are likely to be fractionally more engine than ships, so you'd have to be pretty conservative to design a missile booster stage with 0.5g acceleration.
« Last Edit: December 12, 2011, 09:24:39 AM by Elouda »
 

Offline PTTG

  • Sub-Lieutenant
  • ******
  • Posts: 125
Re: A Dilemma on Interception Mechanics
« Reply #33 on: December 12, 2011, 10:21:51 AM »
I'd say that the second stage is the one that needs to be high-G. The efficient stage will get you within a short range of the enemy ship, and then the second stage will be able to close the distance and detonate on target. The first stage can be slower than the enemy ship, but the second stage has to be faster than the target.

Hmm...

Given the area effect of missiles now, can we have them target a waypoint? It would be useful to allow us to lead enemy ships by instinct.
« Last Edit: December 12, 2011, 11:14:48 AM by PTTG »
 

Offline Mormota

  • Warrant Officer, Class 2
  • ****
  • M
  • Posts: 62
Re: A Dilemma on Interception Mechanics
« Reply #34 on: December 12, 2011, 10:49:51 AM »
You would have to zoom in very far for that to be accurate, and your instincts are probably nowhere near accurate for that.
 

Offline Yonder

  • Registered
  • Lt. Commander
  • ********
  • Y
  • Posts: 261
Re: A Dilemma on Interception Mechanics
« Reply #35 on: December 12, 2011, 01:16:46 PM »
That said, on further reflection I'm not sure what the micro-pulses do for you. Option 3 already gets you, with a little math, the time and location of the explosion. Just make an ordered list of possible explosions, march down, and take out destroyed missiles as necessary.

Steve may or may not get benefit from the micro-pulses depending on how things are working underneath the hood. If all of the accelerations or velocities of ships and missiles stay constant during a sub-pulse, than he probably could just use a Hermite Interpolation method and in order to find the positions and velocities of all of the bodies involved just as accurately as if he was propagating them with micro-pulses.

However if he is using those micro-pulses to allow the ships and especially missiles to update their accelerations on a much finer scale each time step, then there really isn't any way to replicate that via interpolation.

For reference, a Hermite Interpolation algorithm can be written from the following two wikipedia pages:
http://en.wikipedia.org/wiki/Hermite_interpolation
http://en.wikipedia.org/wiki/Divided_differences

This problem sounds fundamentally similar to a common problem with 3D physics engines. I'm not familiar with how it's handled, but the problem may already have been resolved (or at least mitigated) there in a way you can reuse.
It is similar to the problem of collision detection in other environments, yes. The easiest example is with buildings and walls, if collision was only detected on each simulation time-step then for any non-infinitesimal timescale there would be a chance of bullets passing through walls by being just before the wall on one step and just after the wall on the next step. The way you get around this is by doing collision detection not on the point of the bullet, but on a cylinder that goes from the bullets last position, to it's new position, and is the width of the bullet.

That is a much similar problem though, because you are interested in the collision with static walls or (relatively) slow moving models. Here the problem is more similar to trying to track whether one bullet hit another bullet, you now need to track the motion of both objects.

Not only that, but depending on the accelerations involved you can't even assume that the ships and missiles are moving in straight lines anymore, which entails slightly more time-consuming calculations for the computer to figure out whether they hit. In fact, that may be reason enough for the micro-pulses right there, so that the time scales get small enough that it's accurate to assume that each ship is travelling on a straight line for each sub-pulse. That would let you use the constant time "Where is the closest intersection point between these two lines and how far apart are they then" operation on the lines, instead of... Probably the Newton's root finder method with the time as the input and the distance between the two bodies as the output.
 

Offline chuckles73

  • Chief Petty Officer
  • ***
  • c
  • Posts: 37
Re: A Dilemma on Interception Mechanics
« Reply #36 on: December 13, 2011, 01:17:10 PM »
Not only that, but depending on the accelerations involved you can't even assume that the ships and missiles are moving in straight lines anymore, which entails slightly more time-consuming calculations for the computer to figure out whether they hit. In fact, that may be reason enough for the micro-pulses right there, so that the time scales get small enough that it's accurate to assume that each ship is travelling on a straight line for each sub-pulse.

Sort of by definition, ships are only moving in a straight line during a pulse. Pulse is the time slice for which you calculate movement (among other things). So, Point A at the beginning of pulse, Point B at end. There is no movement between those two, it's a straight line.
 

Offline PTTG

  • Sub-Lieutenant
  • ******
  • Posts: 125
Re: A Dilemma on Interception Mechanics
« Reply #37 on: December 13, 2011, 02:22:29 PM »
Well, yes... but if we go int "slow motion" for a few sub-pulses, then the formerly straight line may become curved with time.

Oh, you know, it would be neat to see trajectories curved flight paths on the system map. Any chance we could have it show "Flight path from past X pulses"?
 

Offline Yonder

  • Registered
  • Lt. Commander
  • ********
  • Y
  • Posts: 261
Re: A Dilemma on Interception Mechanics
« Reply #38 on: December 13, 2011, 04:44:56 PM »
Sort of by definition, ships are only moving in a straight line during a pulse. Pulse is the time slice for which you calculate movement (among other things). So, Point A at the beginning of pulse, Point B at end. There is no movement between those two, it's a straight line.

Not necessarily, you would probably assume constant acceleration over each time step, and then integrating that you would get a linear change in velocity, and a parabolic change in position. You don't even have to assume that the acceleration is constant over a time step, when you calculate the acceleration of the current step you can look at the last step and assume that acceleration varied linearly (or with some other variation) during that time when you go to integrate the position. There are several ways to do this sort of thing.

It's also possible to have a program architecture set up such that some information is much more difficult to get on sub-increments. For example Runge Kutta integration schemes naturally break up each step into subsequent sub-steps, and depending on how you have constructed your code it's difficult or impossible for you to actually get those sub-pulse intervals out. If you did something like this you may have a Propagator step forward 5 seconds, but your Runge Kutta method may (depending on the order) automatically break this step into 12 smaller steps. The idea is that you only want your data every 5 seconds, not on these short pulses, but you can do this to efficiently get a more accurate trajectory for those five seconds.
 

Offline chuckles73

  • Chief Petty Officer
  • ***
  • c
  • Posts: 37
Re: A Dilemma on Interception Mechanics
« Reply #39 on: December 14, 2011, 09:03:54 AM »
Not necessarily, you would probably assume constant acceleration over each time step, and then integrating that you would get a linear change in velocity, and a parabolic change in position. You don't even have to assume that the acceleration is constant over a time step, when you calculate the acceleration of the current step you can look at the last step and assume that acceleration varied linearly (or with some other variation) during that time when you go to integrate the position. There are several ways to do this sort of thing.

I was assuming no calculus during movement phase.  :P
 

Offline byron

  • Rear Admiral
  • **********
  • b
  • Posts: 883
  • Thanked: 28 times
Re: A Dilemma on Interception Mechanics
« Reply #40 on: December 15, 2011, 07:57:37 AM »
I was assuming no calculus during movement phase.  :P
You don't actually need calculus during the movement if the acceleration varies linearly with time.  In that case, velocity will vary with the square of time times jerk (dA/dt) and position will vary with the cube of time times jerk.
This is Excel-in-Space, not Wing Commander - Rastaman
 

Offline Nathan_

  • Pulsar 4x Dev
  • Commodore
  • *
  • N
  • Posts: 701
Re: A Dilemma on Interception Mechanics
« Reply #41 on: January 09, 2012, 11:09:10 AM »
Accurate collision detection is generally done via the many sub pulses method you mentioned, and that tends to be expensive so I think that option one is best.   Of course you could cheat and let missiles that overshot their target change directions a set number of times, say 5 chances to hit their target.   If they miss all 5 they are considered to have been successfully dodged.
 

Offline Catty Nebulart

  • Petty Officer
  • **
  • C
  • Posts: 21
Re: A Dilemma on Interception Mechanics
« Reply #42 on: May 28, 2012, 01:29:08 AM »
I'm not sure if you already have a solution or not, but throwing a bit of math at the problem solves it. For each missile designing calculate the intercept cone factor (ICF) which will just be half the max acceleration in distance/time.

Now imagine a pair of line-segments in 4D space, with the 3 coordinates for the ship position at t=0 to the 3 coordinates for the ship at t=5 being one segment, and the same pair for the missile. Now find the point on the ship line segment that is closest to the missile line, and the distance it is from the missile line. The t coordinate will get you the intercept time, now use the ICF and multiply it by t*t. If the distance you get for that calculation is greater than the distance you got for the line segments then the missile will hit, otherwise it will miss. The point you got on the ship line is the point where the detonation occurs.

sample code, though for missile interception you'll want to handle the parallel case separately, T=0 would be a bad choice for missile interception.
 

Offline exdeathbr

  • Petty Officer
  • **
  • e
  • Posts: 17
Re: A Dilemma on Interception Mechanics
« Reply #43 on: July 26, 2012, 09:09:01 AM »
Quote from: Steve Walmsley link=topic=4452. msg44488#msg44488 date=1323540368
Well, possible if I rewrite the entire movement engine of the game :).  Also, some missiles have an area effect warhead so you would also need to know where everything else is at that exact moment as well.  Moving everything in the game simultaneously would be challenging, which is why I used the pulse system.  You can get more accurate by using much smaller pulses but then you run into performance issues.  The point of this thread is to look at way of getting around the issue without a major code rewrite. 
Why not spend time rewriting the code? I mean, in this way you will not end in similar stuff in the future. 
Also you can always continue to worksin normal aurora (and so make it better), the fact this code rewrite will take way more time to create newtonian aurora but people can always play normal aurora while they wait.
 

 

Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53