import math
from statistics import NormalDist
"""
Calculate the optimum angle to place the enemy ship relative to ours.
Assume:
- Angle exactly to the right is 0 degrees
- Possible angles are integers from -179 to 180
- Our ship is:
- heading towards +90 degrees
- pointlike.
- The enemy ship is:
- at a constant range
- a straight line of hittable armor cells
- oriented tangentially to a circle defined by our ship's position
and range.
- The ships are so far apart that the arc across that circle, from one
point on the enemy ship to the other, approximates the secant between
those points.
"""
def probability_hit_before_bound(
x: float,
standard_deviation: float,
uniform_distribution_radius: float) -> float:
"""
Return the probability that the hit coordinate is less than x.
This probability equals the integral, from -inf to x, of the hit
probability distribution, which is
- normal if the parameter of the uniform distribution is 0
- uniform if the standard deviation of the normal distribution is 0
- trivial if both are 0, the hit distribution is trivial: the CDF
equals a step function going from 0 to 1 where x = 0.
- a normal distribution convolved with a uniform one if both exceed 0
x - real number
standard_deviation - standard deviation of the normal distribution
uniform_distribution_radius - radius of the uniform distribution
"""
def g(x: float, normal_distribution: object) -> float:
"""
Return the cumulative distribution function of the convolved
normal distribution.
x - real number
normal_distribution - a Python standard library NormalDist
"""
return x * normal_distribution.cdf(x) + normal_distribution.pdf(x)
def f(x: float,
normal_distribution: float,
uniform_distribution_parameter: float) -> float:
a = x / normal_distribution.stdev
b = uniform_distribution_parameter / normal_distribution.stdev
return (normal_distribution.stdev
/ (2 * uniform_distribution_parameter)
* (g(a + b, normal_distribution)
- g(a - b, normal_distribution)))
if standard_deviation > 0:
normal_distribution = NormalDist(0, standard_deviation)
return (f(x, normal_distribution, uniform_distribution_radius)
if uniform_distribution_radius > 0
else normal_distribution.cdf(x))
if b > 0: return (f(x, NormalDist(0, standard_deviation),
uniform_distribution_radius) if a > 0
else max(0, min(1, b / 2 + x)))
return 0 if x < 0 else 1
def probability_hit_between_bounds(
lower_bound: float,
upper_bound: float,
error_distance: float,
spread_distance: float) -> float:
"""
The probability to hit between the left and right edges of the
ship is the integral, from the lower edge of the ship to the upper one,
of the hit probability distribution. By the fundamental theorem of
calculus, this integral equals
CDF(upper edge) - CDF(lower edge).
"""
return (probability_hit_before_bound(upper_bound, error_distance,
spread_distance)
- probability_hit_before_bound(lower_bound, error_distance,
spread_distance))
"""
Referring to the width of the enemy ship in pixels but to the placement
and tracking ability of turrets as angles is convenient. Therefore, we
must convert between the two. Note that we assume we can use the arc
to describe the enemy ship.
"""
def arc_to_deg(arc: float, distance: float) -> float:
"""
Return the degree angle of an arc.
"""
return arc / distance * 360 / math.pi
def deg_to_arc(degrees: float, distance: float) -> float:
"""
Return the arc of a degree angle.
"""
return degrees * distance / 360 * math.pi
def probability_hit_at_facing(
weapon_facing: float,
spread_distance: float,
error_distance: float,
target_facing: float,
target_radius: float,
distance: float) -> float:
upper_bound = deg_to_arc(weapon_facing + target_radius, distance)
lower_bound = deg_to_arc(weapon_facing - target_radius, distance)
return probability_hit_between_bounds(upper_bound, lower_bound,
error_distance, spread_distance)
"""
A weapon cannot exceed its maximum turn angle and has constant spread;
therefore, the maximum mean points of the probability distribution of a
weapon are
{ maximum turn angle - spread / 2, minimum turn angle + spread/2 }
A weapon tracking a target tries to align the mean of the probability
distribution with the target. Therefore we can find the signed angle
of the target from the mean of the distribution by computing the
following in this order:
1. The mean point, that is, max mean, when target is above max mean
2. target, when target is between max mean
3. min mean, min mean, when target is below min mean.
4. Minimum and maximum means for the weapon and find the median of
its hit distribution ("transform hit coord" for coordinates of mean
of modified dist in terms of the original distribution)
"""
def transformed_hit_coord(
angle: float,
minimum_mean: float,
maximum_mean: float) -> float:
return max(minimum_mean, min(maximum_mean, angle))
def transformed_angle(
angle: float,
minimum_mean: float,
maximum_mean: float) -> float:
"""
Return the angle between the mean and target.
We refer to this as "transforming" since we are moving from
expressing the angle wrt. ship to wrt. weapon.
"""
return angle - transformed_hit_coord(angle, minimum_mean, maximum_mean)
def total_hit_probability(
minimum_mean: float,
maximum_mean: float,
spread_distance: float,
error_distance: float,
target_facing: float,
target_radius: float,
distance: float) -> float:
"""
Return the total probability of hitting the target per second.
Return the sum of areas under the probability distribution curve across
the target, equivalent to integrating, from ship lower angle to ship
greater angle, the probability distribution times damage for each
weapon. We use the CDF we described above.
We refer to auc (area under curve, ie. the curve of damage times
probability distribution, giving total damage) for short.
target_facing - target ship orientation
Output: total damage to target ship
"""
#we have defined spread in degrees, so we must convert it to
#pixels to be consistent
#angle of the ship's upper bound, in coordinates of the
#distribution mean; note that this is weapon specific
weapon_facing = transformed_angle(target_facing, minimum_mean, maximum_mean)
return probability_hit_at_facing(weapon_facing, spread_distance,
error_distance, target_facing,
target_radius, distance)
def weapon_adjustment_distance(
weapon_facing: float,
minimum_mean: float,
maximum_mean: float,
distance: float) -> float:
#Return the segment from the old angle plus the new angle plus
#the weapon's angle.
#the location of the weapon's mean as it tries to track the target from
#transformed_angle
angle_difference = transformed_angle(weapon_facing, minimum_mean,
maximum_mean)
return angle_difference / 360 * 2 * math.pi * distance
def hit_distribution(bounds, standard_deviation, spread):
"""Our normal hit distribution function."""
if standard_deviation == 0:
if spread == 0:
#if both spread and standard deviation are 0 then all shots hit 1 cell. this should be so even if
#the ship has an even number of cells to prevent ships with even no. cells appearing tougher which is not
#the case in the real game most likely
return 0, + tuple(1 if bounds[i-1] < 0 <= bound else 0
for i, bound in enumerate(bounds[1:]))
double_spread = 2 * spread
return (min(1, max(0, (bounds[0] + spread)) / double_spread),
+ tuple(min(1, max(0, bounds[j] + spread) / double_spread)
- min(1, max(0, bounds[j-1] + spread) / double_spread)
for i, bound in enumerate(bounds[1:]))
+ (1 - min(1, max(0, bounds[-1] + spread) / double_spread)),)
elif spread == 0:
#if spread is 0 but standard deviation is not 0 we have a normal distribution
cdf = NormalDist(0, standard_deviation).cdf
return (cdf(bounds[0]),
+ tuple(cdf(bound) - cdf(bounds[i-1]) for i, bound in
enumerate(bounds[1:]))
+ (1 - cdf(bounds[-1])),)
numbers = standard_deviation, spread
return (probability_hit_within_bound(bounds[0], *numbers),
+ tuple(probability_hit_within_bound(bound, *numbers)
- probability_hit_within_bound(bounds[i-1], *numbers)
for i, bound in enumerate(bounds[1:]))
+ (1 - probability_hit_within_bound(bounds[-1], *numbers)),)
def hit_distribution_at_optimum_angle(
spread_distance: float,
weapon_facing: float,
minimum_mean: float,
maximum_mean: float,
upper_bounds: tuple) -> tuple:
adjustment_distance = weapon_adjustment_distance(weapon_facing,
minimum_mean,
maximum_mean,
distance)
adjusted_upper_bounds = tuple(upper_bound + adjustment_distance for
upper_bound in upper_bounds)
return hit_distribution(adjusted_upper_bounds, error, spread_distance)
def main():
#Section 1. general considerations
#We will test against a Dominator. We wish to integrate this code
#with the other modules eventually, so we will use the full ship
#definition, even though only the width is needed.
target_radius = 220 #(14000, 500, 10000, 1500, 220, 12, 440, 1.0, 200)
cell_count = 12
distance = 1000
#For testing, we will give these parameters for weapons:
#damage, facing (deg), tracking range (deg), spread
#collect them in a data frame
#for this test we will add two weapons that are slightly angled
#away from each other and able to overlap in the exact middle
# and some rear mounted point defense weapons to make sure the
#wraparound, extreme angles are correct
weapons = (
{"damage" : 100, "facing" : -10, "arc" : 20, "spread" : 5},
{"damage" : 100, "facing" : 10, "arc" : 20, "spread" : 5},
{"damage" : 30, "facing" : -160, "arc" : 20, "spread" : 0},
{"damage" : 30, "facing" : 180, "arc" : 20, "spread" : 0},
{"damage" : 30, "facing" : 160, "arc" : 20, "spread" : 0},
{"damage" : 120, "facing" : 90, "arc" : 0, "spread" : 5}
)
for weapon in weapons:
weapon["spread distance"] = deg_to_arc(weapon["spread"], distance)
weapon["minimum_mean"] = (
weapon["facing"] + (weapon["arc"] + weapon["spread distance"]) / 2)
weapon["maximum_mean"] = (
weapon["facing"] + (weapon["arc"] - weapon["spread distance"]) / 2)
#We will use the same parameter for the normal distribution as
#we do in the other modules. Note that this results in the SD of
#the normal distribution being in pixels.
error_standard_deviation = 0.05
error_distance = error_standard_deviation * distance
#Now that we have all the pieces, we can perform the calculation.
#A special consideration is that we are using signed angles for the
#probability distritbutions, but in reality, the ship's guns wrap
#around, so we must devise a way to map -359 to 1, etc.
#So first, we define a vector from -360 to 360. These all possible
#angles of fire, since a gun can only have a position from -180 to
#180 degrees on the ship, and can only track 360 degrees at most.
damage_per_second_total_at_angles = [
sum(weapon["damage"]
* total_hit_probability(weapon["minimum_mean"],
weapon["maximum_mean"],
weapon["spread distance"],
error_distance,
target_facing,
target_radius,
distance) for weapon in weapons)
for target_facing in range(-359,361)]
i = 0
for target_facing, damage_per_second_total in zip(range(-359,360),
damage_per_second_total_at_angles):
print(i, target_facing, damage_per_second_total)
i += 1
#next, we go back to one loop of the ship by noting that
#-180 corresponds to +180
#-181 corresponds to +179 etc, so 360 + index for indices 1:180
for i in range(180):
damage_per_second_total_at_angles[i+360] += (
damage_per_second_total_at_angles[i])
#and +360 corresponds to 0, +359 to -1 etc. so index - 360 for indices 540:720
for i in range(540, 720): damage_per_second_total_at_angles[i-360] += (
damage_per_second_total_at_angles[i])
#finally, to get angles -179 to 180, we select indices 181 to 540 of the new vector.
damage_per_second_total_at_angles = damage_per_second_total_at_angles[181:540]
#note that vector indices no longer correspond to angles, rather vector index 1 corresponds to -179.
#to get a correct plot add this
xaxis = range(-179,180)
#the problem is solved. Now we can find the optimum angle quite simply by selecting the midmost maximum
#optimumangle = xaxis[which(round(dps_at_angles,3) == round(max(dps_at_angles),3))[ceiling(length(which(round(dps_at_angles,3) == round(max(dps_at_angles),3)))/2)]]
#plot the result
#plot(dps_at_angles,x=xaxis)
#abline(v=optimumangle)
#the usual - calculate ship cell upper bound angles
target_angle = target_radius / (2 * math.pi * distance)
cell_angle = target_angle / cell_count
angle_ranges = [-target_angle/2]
for _ in range(cell_count):
angle_ranges.append(angle_ranges[-1] + cell_angle)
#convert to pixels
upper_bound_distances = [angle_range * 2 * math.pi * distance
for angle_range in angle_ranges]
print(upper_bound_distances)
#print results
#for weapon in weapons: print(hit_distribution_at_optimum_angle(weapon))
main()
Author
Topic: Optimizing the Conquest: a Mathematical Model of Space Combat (Read 25342 times)