Aurora 4x

VB6 Aurora => Newtonian Aurora => Topic started by: Steve Walmsley on December 09, 2011, 03:28:48 PM

Title: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 09, 2011, 03:28:48 PM
I have just encountered a problem that I should have foreseen and I am interested in opinions on how I should resolve it.

In Newtonian Aurora, one of the whole points of the game is the inability for fast moving objects to easily change course. This means that missile guidance needs to be based on intercepting the future position of an object rather than simply moving toward its current position, as in Standard Aurora. So take the example of a missile trying to intercept a ship. Based on a combination of the contact information (which provides the current location of the target, its current speed, its current heading and its current acceleration rate) and the missile's own location, speed, heading and acceleration rate, the missile guidance code works out where the two objects will intercept, assuming constant acceleration. The missile then expends delta-V over time to make the necessary course change, adjusting as it goes. As the target changes speed, heading and acceleration, the missile calculates a new interception point and corrects its course (also taking into account that vs other missiles the other missile may not have moved yet in the current sub-pulse). This is tricky :) but it is working. Now the problem:

The underlying mechanics of Aurora are

a) Advance time by an increment from 5 seconds to 30 days
b) Move objects several times during an increment (using anything from 1 to 60 sub-pulses)
c) Within those sub-pulses, objects are moved one at a time using a initiative system, with all missiles moving after ships.
c) Resolve any interceptions, etc.

This is easy in Standard Aurora because objects can change direction and speed at any time. The problem for Newtonian Aurora is that although the missile guidance code puts the missile on the correct course, unless the position of the missile and the ship happen to coincide at the end of a sub-pulse, the ship moves first and then the missile moves through the path of the ship and passes behind it. This is because the missile is expecting to find the ship at the point in its path where the courses intercept but of course that point could be 2.47 seconds into the increment, rather than 5 seconds. Not a problem in Standard Aurora because the missile would just change course but in Newtonian Aurora the course change is not even close to possible. If both objects were moving simultaneously, or with really tiny sub-pulses, the missile would hit. So without changing the fundamental mechanics of the whole movement system - how do I fix this. I have considered four options so far:

1) Change the interception code so the missile will only aim for a location which the target will be in after an amount of time divisible by 5 seconds. This might cause some slight course swapping and additional delta-V use by the missile

2) Add much smaller sub pulses (perhaps 0.1 seconds or less). However, besides the perfomance implications during the increment, any potential missile hits will have to be calculated before the increment begins so the appropriate fractional sub-pulses can be used. This type of thing is done already on a large scale. The major problem though is that all times anywhere in the program are currently assumed to be integers so I could try changing this but there is a risk of a screw-up.

3) Calculate the closest point of both missile and the target during the sub-pulse, based on their movement paths (this is a calculation of both time and space as their paths may cross but it depends on where they are along that path). Detonate if on target or within detonation range and note the exact time of detonation during the sub-pulse. Then check the paths of all objects and resolve damage based on their distance from detonation at that exact point in time during the sub-pulse (so where was every ship 3.16 seconds into the sub-pulse and how far where they from the blast at that exact moment).

4) Calculate closest point of both missile and target during sub-pulse, as in 3). However, actually detonate the missile that distance from the ship on a direct path from the start location of the missile to the end location of the ship rather than the actual detonation point, then assess area damage based on adjusted detonation location and the position of nearby ships at the end of their movement. The difference between this and 3) is that it will be more obvious to the player which ships were in the blast radius.

I would also welcome any other ideas - apart from "entirely rewrite the way Aurora handles movement" :)

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: UnLimiTeD on December 09, 2011, 03:39:35 PM
Do 3 and 4 work with kinetic kill vehicles?

I think the option of calculating where it will hit, and then detonating it there in the pulse, seems good enough.
Title: Re: A Dilemma on Interception Mechanics
Post by: TheDeadlyShoe on December 09, 2011, 03:42:04 PM
If it's going to be a 'close pass' situation where a ship and missile are likely to intercept in a 5s increment (or in a 1s subpulse?) you could game it out as skill-based evasive maneuvers - crew grade/movement initiative/ECM VS thrust and homing ability of the missile. However, that may not really get what you want in terms of determining where the big ol kaboom occurs.  

I favor 3.  4 is more clear but it seems ...futzy? gamey?   Worst case you could generate a graphic for each missile detonation...lol :D
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 09, 2011, 03:43:01 PM
Do 3 and 4 work with kinetic kill vehicles?

I think the option of calculating where it will hit, and then detonating it there in the pulse, seems good enough.

Once I solve this for missiles, I will use it for railguns as well.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 09, 2011, 03:47:58 PM
If it's going to be a 'close pass' situation where a ship and missile are likely to intercept in a 5s increment (or in a 1s subpulse?) you could game it out as skill-based evasive maneuvers - crew grade/movement initiative/ECM VS thrust and homing ability of the missile.

These are objects moving at over 1000 km/s so there are extremely few 'close passes' with 5 or even 1 second increments. They can easily miss by 3000 km/s or more. Think of an area of twenty-five million square kilometers. Two objects dash across it from different directions and pass through in less than five seconds. How often will they pass within detonation range, which is maybe one kilometer for nukes and 50-100 km for laser heads.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: chuckles73 on December 09, 2011, 04:05:41 PM
I like 2 a lot, but at high enough speeds you'd need smaller and smaller subpulses. (eg at 5000km/s with .1 second subpulses, you'd still be covering 500km in that subpulse)

4 would be nice for ease of understanding's sake, but it could screw up who's getting hit in certain situations. For perpendicular courses, the missiles could be blowing up pretty far from where they should. Assume 5000km/s again, for the missile and the target. Assume they would actually meet immediately at the start of the pulse and that their courses are perpendicular. The missile end up exploding roughly 25,000km from where it should be with a pulse length of 5 seconds.

I think 3 would be a good solution.
Title: Re: A Dilemma on Interception Mechanics
Post by: PTTG on December 09, 2011, 04:11:09 PM
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.

I suppose that my approach might be to, every tick, find out when and where the missile will cross/has crossed the path of the ship, then see if the ship is at the same place (or within detination distance) at that time. On reflection, that sounds much like 3.

I must say, solution 1 sounds like the most robust from a programming standpoint. It does drop some accuracy, but it'll be just as fast and stable as what we currently have.
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 09, 2011, 04:17:31 PM
I like 2 a lot, but at high enough speeds you'd need smaller and smaller subpulses. (eg at 5000km/s with .1 second subpulses, you'd still be covering 500km in that subpulse)

4 would be nice for ease of understanding's sake, but it could screw up who's getting hit in certain situations. For perpendicular courses, the missiles could be blowing up pretty far from where they should. Assume 5000km/s again, for the missile and the target. Assume they would actually meet immediately at the start of the pulse and that their courses are perpendicular. The missile end up exploding roughly 25,000km from where it should be with a pulse length of 5 seconds.

I think 3 would be a good solution.

I am considering another option to combine 2 and 3, which would effectively be to replay the pass in slow motion. If the missile crosses the path of the target object, I rerun them both in a mini-increment of their own with really tiny sub-pulses (0.0001 seconds?) and check their distance at each point. Because I am doing this for those two objects alone, it doesn't cause any problems with using fractional seconds for the rest of the program. After the recheck is done, I detonate the warhead at the closest point, and assess every other potentially-affected object by checking its location at that exact fraction of a second. I already track start and finish positions for every objects in an increment so the necessary information is already available.

Hmm! Although another complication just occured to me. What if the nuclear detonation takes out another missile that exploded slightly later in the increment. I guess I will have to save all possible nuclear detonations until after all movement then check them all in exact order of detonation and see if any were destroyed before they exploded. With that level of detail I probably need to also track how long it would take the blast wave to arrive.

Although 1 looks more attractive now because at least everything would happen simultaneously :)

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 09, 2011, 04:18:48 PM
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.

I suppose that my approach might be to, every tick, find out when and where the missile will cross/has crossed the path of the ship, then see if the ship is at the same place (or within detination distance) at that time. On reflection, that sounds much like 3.

I must say, solution 1 sounds like the most robust from a programming standpoint. It does drop some accuracy, but it'll be just as fast and stable as what we currently have.

LOL this is almost identical to the post I just made - you beat me to it by 6 minutes :)

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: bean on December 09, 2011, 04:35:23 PM
I'm not sure where I fall in this.  For kinetics (and anything else that doesn't have a blast radius) you can skip this, and simply figure out if it would have hit during that increment.  For nukes, option 3.
Title: Re: A Dilemma on Interception Mechanics
Post by: UnLimiTeD on December 09, 2011, 05:12:00 PM
So, in that case, wouldn't a sentient race have all their nukes set so they communicate and detonate at once?
It might not do much, but it's better than to just disappear.
Title: Re: A Dilemma on Interception Mechanics
Post by: chrislocke2000 on December 09, 2011, 05:24:02 PM
The replay in smaller ticks makes sense to me. I guess that rather than rerunning the whole thing in tiny steps you can just do increasingly small reruns. Ie replay the 5 sec tick at 1 sec increments and find in which tick it crosses and not calculating for any ticks after that. The replay that tick in .1 sec increments. I assume, (probably wrongly!) that that would allow you to get to a very precise point whilst limiting the total number of ticks you need to check.
Title: Re: A Dilemma on Interception Mechanics
Post by: Vanigo on December 09, 2011, 06:03:05 PM
I am considering another option to combine 2 and 3, which would effectively be to replay the pass in slow motion. If the missile crosses the path of the target object, I rerun them both in a mini-increment of their own with really tiny sub-pulses (0.0001 seconds?) and check their distance at each point. Because I am doing this for those two objects alone, it doesn't cause any problems with using fractional seconds for the rest of the program. After the recheck is done, I detonate the warhead at the closest point, and assess every other potentially-affected object by checking its location at that exact fraction of a second. I already track start and finish positions for every objects in an increment so the necessary information is already available.

Hmm! Although another complication just occured to me. What if the nuclear detonation takes out another missile that exploded slightly later in the increment. I guess I will have to save all possible nuclear detonations until after all movement then check them all in exact order of detonation and see if any were destroyed before they exploded. With that level of detail I probably need to also track how long it would take the blast wave to arrive.
Wouldn't the proposed combination of 2 and 3 almost take care of this already? Just run the micro-pulse reruns in parallel, instead of one at a time. Then, when the first blows, you can easily examine the current location of other nearby missiles and take them off the list as appropriate. I suppose once in a blue moon you'd see two missiles go off in the same micro-pulse, but not often enough to worry about, I think.
Title: Re: A Dilemma on Interception Mechanics
Post by: TheDeadlyShoe on December 09, 2011, 06:47:24 PM
Question: If AMMs have nuclear warheads, arn't you going to have to run these calcs for all AMM intercepts?  Hopefully it won't take epic amounts of time.
Title: Re: A Dilemma on Interception Mechanics
Post by: UnLimiTeD on December 09, 2011, 06:53:23 PM
Maybe create a second thread (aka a mini-program) that does nothing else but micropulses? ;)
Title: Re: A Dilemma on Interception Mechanics
Post by: GeaXle on December 10, 2011, 04:43:58 AM
Quote
Hmm! Although another complication just occured to me. What if the nuclear detonation takes out another missile that exploded slightly later in the increment. I guess I will have to save all possible nuclear detonations until after all movement then check them all in exact order of detonation and see if any were destroyed before they exploded. With that level of detail I probably need to also track how long it would take the blast wave to arrive.

Quote
So, in that case, wouldn't a sentient race have all their nukes set so they communicate and detonate at once?
It might not do much, but it's better than to just disappear.

This made me think. Will it be possible to chose to spread a group of missile separated by their extact detonation range and to all detonate at the same time? Maybe aiming for a group of ships instead of a single one. A kind of huge area of damage.
Title: Re: A Dilemma on Interception Mechanics
Post by: Mel Vixen on December 10, 2011, 04:59:47 AM
Wouldt it be sufficient to let ship and missile move on the same turn/in the same phase once they are in interception-distance? Sure its some more linesof code but it could work.
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 08:54:55 AM
This made me think. Will it be possible to chose to spread a group of missile separated by their extact detonation range and to all detonate at the same time? Maybe aiming for a group of ships instead of a single one. A kind of huge area of damage.

I think it would be possible to link several salvos together so they all detonate at the same time. Or maybe a MW missile that sends its sub-munitions in diverging directions with the same end result. I think the days of large salvos are over anyway as one nuclear AAM will destroy the whole incoming salvo. Anti-ship missiles will have to be spread out to avoid that fate. I haven't decided how to do that yet but staggered launch would be one option and a second would be divergent courses for a set period before they all lock on to a target and begin homing.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 08:56:25 AM
Wouldt it be sufficient to let ship and missile move on the same turn/in the same phase once they are in interception-distance? Sure its some more linesof code but it could work.

Its a little more than a few lines of code :). It wouldn't solve the underlying problem though because whatever order they moved in, if the interception point is 2.5 seconds into an increment, they would still miss each other.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 08:56:53 AM
Maybe create a second thread (aka a mini-program) that does nothing else but micropulses? ;)

This is VB6 :). There is no multi-threading.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 08:58:52 AM
Wouldn't the proposed combination of 2 and 3 almost take care of this already? Just run the micro-pulse reruns in parallel, instead of one at a time. Then, when the first blows, you can easily examine the current location of other nearby missiles and take them off the list as appropriate. I suppose once in a blue moon you'd see two missiles go off in the same micro-pulse, but not often enough to worry about, I think.

Running everything in micro-pulses would be really hard on performance, that's why I was considered re-running after the event for just the affected objects. Unless I have misintepreted what you meant.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 09:02:45 AM
I tried 1) last night. A ship moving at 350 km/s launched at a second ship moving across its path at 700 km/s and under constant acceleration. The missile reached 1200 km/s, which was its set max speed, and homed in. It actually hit the target ship and detonated its 250 KT laser warhead. As you can imagine, the target didn't survive.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Mormota on December 10, 2011, 09:38:43 AM
Wouldn't it be better to make missiles move before ships? At longer ranges, this would hardly make a difference, and it would solve the whole interception problem, I think.
Title: Re: A Dilemma on Interception Mechanics
Post by: UnLimiTeD on December 10, 2011, 10:18:21 AM
Crap, I always forget how old the code is..
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 11:17:16 AM
Wouldn't it be better to make missiles move before ships? At longer ranges, this would hardly make a difference, and it would solve the whole interception problem, I think.

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.

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Mormota on December 10, 2011, 11:53:56 AM
Is it not possible to make missiles move at the same time their target does, then?
Title: Re: A Dilemma on Interception Mechanics
Post by: Steve Walmsley on December 10, 2011, 12:06:08 PM
Is it not possible to make missiles move at the same time their target does, then?

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. I think I am going to use the first of the four options for missiles because it is only a slight fudge, it only required a couple of lines of code and the first test actually physically hit a fast-moving target with a flight path perpendicular to that of the missile. For railgun shots I think I will use a combination of 2) and 3).

Steve
Title: Re: A Dilemma on Interception Mechanics
Post by: Vanigo on December 10, 2011, 01:35:30 PM
Running everything in micro-pulses would be really hard on performance, that's why I was considered re-running after the event for just the affected objects. Unless I have misintepreted what you meant.

Steve
Well, what I meant was, you're talking about taking one missile and one target and running them on micro-pulses, then taking another missile and its target and running them on micro-pulses, and so on until you've done every potentially-intercepting missile. Instead, take every such missile and every target and run all of them on micro-pulses at once. It's no harder on the CPU - in fact, it's easier if there are multiple missiles going after the same ship.
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.
You might even consider doing the same with potential fleet interceptions, come to think of it. Just use detection distance instead of detonation distance, and all the math is the same. Check to see if someone is going to see someone else as the first thing in the pulse, and if the answer is yes, break down into smaller sub-pulses (but no smaller than 5 seconds, of course). That solves the bug where fleet detection can be late, especially if the game's moving in 30-day increments. Probably isn't really necessary, but since you're writing the code anyway, you could see how much overhead it adds. (Although, figuring out which pairs of fleets need to be checked is non-trivial. That... yeah, that might kill this notion.)
Title: Re: A Dilemma on Interception Mechanics
Post by: chrislocke2000 on December 12, 2011, 08:13:33 AM
Quote
I tried 1) last night. A ship moving at 350 km/s launched at a second ship moving across its path at 700 km/s and under constant acceleration. The missile reached 1200 km/s, which was its set max speed, and homed in. It actually hit the target ship

Quick question on the mechanics of the above, does the missile calculate expected location before or after actions of the ship? Ie if I change my ships velocity in the tick before the last 5 seconds will this force a miss as my ship will no longer be where the missle projected it to be at that stage?
Title: Re: A Dilemma on Interception Mechanics
Post by: Elouda on December 12, 2011, 08:35:47 AM
I would imagine the missile would attempt to accelerate to compensate for any changes, so afterwards?

This would offer an interesting balance between high-efficiency missiles built for long range high velocity strikes, and high-acceleration missiles capable of handling even very maneuverable targets...

Of course, the optimal designs then becomes a 2 stage with a high-efficiency booster and high-acceleration warhead.
Title: Re: A Dilemma on Interception Mechanics
Post by: sloanjh 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
Title: Re: A Dilemma on Interception Mechanics
Post by: 3_14159 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. )
Title: Re: A Dilemma on Interception Mechanics
Post by: Elouda 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: PTTG 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: Mormota 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: Yonder 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: chuckles73 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: PTTG 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"?
Title: Re: A Dilemma on Interception Mechanics
Post by: Yonder 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: chuckles73 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
Title: Re: A Dilemma on Interception Mechanics
Post by: bean 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: Nathan_ 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.
Title: Re: A Dilemma on Interception Mechanics
Post by: Catty Nebulart 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 (http://answers.unity3d.com/questions/192261/finding-shortest-line-segment-between-two-rays-clo.html), though for missile interception you'll want to handle the parallel case separately, T=0 would be a bad choice for missile interception.
Title: Re: A Dilemma on Interception Mechanics
Post by: exdeathbr 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.