Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Liral]

All right, great job! Seems like we now have the tools to import and analyze ships, at least to a degree of precision.

Woooooooo!   Yaaaaay! Hahahaha.  Thank you so much.  Here's what we have more specifically:

- a data pipeline to import all the data from vanilla (and some mods) without having to launch Starsector
- the analytics to evaluate how combinations of closely-spaced weapons perform against unshielded slab-sided armor at long range
- a (hopefully-portable) app we could modify to let you press a button to run the pipeline and analytics

By the way, and you probably know this but just to be sure, the code is in no way fixed to right = 0 degrees. It can be anything so long as all the ships and guns use the same reference point, for example if 0 is straight ahead in game files (I have no idea) then that is fine so long as it is the same for all ships.

Oh, well that's fantastic news.

Want to wander into projective geometry to implement more complex shapes or proceed with this?

I wonder if the following pre-calculations might also help:

1. Gather the collision bounds of the ship.
2. Create an armor grid shaped for the ship.
3. Map each outer armor grid cells to its adjacent bound.
4. For each outer armor grid cell,
    a. Draw a line from its four corners to each weapon
    b. If any of these lines does not intersect a non-adjacent bound
        i. Do arbitrary math here to assign how much fire this armor cell would take

That arbitrary math could have plenty of quick and convenient approximations, too.  Speaking of performance, I should note that scientific computing time is freely available from many online cloud providers, so we can use more than a potato if sorely pressed.

Happy new year!

Happppppyyyyy newwww yeaaaaaaar!

P.s. attached is how I imagine you might go about it. (If it should turn out to be difficult to formulate rules for which index to use from which direction using just 1 cell index, the alternative computation is just calculate cell distance from gun and hit nearest when the boundaries of multiple cells overlap. It might be that we have to do that because the rules for cell selection could be unclear for guns at the middle. (Edit: removed idea about using modular arithmetic and integers for this as euclidean distance might be more practical later if we want to e.g. add range)). The indices are a little wrong in the picture but the idea is that you would number cells from back to front and from right to left if the gun is to the left, and left to right if gun is to the right. Then you would find the corners of all cells projected to the circle. Then you find all overlaps. Then for all overlaps you select the highest cell number as the cell which will be hit. Then you calculate the probability distribution over the resulting line of cell bounds and map the hits to the ship armor grid. And the mathematical question is does this procedure always result in hitting the nearest cell in terms of euclidean distance among those whose projections to the circle overlap.  (I should think so when the ship is to the side, because let's say the enemy ship is rectangular. Then the vector from our ship to cell 1 is (x, y). Then let's say that the number of a particular cell is ar+c, where a is the number of rows, r is the number of cells per row, and c is the column index ie. the remainder of cell number / r. Then, the vector from cell 1 to that cell is (-sa, -sc) if s is the side of an armor cell. Without loss of generality we can say s=1. Then the euclidean distance to the cell from our ship is sqrt((x-a)^2+(y-c)^2). Now let's say that a cell has a shorter euclidean distance but a lower index. Then it must be the case that either a or c is lower (or both). But then it follows that the euclidean distance is greater. Then the question is does this apply to ships of an arbitrary shape. Most likely so, because we might conceptualize of the arbitrary shape as a rectangle but with cells that can't be hit, and if a cell can't be hit then the task is to find the highest index in the rectangle behind it. However, how to define the index when the enemy ship is not to one side but in the middle of our field of fire?)

But, as stated, I don't really think this is necessary to publish for now and it might lead to some work, so your call. It does seem like it will be pretty computationally intensive compared to what we have now.

See above idea to perhaps make it easier.

[CapnHector]

Right. Adding shields to the model should be almost trivial. Just keep track of time and soft and hard flux and use the shield on/off algorithm above described.

The idea you described sounds quite reasonable. However there is a big obstacle to implementing all of these: I have no idea how the ship's armor grid relates to its geometric shape in general terms. Vanshilar gave the horizontal size of armor cells but what about the vertical? And is there padding and how does it works? Anybody know about this?

[Liral]

Right. Adding shields to the model should be almost trivial. Just keep track of time and soft and hard flux and use the shield on/off algorithm above described.

Which algorithm would that be?  I can't find it easily by typing "shield" into the search-bar of this thread.

The idea you described sounds quite reasonable. However there is a big obstacle to implementing all of these: I have no idea how the ship's armor grid relates to its geometric shape in general terms. Vanshilar gave the horizontal size of armor cells but what about the vertical? And is there padding and how does it works? Anybody know about this?

I have a guess.  Rather than thinking of the armor grid having a 'real' part 'inside' the ship with 'padding' sticking out, think of the ship bounds as being centered in and drawn on a grid of square cells, each of which has an associated armor value, which begins equal to the ship's armor rating / 15.  When a shot hits the bounds of the ship, find which cell the shot is in and pool, calculate, and distribute according to the matrix and grid laid out earlier.

[CapnHector]

Seems reasonable. However, this method also leads to a hit to the ship being able to damage cells across a gap in the ship (e.g. imagine a ship that consists of two parallel lines of armor cells 1 cell width apart, then with this algorithm hits on either line will also damage the other). Is that how it works?

Also, another case, does that mean that for a ship shaped like a triangle, the armor grid is shaped like a stepped pyramid, with hittable armor cells everywhere where at least 1 pixel of the triangle exceeds a grid boundary? Alternative version: say that somebody has specified a ship that is exactly 1 armor cell wide and 1 armor cell + 2 pixels long. Does this ship have 1, 2 or 3 hittable armor cells? For example if the logic is center the ship on a grid of square armor cells, then add hittable armor cells to all squares where the ship has a nonzero area, then this would have 3 armor cells with shots parallel to ship length hitting different cells depending on direction and shots parallel to ship width hitting mostly one cell. And another: say that someone has made a ship that is square and the size of 1 armor cell, but rotated it 45 degrees so it is oriented like a diamond. Does this ship have 5 different hittable armor cells?

The algorithm for shields is
1. At the start of each second, compute incoming damage
2. Then if you can block without overloading, do so, and deal all damage that second to shields, otherwise to armor
3. If you did not block, dissipate first soft and then hard flux equal to flux dissip stat. If you did, soft flux only and equal to flux dissip - shield upkeep.

There is still the question of what to do with ships with different dps optimum angles vs shield and armor. One step at a time I guess. There are broadly four different strategies: 1. ignore, 2. assume ship always uses optimum (can rotate instantly), 3. compute some kind of an index beforehand to determine which to use for the whole combat (optimal rotation when unable to rotate), 4. rotate the ship based on some kind of a threshold with the rotation taking actual time (pseudo-ai).

It occurs to me that there is a terrifying possibility that is permitted by options 3 and 4: what if the optimum angles are angles that are neither the highest dps vs enemy shields nor the highest vs armor?. For example imagine a ship that rotates extremely slowly and has a fixed gun that deals 399 energy dps straight ahead, and two other fixed guns, one dealing 200 kinetic dps to the exact left and one dealing 200 he dps to the exact right. It seems like the correct choice for this ship would be to not rotate at all using options 3-4, but we would not find this choice using the dps at angles function we have now, just checking dps vs shields and dps vs armor...

I suppose we would find this maximum by computing an "average real dps vs shields and armor" which would be something like shield dps*shield efficacy - shield regen vs shields and the solution f'(1) to f'(t)=dps*hit strength/(hit strength+armor -f(t)) vs armor and then maximize the average of those two, possibly weighed with something.

At this point it might be helpful to know how the game's AI makes that decision. Because it probably doesn't involve solving this but rather something like "point biggest gun at target". If we knew that we could just replicate the process since that is the most valid way to do it even if it doesn't lead to mathematically optimal damage.

[Liral]

Seems reasonable. However, this method also leads to a hit to the ship being able to damage cells across a gap in the ship (e.g. imagine a ship that consists of two parallel lines of armor cells 1 cell width apart, then with this algorithm hits on either line will also damage the other). Is that how it works?

Come to think of it, our previous approach would damage the cells on both sides too.  We would need to check whether each cell of the 'splash' of armor damage 'crossed' a bound before applying it to cells inside the bounds of the ship; oof, that step would multiply the work at worst 25 x the number of ship bounds, which are at least 4 and possibly as high as 40, for 100 to 1,000 extra operations per shot per ship.  Maybe we could check whether this check is necessary once per ship and then consider it only when necessary.  Even then, with worst case 100 outer armor cells, that check in and of itself would be 10,000 to 100,000 steps per ship at startup.  We might have to use caching.   

Also, another case, does that mean that for a ship shaped like a triangle, the armor grid is shaped like a stepped pyramid, with hittable armor cells everywhere where at least 1 pixel of the triangle exceeds a grid boundary? Alternative version: say that somebody has specified a ship that is exactly 1 armor cell wide and 1 armor cell + 2 pixels long. Does this ship have 1, 2 or 3 hittable armor cells? For example if the logic is center the ship on a grid of square armor cells, then add hittable armor cells to all squares where the ship has a nonzero area, then this would have 3 armor cells with shots parallel to ship length hitting different cells depending on direction and shots parallel to ship width hitting mostly one cell. And another: say that someone has made a ship that is square and the size of 1 armor cell, but rotated it 45 degrees so it is oriented like a diamond. Does this ship have 5 different hittable armor cells?

It's not about exceeding a grid boundary, though.  If any corner of an outer armor cell is within range of a weapon, and if a line from that corner to that weapon does not cross a bound not adjacent to that cell, then that cell is at least slightly exposed to that weapon, and we can do arbitrary math.

The algorithm for shields is
1. At the start of each second, compute incoming damage
2. Then if you can block without overloading, do so, and deal all damage that second to shields, otherwise to armor
3. If you did not block, dissipate first soft and then hard flux equal to flux dissip stat. If you did, soft flux only and equal to flux dissip - shield upkeep.

Aha, thank you!

There is still the question of what to do with ships with different dps optimum angles vs shield and armor. One step at a time I guess. There are broadly four different strategies: 1. ignore, 2. assume ship always uses optimum (can rotate instantly), 3. compute some kind of an index beforehand to determine which to use for the whole combat (optimal rotation when unable to rotate), 4. rotate the ship based on some kind of a threshold with the rotation taking actual time (pseudo-ai).

Here we get into questions of aggression versus defense as well: should you face the enemy with your toughest armor or best weapons?  Probably just rotate toward optimum each step.

It occurs to me that there is a terrifying possibility that is permitted by options 3 and 4: what if the optimum angles are angles that are neither the highest dps vs enemy shields nor the highest vs armor?. For example imagine a ship that rotates extremely slowly and has a fixed gun that deals 399 energy dps straight ahead, and two other fixed guns, one dealing 200 kinetic dps to the exact left and one dealing 200 he dps to the exact right. It seems like the correct choice for this ship would be to not rotate at all using options 3-4, but we would not find this choice using the dps at angles function we have now, just checking dps vs shields and dps vs armor...

I suppose we would find this maximum by computing an "average real dps vs shields and armor" which would be something like shield dps*shield efficacy - shield regen vs shields and the solution f'(1) to f'(t)=dps*hit strength/(hit strength+armor -f(t)) vs armor and then maximize the average of those two, possibly weighed with something.

At this point it might be helpful to know how the game's AI makes that decision. Because it probably doesn't involve solving this but rather something like "point biggest gun at target". If we knew that we could just replicate the process since that is the most valid way to do it even if it doesn't lead to mathematically optimal damage.

We might have to ask Alex.

[CapnHector]

Yeah we are going to have to ask Alex or somebody else who knows, because look at this sucker:



It COULD go for 4*500 + 1*200 + 4*150 = 2800 DPS vs shields from 4 Heavy Needlers, 1 Graviton Beam and 4 IR Pulse Lasers.

Instead it prefers to blast the shields with 2x 60 + 2 x 125 DPS vs shields from 2 Hellbores and 2 Heavy Maulers. I tried this test 5 times vs the Dominator and 2 times vs the Aurora and the behavior is identical. Were it to go for the mathematical optimum it would make some somewhat different choices.

Of course it could be the range, which causes it to assume an incorrect position initially and then persist, since I didn't follow through to see what happens as the fight goes on, and whether it would correct itself, but it shows that it's not sufficient to just assume the AI will home straight to the optimum.

Anyway, settling this might take a while, so want to wrap up a pre-release where player sets ship angle manually for ship tests and that is suitable for weapons testing?(this should be much less confusing if it can print out a dps at angles graph) Might also get others interested.

[Liral]

Yes, let's ask Alex and wrap a pre-release for now.

[CapnHector]

All right, I sent a PM to Alex and we'll see if he responds. I can understand if he doesn't feel like revealing this stuff, though.

Here's some further thoughts on the hitting cells thing. Won't be programming it in the near future as there is something slightly more pressing right now so just tossing this out there. I am not particularly great at geometry (or more like don't know anything about it) so there are probably much smarter ways of doing this.

[attachment deleted by admin]

[Liral]

Coordinate pairs of real numbers would be simpler to understand and implement than complex numbers, and I suspect the armor grid could even more simply be rectangular, with each cell containing a boolean indicating its being an outer shell within the ship bounds.  Then we could vectorize the calculation to:

1. Falsify cells outside the bounds
2. Falsify all still-true cells surrounded by true cells
3. Determine which true cells are affected.

Here's a catch to any approach: the normal distribution we've added to the uniform spread distribution approaches but never quite reaches zero.  Therefore, any cell on the entire weapon-side of the ship might be hit.  How do you want to handle this issue?

[CapnHector]

It is not in fact true that all cells could be hit with the normal distribution.

The problem should be handled like this, to use the example of one rectangle:

- project the rectangle to the circle defined by the gun and range
- apply the probability distribution to coordinates (be it angles or pixels) on the circle
- when there is an overlap in the projection you hit the closest point using whatever metric you desire, be it a system of indexing or euclidean distance

It is never possible to hit the other side of the ship, because you only consider the closest point of the enemy ship. The rest are behind the closest points so unhittable even if there is an error. (Unless we go out of our way to model this possibility by adding both an x and an y directional error)

To explain a little further, our probability distributions only work in one dimension. So when we are collapsing a two dimensional object to one dimension we will have overlaps. We must have one rule to deal with these overlaps. The natural rule is hit the closest because anything else is not what happens in the game. As a result you only hit those points visible from the gun unless we add another dimension to the distribution.

Wait, my bad. You mean any cell on the side of the enemy ship near our ship could be hit. Yes, this is true, but just statistics. The normal distribution really means error from the perfect situation of alignment and no movement. In extremely rare cases we might be extremely off. But this should make it more realistic, not less because we are not in the perfect situation in the game, hence the normal dist.

In a sense it would be more realistic to be able to hit the back of the enemy ship with very small probability, because the enemy ship is also not always rotated towards us. Don't particularly feel like implementing that though, but I guess if you were using the euclidean distance to cell as the metric to see which cell you hit, then you would add an error to that distance, maybe? Of course the real solution with no hacking would be to have the boundaries of the enemy ship include a random rotational error. Or even more appropriately go back to the Brownian motion idea but with rotation.

By the way, re-examining the fundamentals really makes me wonder: given that we have a probability wave of damage acting on an armor, is there really no simple solution, say, something like a propagating wave, that describes the armor state? The equation for a single cell is f'(t)=max(0.15d, hd/(h+max(0.05 starting armor/15, a-f(t))). For an entire armor matrix it can be expressed as a matrix differential equation using the matrix notation presented above. But I'm out of my depth here for the time being again and also need to work on figures for some paper again. Still, food for thought.

I mean it seems like there should be a single equation when we have a fixed effect acting repeatedly on a bunch of cells characterized by one value with fixed rules of how they interact with one another.

[Liral]

I'm confused because I understand applying the normal distribution to mean that the ship is is at one angle but might be at another: what angle would the armor cells be at over those angles at which the ship only might be?  I suppose we could find a formula for what cells would be exposed around a ring of ship angles for a weapon of uniform spread, but then might we not as well use those results directly?

[CapnHector]

Well, if we are using the normal distribution as is and using the coordinates projected to the circle arc, then we are essentially saying the enemy ship's position has a random normal error but it is along the same arc and the same for all cells. But in reality this is an assumption of convenience: if the enemy whip's angle is uncertain then other cells might be exposed. And if the enemy ship is further away then not only does that affect range but also the armor cells' projections would be smaller. We"fix" this by adjusting the SD parameter until it matches the results from simming. But what should happen in reality is in fact the error is applied to enemy ship's position and rotation before the projection as you say, you are correct.

Where that leads us though were we to go that route is calculating a uniform distribution over some bins whose parameters (and also which bins are available) are normally distributed. I am not sure how to do that.

This could be done numerically though, but the problem is there is theoretically an infinite number of possible ships. Or if we restrict ourselves to a 20x20 armor grid, then 2^400-1 ships. So pre-computing is not an option. (If we restrict ourselves to ships that are continuous, then it actually becomes the following math problem: given a n x n grid, using one color, in how many different ways can you color any number of cells so that all colored cells are connected?)

[Liral]

Uh-oh.  Maybe we should change our approach to avoid these problems.  I have one idea: modifying the normal distribution, perhaps by constraint to +- 90 degrees or +- spread arc from the weapon direction,  or ignoring it entirely might reduce geometric complexity. 

[CapnHector]

I'm not sure how this idea could be done without a normal distribution, because isn't that where the enemy ship's random angle is assumed to come from?

The simplest way to avoid all of these issues is to model the enemy ship as a line as we have, and note in documentation that the enemy ship is modeled as a slab of armor with defensive statistics equal to enemy ship and rotation of the enemy ship is not considered. This is unsatisfying on a level, but on the other hand we are also not currently pursuing error correction to the armor, return fire, or actual simulation of the game's AI so it will always be an approximation anyway.

Incidentally the question of how many non-discontinuous ships can exist in Starsector has been calculated by these folks:

https://iopscience.iop.org/article/10.1088/0305-4470/26/7/012

since the question is equivalent to how many snakes of length at most n can be made in the game Snake.

The number is this  http://oeis.org/A001411 (sum up to the largest permitted number of armor cells for the ship).

Edit: not actually true because we would consider two ships with the same configuration of armor cells the same ship even if they are positioned differently on the armor grid. Then we would get this: https://oeis.org/A037245

[CapnHector]

On a different note (double posting because this is very important) got a response from Alex who is officially Best Dev in history. He writes

I think it's actually "point guns with a highest possible total <value> at the target" where <value> is based on gun size and some other stuff like whether the gun needs to aim, is PD, has ammo remaining, some stuff about the target's state, etc.

When I asked about how guns would be pointed at an immobile unresponsive wall. It is more complex in real combat with various other parameters considered. Must ask about how value is calculated but it seems this is tractable.