Gazz wrote:One of the early interviews about Rebirth mentions the region about capital ships being divided into quadrants. Not sure if they meant 4 or 8 but the basic idea is that a fighter AI can assess the danger of a particular approach more easily (if not as accurately) if it only has to decide between 4 or 8 zones.

Sounds reasonable, although, as with most things, I will probable take a Monte-Carlo approach here for a number of reason. I will take n randomly-chosen sample angles, compute the target ship's "threat" rating for each angle, and select the minimal. I prefer methods like these because it scales perfectly: increasing the number n increases the intelligence of the AI, period. We can scale it back to save CPU, or to create the impression of a dumb AI, or whatever. And, as a bonus, we can easily gain more accuracy than the Rebirth AI - 64 samples wouldn't even be pushing it.

Gazz wrote: In my experience with turrets it is more advantageous to have "a bunch of" turrets guided by a local fire control system. Fire from slightly different angles (especially from a large ship) can "flank" a target and still have a chance to hit it even if it starts evading.
OTOH, you lose accuracy because not every individual turret makes an optimal choice.
It's a lot less fiddly, though, because the player can control / design a handful of batteries instead of dealing with 30 "individually intelligent' turrets.

The number of installed fire control nodes would be a balancing option, increasing the number of targets that can be tracked simultaneously.

Those systems would be a prime vulnerability on such a ship whereas it would be an unfun amount of work to take out every single turret.
Damage is "cooler" if it's something tangible rather than some vague, tiny bit. Losing one or two small turrets is basically irrelevant but losing one of your two starboard batteries is a distinct tactical problem that the player (or the AI) can deal with.
If you want to avoid that, you can build more redundancy into the system if you invest into more control nodes. At a cost. Valid trade-off in your ship design. Redundancy is good. Redundancy is good.

Well, I'm going to have to disagree with you entirely on this one As a player, when I finally work up to a battleship, I'm going to want my turrets to be really good at what they do. I've been doing tests for hours, pitting a battleship against swarms of fighters. In the early days, when turrets tracked as one, my hulking battleship couldn't even handle a swarm of 20 fighters - they could take it out. Now, with separate tracking + smarter calculation, my battleship can regularly win against 100 well-armed fighters, which I think is fair, because it will probably cost more than 100x! Naturally, that doesn't mean that every turret is always tracking a different ship - sometimes it is advantageous to double or triple up, depending on the probabilities computed. But the point is that the massive war machine that you shelled out for is performing optimally.

Also, it's still very fun, and taking out a turret is still a big deal! I have watched enough battles now to be able to say that, even when all turrets are tracking separately, a single turret lost on a 12-turret batleship is a big deal. Now, if you've done your homework beforehand and know which turrets are which, you're in even better shape. If you've seen the ship in engagements before, you might also even have some idea of which turret is the most "dangerous," based on the geometry of the ship / occlusion of the turret. Point being, turret kills can still feel empowering!

Ultimately, the reason that my mind cannot be changed on this matter is that I've been watching this battleship for hours now, and I still can't get over how absurdly cool is looks to see all those turrets tracking and firing separately...locking on, nailing the fighter out of the sky, and moving on to the next one. It's awesome. Really. I enjoy it far too much

I agree with your thoughts on sensors, implementation is yet to be determined, because there's a good bit of complication surrounding sensors / visibility at the moment (thanks to ye olde physics engine).

Okay, turrets pick their targets individually.

Still wondering if "fire control systems" could be used to provide a local bonus.
Maybe turrets that are not "in range of one" fire less accurately.

Even if your fighter doesn't have the firepower to take out all heavy turrets on the capital ship, maybe you can throw off it's aim a bit and give your own ship a better chance?
The cap ship would then probably have a shorter "best range" and close in to compensate.

JoshParnell wrote:Well, I'm going to have to disagree with you entirely on this one As a player, when I finally work up to a battleship, I'm going to want my turrets to be really good at what they do. I've been doing tests for hours, pitting a battleship against swarms of fighters. In the early days, when turrets tracked as one, my hulking battleship couldn't even handle a swarm of 20 fighters - they could take it out. Now, with separate tracking + smarter calculation, my battleship can regularly win against 100 well-armed fighters, which I think is fair, because it will probably cost more than 100x! Naturally, that doesn't mean that every turret is always tracking a different ship - sometimes it is advantageous to double or triple up, depending on the probabilities computed. But the point is that the massive war machine that you shelled out for is performing optimally.

...

Ultimately, the reason that my mind cannot be changed on this matter is that I've been watching this battleship for hours now, and I still can't get over how absurdly cool is looks to see all those turrets tracking and firing separately...locking on, nailing the fighter out of the sky, and moving on to the next one. It's awesome. Really. I enjoy it far too much

At the same time, you're forcing a better mouse (see 'if someone builds a better mouse trap, someone else will build a better mouse', etc).

By making it smart, you're forcing the tactical hand. While you haven't yet implemented it yet, I'm sure if you adapted your tracking algorithm to take into account different ship types, and then toss a few bombers to the mix, it'll be even more fun.

I'd really be interested to see how to outsmart the enemy that way.

Been there, done that.
One time I evaluated the MARS script in X3.

A vanilla destroyer wouldn't have a snowball's chance but the same destroyer with MARS would win against 20+ fighters and 2 M6 thrown in for good measure.
The target prioritizing by lateral vector (and other factors) was a wholly new ballgame.

Same with missiles. A vanilla M2 would have a hard time surviving a barrage of maybe 40 torpedoes.

In a test series with a MARS M2, the M2 had about a 40% chance to survive... a total of 400 torpedoes simultaneously fired from 3 missile frigates from different directions, so that the entire attack would impact more or less simultaneously.


That's the difference that even the most basic and inaccurate calculations can make...


One of the consequences were a missile mod or two that made them considerably faster and meaner. =)

JoshParnell wrote:I haven't yet had any good insights on how to perform the calculation of intersecting spherical sectors...maybe soon though

It's just occurred to me, there should be a single iterative solution.

Each sphere's path is a vector, which translates to cartsian coords that change wrt time. That means their separation translates to a vector, also cartesian wrt t - a well-behaved polynomial. The derivative of that is the rate of change of separation wrt t, and that's just an equation root that needs solved. Use a second derivative and plug it into a Newton Raphson iteration to find t_min, hence sep_min. Again, you can avoid any SQRT until the end, so it's int-friendly.

Now you have their minimum separation and trivially the sphere radii which are linear wrt t. The effect will depend on how the radius matters for that munition, e.g. probability exponential with radius or straight spherical volume overlap.

Gazz wrote:I do wonder if "intersecting spherical cones" isn't already taking it too far.
How about doing a linear target lead prediction for the target but a spherical cone for the projectile (because that one is relatively easy to nail down)?
Then, depending on how fast / maneuverable / big the target is, you randomise the target point's location around the computed lead point.

I may be a bit late in answering that old post, but I like the idea and want to expand it a bit.

Linear lead prediction - makes sense. I would not change that.
Spherical cone for the projectile - this one can handle

• The spread of the bullets, as inherent in the gun (seems to be zero in X3, if I hold down the trigger all bullets fly the same way).
• The ability of the target to do evasive maneuvers, derived from speed, acceleration and turning rate. I'm glossing over the exact formula for now

The first one is obvious. The second needs some explanation:
It does not matter (much) if the aim of the gun is wrong or the target veers to the side - either leads to the shot being off target by an angle alpha. Now we have two such angles, lets call them alpha_gun and alpha_evade. If we dare to assume they are independent of each other, and also normally distributed, we can combine them into one alpha_miss. http://en.wikipedia.org/wiki/Normal_distribution gives some formulae.

Now we have a relatively simple distribution for how much the shot is off target. It is not perfect (the normal distribution for alpha_evade contains a small probability for really drastic maneuvers the target cannot perform), but probably good enough for simulating OOS combat.

Next, we need an approximation of the angular diameter delta (http://en.wikipedia.org/wiki/Angular_diameter) of the target. I guess the approximation delta = d / D (for small delta) will be good enough. A somewhat harder problem is getting an "equivalent angular diameter" for irregular shapes.

But assuming the solution for those details I've glossed over is found, we have now

• the angle alpha_miss
• and the interval delta in which the shot will hit. If alpha_miss is within -delta/2 and +delta2, the shot will hit. Outside, it will miss.

P_hit can then be calculated as the cumulative distribution function of alpha_miss at (+delta/2) minus the cumulative distribution function at (-delta/2).

I realize the above leaves some details unresolved , but I hope it is useful anyway.

Rabiator wrote:I may be a bit late in answering that old post, but I like the idea and want to expand it a bit.

Linear lead prediction - makes sense. I would not change that.
Spherical cone for the projectile - this one can handle

• The spread of the bullets, as inherent in the gun (seems to be zero in X3, if I hold down the trigger all bullets fly the same way).
• The ability of the target to do evasive maneuvers, derived from speed, acceleration and turning rate. I'm glossing over the exact formula for now

The first one is obvious. The second needs some explanation:
It does not matter (much) if the aim of the gun is wrong or the target veers to the side - either leads to the shot being off target by an angle alpha. Now we have two such angles, lets call them alpha_gun and alpha_evade. If we dare to assume they are independent of each other, and also normally distributed, we can combine them into one alpha_miss. http://en.wikipedia.org/wiki/Normal_distribution gives some formulae.

Now we have a relatively simple distribution for how much the shot is off target. It is not perfect (the normal distribution for alpha_evade contains a small probability for really drastic maneuvers the target cannot perform), but probably good enough for simulating OOS combat.

Next, we need an approximation of the angular diameter delta (http://en.wikipedia.org/wiki/Angular_diameter) of the target. I guess the approximation delta = d / D (for small delta) will be good enough. A somewhat harder problem is getting an "equivalent angular diameter" for irregular shapes.

But assuming the solution for those details I've glossed over is found, we have now

• the angle alpha_miss
• and the interval delta in which the shot will hit. If alpha_miss is within -delta/2 and +delta2, the shot will hit. Outside, it will miss.

P_hit can then be calculated as the cumulative distribution function of alpha_miss at (+delta/2) minus the cumulative distribution function at (-delta/2).

I realize the above leaves some details unresolved , but I hope it is useful anyway.

Interesting thoughts! But the major question that it raises for me is, why can you roll the uncertainty in the target's location and the uncertainty in the bullet's trajectory into a single spherical cone? This part is mathematically non-obvious to me, and I'm not sure I buy it.

If it were just a spherical distribution, for example, I would agree that we can combine them. But these are directional distributions, i.e., the bullet's conical distribution is pointed one way, and the target's distribution another way - I'm not seeing how you could simplify the difference of those two distributions into a single one? I'm pretty sure you cant

At any rate, another problem that we run into if we start using normal distributions rather than uniform, is that the solution now requires integration over a manifold, which...err...seems like it might be a bit too heavy-handed for this. If we assume a uniform distribution, the solution is just a question of intersection.

Hmm yes,
I may have confused the two-dimensional with the linear superposition of two normal distributions .
I'm currently at work so I cannot put too much time into it, but maybe I can find a formula that is backed up by an actual deduction tonight.

Not making any promises yet, as formula wrangling was always a bit of a weak point in my university maths. But I will try .

A spherical cone.

What if you use something similar to a silhouette approach? We know when an object is within that sphere by the shadow it casts upon the edge of the sphere itself. If the randomness of a projectile trajectory dictates the size of that cone, and we have a silhouette of a ship against the edge of that cone, can we then use percentages of how much of the "floor" part of the cone is being covered and use that?

OK, next attempt with hopefully better mathematics...
I'll assume something similar to a spherical cone, but with normal distributions for the evasive movement of the ship and the spread of the gun.
We have separate, normally distributed variables for the error angle resulting from the movement of the ship, alpha_evade_x and alpha_evade_y.
For both, the mean is zero (before movement of the ship, our aim was perfect). The blue diagrams show the probability density.

We also have separate, normally distributed variables for the error angle resulting from the spread of the gun, alpha_gun_x and alpha_gun_y.
For both, the mean is zero (the gun is sighted in well, but that cannot eliminate the spread). The red dots illustrate the shot placement:
Most are near the center, but we have a few outliers too.

I'm also daring to assume the above variables are all independent , and that the deviations along the z-Axis (closer or more distant) can be neglected for calculating P_hit .

Now the resulting total aiming error alpha_miss is
alpha_miss_x = alpha_gun_x - alpha_evade_x and
alpha_miss_y = alpha_gun_y - alpha_evade_y.
Subtraction because if they go in the same direction, they cancel each other out.


For the part that follows now, I'll rely a lot on Wikipedia, because I don't remember that much of my statistics classes .
Wikipedia says (http://en.wikipedia.org/wiki/Normal_dis ... l_deviates):

Also if X1 and X2 are two independent normal random variables, with means μ1, μ2 and standard deviations σ1, σ2, then their sum X1 + X2 will also be normally distributed, with mean μ1 + μ2 and variance σ1² + σ2².

If we believe that, we can deduct that alpha_miss_x and alpha_miss_y are also normally distributed, with a mean of zero and a variance that is easily calculated from the variances of the original distributions of alpha_gun and alpha_evade

Next, we need to make the jump from separate distributions to a two-dimensional one. That is where you caught me . New attempt, and I'm relying on Wikipedia again. This time on http://en.wikipedia.org/wiki/Chi-squared_distribution.
We have (hopefully) established above that alpha_miss_x and alpha_miss_y are normally distributed and independent. Now Wikipedia says that the sum of their squares follows the chi-squared distribution with two degrees of freedom. Next comes some heavy-looking mathematics, but if I understand it correctly, the resulting cumulative distribution function (CDF) is a one-dimensional curve you could pre-calculate and store in a lookup table.

If we apply the good old Pythagorean theorem, the sum of the squares can be interpreted as the square of the total alpha_miss over both dimensions. So for a given angle beta, you can compare its square to the CDF of the chi-squared distribution and get the probability of a shot having a greater alpha_miss than beta.

Now if the target ship has an "equivalent angular diameter" of delta, you can make the above comparison with beta = delta/2 and get P_hit from the lookup table. That still leaves the little problem of calculating the "equivalent angular diameter" for an irregular shape , but otherwise the algorithm looks clear to me now.

That's it, and I hope my train of thought is verifiable now. If it looks correct to you (or at least close enough for an OOS fudge), feel free to use it .

P.S.: The spaceship in the crosshairs is © 2010 Brett Fitzpatrick, created for Vega Strike and licensed under Creative Commons. Credits where credits are due

I'm also daring to assume the above variables are all independent , and that the deviations along the z-Axis (closer or more distant) can be neglected for calculating P_hit .

That is quite a daring assumption, if we are correct in counter-assuming that LT weapons will have maximum ranges (Josh is not using a friction-less/near-total vacuum space physics model), as we have seen in the Dev Updates. Consider then that the target could very well be riding the outer range threshold of the gun (or perhaps outside of max range?), together with Josh's explicit assertion that a z-Axis (distance to target) is necessary to P_hit:

Calculating P_hit... must take into consideration many factors: the distance between the weapon and the target...

..granted, as you say, this would be "an OOS fudge", but uhh, perhaps a little too much fudge?

Rabiator, I really appreciate the detailed response. I read it shortly after you posted and it has been in the back of my mind ever since. It's really a clever intuition, and I think there are some valid concepts that can be extracted. Any way of being able to think about this problem that involves something as mathematically-nice as summing Gaussians is definitely worth exploring. As Baile nam Fonn says, the consideration in terms of only angles is a bit distressing, and it's the main point that has had me puzzled. Trying to convince myself that we can really transform this problem into a purely-2D angular one is going against all of my 3D intuition, but then again, I don't doubt that there is a "close" approximation floating somewhere out there in 2D.

Ooook, looks like I have some more explaining to do. Maybe I took too much for granted .

One unwritten assumption was that the "bullets" are much faster than their targets, and the evasive movements a target can make before the bullet hits are small compared the range of the weapon.
So I neglected the likelihood that a target could escape being shot by increasing the distance from the gun. Which is certainly a fudge (a target close to maximum range may be able to gain the few meters of distance needed to be safe), but hopefully not too much of a fudge for OOS purposes.
Edit: evasive movements are on top of the linear prediction of the target's path. By all means, keep the linear prediction. I'm assuming the turret AI handles linear prediction perfectly, and only evasive maneuvers make a difference. If the linear prediction alone puts the target out of harm's way, let's assume it stays unharmed.

I also neglected the change in "equivalent angular diameter" resulting from the distance between gun and target changing. Which is based on the same assumption that the "bullets" are much faster than their targets. That is another thing that is not 100% accurate, but probably less critical than getting the "equivalent angular diameter" right. Unfortunately, I still don't have a good idea for calculating that from the shape of the target (and for different aspects to boot) .

Based on the above simplification, it follows that only the lateral maneuvers of the target help it to escape being shot. My next mental leap was to express this as "apparent angle". Lets say the distance between gun and target is dist meters and the target manages to move evade meters to the side. Then you can model this as a right triangle (http://en.wikipedia.org/wiki/Triangle#Right_triangles), with the legs being dist and evade, and the hypotenuse being the new distance dist_new between gun and target.

Enter the sine function:
As viewed from the gun, the evasive maneuver of the target has put it at an angle alpha_evade to the path of the bullet, which can be calculated as sin(alpha_evade) = evade/dist_new. If sin(alpha_evade) is fairly small, some further approximations apply that say alpha_evade in radians is roughly evade / dist.

Now we have arrived at the alpha_evade from the picture in my last post. Assuming that it follows a normal distribution is really a WAG (wild-ass guess) by me, as I don't know much about real life fighter jets and their evasive habits . I suspect some physics calculations would be needed to determine the lateral distance evade_max the target could reach in a given time, and some additional experimentation to get a reasonable constant factor to go from evade_max / dist to the standard deviation of alpha_evade.

Looks pretty conceptually solid to me, but then my own math hat & coding hat are both bargain basement rubbish that I wouldn't dream of donning in public. So I have no idea whether this would be either a clunky or an elegant solution.

One unwritten assumption was that the "bullets" are much faster than their targets, and the evasive movements a target can make before the bullet hits are small compared the range of the weapon.

Unless I badly misunderstood Josh, I think his intent was to employ P_hit across the whole range of possible turrets, including (comparatively) low velocity, long range missiles (as seen in this Dev Update). Though the extreme case which appeared in yesterday's dev log may not make the cut for the game (in spite of Josh making it sound like a really fun bomber gameplay option ), you'll immediately see what kind of a monkey wrench this will toss into the machinery.

Having looked again at Josh's P_hit Dev Log from waay back in the hazy past of February 5 , I've got it pretty well clear in my mind that P_hit isn't meant to be bothered about targets that aren't in range of the given turret or even concern itself with a turret tracking speed < lateral target movement situation (the AI would've opted not to take the shot in either case?), so at least that's (possibly) out of the way. Unless Josh has been working his noodle to try and consolidate that stuff in his relentless quest for code bloat extermination .

Hmmm.. my brain is hurting just trying to visualize what a consolidated P_hit with other range considerations might look like, or whether such a beastie is even remotely viable. As I said above, donning any of my shabby "smart stuff" hats would quite inevitably prove fatal to my delicate ego in the end .

Perhaps if the AI decided quite independently of P_hit whether it was going to bother taking the shot anyway based on some sort of quick "effective range" calculation, you could legitimately take z out of P_hit.. but I fear that Josh would balk at this, as even to me it smells, well, suspect of non-elegance.

Baile nam Fonn wrote:Looks pretty conceptually solid to me, but then my own math hat & coding hat are both bargain basement rubbish that I wouldn't dream of donning in public. So I have no idea whether this would be either a clunky or an elegant solution.

I think it is a reasonable approximation in concept, but with some kinks that still need working out. The biggest one being the leap from a silhouette changing with the aspect of a ship to the "equivalent angular diameter". So there is still some mathematical refining to do.

Baile nam Fonn wrote:

One unwritten assumption was that the "bullets" are much faster than their targets, and the evasive movements a target can make before the bullet hits are small compared the range of the weapon.

Unless I badly misunderstood Josh, I think his intent was to employ P_hit across the whole range of possible turrets, including (comparatively) low velocity, long range missiles (as seen in this Dev Update).

Well, I think that at (comparatively) low velocity, long range my concept tends to fall apart, because the approximations I made are no longer appropriate. It does not cover guided missiles at all, those will need a separate formula for P_hit.

Baile nam Fonn wrote:Hmmm.. my brain is hurting just trying to visualize what a consolidated P_hit with other range considerations might look like, or whether such a beastie is even remotely viable. As I said above, donning any of my shabby "smart stuff" hats would quite inevitably prove fatal to my delicate ego in the end .

Perhaps if the AI decided quite independently of P_hit whether it was going to bother taking the shot anyway based on some sort of quick "effective range" calculation, you could legitimately take z out of P_hit.. but I fear that Josh would balk at this, as even to me it smells, well, suspect of non-elegance.

That is where the "linear prediction" Josh mentioned comes in. I understand it works like this (without math):

• 1) Assume the current course and speed of the target will stay constant
  2) Based on the above assumptions, calculate the point where a perfectly aimed bullet would hit the target

Now you have the approximate range at the time of impact. If it is greater than the range of the gun, assume the bullet does evaporate before it hits. Do not bother with the P_hit calculation. A smart AI might decide not to shoot at all in this case.

If the linear prediction shows the target is in range, apply the P_hit calculation.