Fractal Softworks Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Starsector 0.97a is out! (02/02/24); New blog post: Simulator Enhancements (03/13/24)

Pages: 1 ... 23 24 [25] 26 27 ... 32

Author Topic: Optimizing the Conquest: a Mathematical Model of Space Combat  (Read 24621 times)

Vanshilar

  • Admiral
  • *****
  • Posts: 585
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #360 on: January 04, 2023, 03:09:11 AM »

For further testing here is a more challenging problem
- a beam with a chargeup over 1 second, travel time 1 second, chargedown of 1 second, burst size of 1 second, stores 7 ammo, after that regenerates 1 ammo / 7 sec in clips of 3

...
Let's manually check the first numbers
1. takes 1 second for beam to arrive - this is incorrect in my code, I notice that the beam is missing a check for travel time so travel time is only applied for guns. The fix is quite simple, add a "+ traveltime" to the time coordinate. However, I'll present the original output here.
2. During the first second, ticks 10 times during chargeup with quadratically increasing intensity, so the intensity adjusted ticks during the first second should be sum{i from 1 to 10} (i/10)^2, so 3.85
3. Then fires 1 second at full intensity, so 10 ticks.
4. Then from the next tick starts charging down, so sum{i from 9 to 0}(i/10)^2, so 2.85 ticks.
5. Then the next chargeup is delayed by 1 tick, so we have sum{i from 9 to 0}(i/10)^2 = 2.85 ticks during the next second, then the beam bursts for 10 ticks, then charges down with the 1 extra tick so 3.85 ticks during the chargedown.

I am not actually sure that this is how it works. The quadratic intensity during chargeup and chargedown was empirically determined by Vanshilar from combat data, not something we know the exact math of from the code, although the difference is only 1 tick. But it could be that chargedown should also be 3.85 ticks (first tick is at full intensity) or that chargeup should also be 2.85 ticks (first tick is at 0 intensity). The way it is now is an average of the two possibilities.

If anybody knows, let us know the exact math.

The damage is at 0 DPS (and 0 slope) at the beginning of chargeup, and full strength DPS at the end of chargeup, with the same in reverse for chargedown. The hit strength stays constant throughout (at half of the full strength DPS). So the total damage is simply 1/3 of the full strength DPS times the time of the chargeup. So a beam with a chargeup of 2 and DPS of 300 will do a total of 2*300/3 = 200 damage, hit strength 150, over those 2 seconds.

Beam travel time is usually pretty fast. The slowest beams extend at 2400 su/s, with the fastest at 1000000 su/s (Paladin PD). Compare that with projectiles which are usually from 500 su/s to 1200 su/s. So I'm not sure if it's really worth modeling the extension speed of beams.

Beams are charging up in intensity as they extend. So in your example (1 second chargeup, 1 second travel time), the first tick would do 0 damage (since the beam is still extending), and then do full damage for a second, then do 1/3 damage for a second, all with a hit strength of DPS/2.

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?

The armor cells are squares. What the game does is have an invisible grid of armor cells overlaid with the ship's collision bounds. The grid extends into the empty space around ships. So generally speaking, you can assume that hits to armor/hull occurred on the polygon that makes up the ship's bounds, and thus to the related armor cells. There may occasionally be hits elsewhere (such as if a ship phase skims onto a projectile, or a fighter fires a missile "inside" of an enemy ship), but most of the damage will be on the collision bounds.

So if you're looking to model the shape of the target shape, it should be sufficient to look at the part of the collision bounds that the weapon can "see", then calculate the angular diameter of each armor cell that each part of the bounds is in, and that makes up the probability that each armor cell in that grid gets hit.

In general though I think you might want to consider whether or not the effort to make it more accurate is worthwhile. For example, generally speaking you're going to be looking for how to lay out the weapons for a frontal assault. Conquest of course is a broadside ship so it would be from the side. The enemy ship is not necessarily going to be perfectly facing you but you can approximate it as being fairly close. Etc. You can gradually work the analysis to be more accurate over time instead of trying to account for everything in the initial version.
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #361 on: January 04, 2023, 04:26:53 AM »

All right, thanks for explaining. I do think it is reasonable to go for a more limited model now. You really know this stuff. Do you have any knowledge of AI behavior? Specifically, which guns the AI prefers to fire at the target.

About the beam ticks, here is the question: don't beams tick every 1/10th of a second rather than in real time? So if, for example, the chargeup lasts 10 ticks, and the beam is at 0 strength at the start of it and full strength at the end of it, then rather than integral (0 to 1) x^2dx = 1/3, wouldn't it be the Riemann sum: sum(k=1 to 10) (((k-r)/10)^2), where r refers to which point you are calculating the intensity at? (if first tick's intensity is 1/10 then r=0 and the last tick is at intensity 1 for a total of 3.85 ticks and if it is 0/1 then r =1 and the last tick is at intensity 81/100 for a total of 2.85 ticks, and if we go for the midpoint the first tick is at intensity 1/20 and the last tick is at intensity 361/400, and the total ticks are 3.325). And of course we would approach 10/3 ticks as beam ticks approach continuous.
« Last Edit: January 04, 2023, 04:28:37 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #362 on: January 04, 2023, 07:10:50 AM »

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.

Good point.  Let's save the harder math for later if ever.

Quote
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

Tricky, ain't it?  :o

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #363 on: January 04, 2023, 10:04:30 AM »

I got the exact info from Alex. He says he thinks it is 1/3/7 weapon points for small/medium/large weapons and half points for PD weapons and the AI maximizes this value when pointing guns.

Note that he was very clear this is not a description of the decision making process in the real game as a variety of different factors are considered when rotating the ship in real combat. But it is the weapon choice logic.

We can implement this quite easily: instead of calculating max dps, calculate max weapon points by maximizing points for weapon * hit probability (ie. area under curve, the thing we are already calculating).

The final product should definitely also include an option to manually input the rotation as a player would use weapons differently, and to plot the DPS at angles graph. However, since this is the AI's logic, I am of the opinion that it should be our logic for comparing the strength of ships in general, as that is what those ships would do in combat in general (if they were fighting immobile slabs of metal and ignoring everything except the target, but you know).

Re: how many different connected spaceship armor grids can exist: it is actually not the same as snake, because snakes can't branch. It's this https://en.m.wikipedia.org/wiki/Polyomino . Amazingly enough no general formula is known, so we don't know how many ships you could make with 100 cells (but the number is humongous).
« Last Edit: January 04, 2023, 11:06:40 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #364 on: January 04, 2023, 11:37:32 AM »

I am surprised to learn Alex uses 'weapon points' rather than direct DPS calculation, though I suppose his approach is more flexible because it implicitly (though only presumptively) includes such non-DPS effects as On-Hit Effect.  I wonder how our algorithm would perform against his on the DPS-only vanilla weapons.  If we could beat his algorithm, I wonder if we could ask him to expose the relevant 'sockets' to the API for us to publish a mod.  ;D

A one-cell-thick armor slab as wide as the target is a good first approximation of its armor; a good first approximation of the width would be the difference between the greatest and least x coordinates of the bound vertices in the ship file.

intrinsic_parity

  • Admiral
  • *****
  • Posts: 3071
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #365 on: January 04, 2023, 01:34:50 PM »

I haven't been following closely for a week or two because I've been busy with other things. Is all of this just to figure out what rotational orientation to put the ship in so that the most weapons/DPS are available?

I'm seeing stuff about random rotational states... that seems highly unnecessary.

If you want to get super detailed modeling rotational states, you can just copy the algorithm the game uses. Other than that, a fixed rotation state based on the loadout to maximize DPS or weapons points or whatever seems both relatively easy and reasonably realistic.

Also, I feel like for any ship with hardpoints (which is a large fraction of them), it's all pretty trivial anyway.
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #366 on: January 04, 2023, 08:45:16 PM »

Yeah, since the AI uses weapon points, then maximizing weapon points is the way to go. Don't we basically have all of the pieces to put it together then, Liral? If we are not adding depth to the enemy ship then we might just as well characterize our ship as pointlike, really, so use code as is.

I have a new idea about armor which involves this observation: you can reconstruct the armor state from pooled ADR adjusted damage to middle cells using simple rules (distribute the damage to the armor as usual). So, all information that is necessary to consider wrt armor must be coded in the armor starting parameters and damage to middle cells. Then if we can construct a description of ADR at middle cells in terms of ADR adjusted damage at middle cells we have a new way to describe armor (in terms of pooled damage, not an armor matrix). I'll let you know if it goes anywhere.
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #367 on: January 04, 2023, 11:00:18 PM »

Yeah, since the AI uses weapon points, then maximizing weapon points is the way to go. Don't we basically have all of the pieces to put it together then, Liral?

Note yet.

Deployment:
-Can freeze from MacOS to MacOS and, in principle, from anything to anything else

App:
-Opens a window that shows some text
-No user interface in the window

Database:
-Walks over all folders in mods
-Reads weapon_data.csv and ship_data.csv and converts their strings to data types
-Reads .ship files as .json

Analysis:
-Does a single weapon
-No shields
-Not fully object oriented

Quote
If we are not adding depth to the enemy ship then we might just as well characterize our ship as pointlike, really, so use code as is.

With weapon tracking arcs modeled, though, right?

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #368 on: January 04, 2023, 11:19:02 PM »

Yeah, with weapon tracking arcs using the code that we have. Basically you toss in the weapons that the ship is going to use, use the code to produce the hit distributions at optimum angle, and then use those hit distributions for the simulation. To save time, it would be reasonable to say that if a weapon has more than a 99.9% chance of missing (so, sum of the final and first cell of hit distribution is more than this) you discard it from the model.

I do not really know how to make a user interface or an application or what object oriented means so I am of limited help with these other problems. I do think it would be kind of interesting to learn and I even looked up a programming course but they literally made me choose between that and abstract algebra and well, uh, it's not really a fair contest, sorry. Some day!

Here is an idea of how I think the program should flow:

1. User modes: test single weapon, test single ship layout, test collection of weapons, test collection of layouts, diagnose weapon / layout.
2. Import data from Starsector files
Process for modes 1-4:
3. Select ship layout that we are using and target ship
4. For our ship, find the weapons that we are using, their facing and their tracking ability.
    Note if a weapon is in a hardpoint, since that will halve its spread.
    For target ship, find ship width, shield width, horizontal number of armor cells, armor stat, hull hp, max flux, flux dissipation, shield upkeep, and shield efficiency.
    Do we want the opponent to also have a layout including capacitors, vents and hullmods?
5. Using our code, find the weapon facing of choice for the AI (same method as optimum DPS but using weapon scores).
    Compute hit distributions at this facing. Discard weapons that have more than 99.9% chance to miss.
6. For the weapons we are keeping, compute shot time sequences.
7. Run the combat simulation vs. target ship in discrete time. For each second:
    - Calculate all incoming damage
    - Block it with shield if you are able to and increase flux by shield damage * shield effectiveness.
       If you did, dissipate only soft flux at rate flux dissipation - shield upkeep.
       If you did not, dissipate soft flux, then hard flux after soft flux, at rate flux dissipation.
    - If can't block with shield, deal damage to armor and then to hull.
    - End simulation when hull hits 0 and record time to kill.
8. Repeat for the requested collection of items to be tested and opponents. Print time to kill statistics for the requested collection of items.
Process for mode 5:
3. Using weapon data, calculate and print the DPS spread at angles with an SD of 0, and, if the user requests, the time to kill for that weapon vs some variety of ships.
Process for mode 6:
3. Using weapon and layout data data, calculate the DPS at angles for the layout with an SD of 0, as well as an indicator of the facing the AI would choose, and,
   if the user requests, the time to kill for that layout vs. some variety of ships.


There is, in fact, one more step. When the combat module is done, the adjustable parameter for SD should be calibrated vs. simulation data. It will likely be smaller than what I had due to our simulation being more accurate now.

However, you know much more about programs than I do, so I think it is smarter if you design what it should do and how it should go, and I'll help if I can!
« Last Edit: January 05, 2023, 03:21:32 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #369 on: January 05, 2023, 11:52:16 AM »

Good news.  I have made a clickable MacOS app!  I will try to have it run our tests when I click it.

Edit: It runs one of the tests and displays a result from it in a window, demonstrating the principle that the app can run our code and show the results.  Now to add fields and buttons.

Edit 2: I can't cross-compile to Windows easily.  Any suggestions would be appreciated.  Am on MacOS.
« Last Edit: January 05, 2023, 07:59:50 PM by Liral »
Logged

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #370 on: January 05, 2023, 08:30:46 PM »

Will it help if, when the source code is done, I compile it on Windows?
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #371 on: January 05, 2023, 09:05:31 PM »

Will it help if, when the source code is done, I compile it on Windows?

Oh, you have Windows?  Neat! :D  You would have to install Python, plus the project dependencies, and a code freezing tool, then run the freezing tool on the code from the command line.

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #372 on: January 05, 2023, 09:08:43 PM »

Well, I think I can manage that, so I can build it on Windows when that would be useful. Just tell me which things to install when the time comes.
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

CapnHector

  • Admiral
  • *****
  • Posts: 1056
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #373 on: January 07, 2023, 12:18:36 AM »

It occurs to me that it is fine to assume infinite flux capacity while testing weapons, but we may not wish to do so for ship variants. Unfortunately the current code can't really handle weapon flux as the time series is no longer dependent on weapon only but is dynamic and also dependent on weapon angle.

The logic is, of course, fire only those weapons that can hit. Only fire if you can afford to. Otherwise delay firing until you can. What makes it dynamic is there is only one flux pool but several weapons. And also ammo will regenerate even when weapons do not fire.

I wonder if this would be a task more easily realized with these objects you have mentioned rather than arithmetic?

The basic mode of operation should still be fine - generate a time sequence of gunfire up to the time limit. However must devise a way to account for flux pool.
« Last Edit: January 07, 2023, 12:34:31 AM by CapnHector »
Logged
5 ships vs 5 Ordos: Executor · Invictus · Paragon · Astral · Legion · Onslaught · Odyssey | Video LibraryHiruma Kai's Challenge

Liral

  • Admiral
  • *****
  • Posts: 717
  • Realistic Combat Mod Author
    • View Profile
Re: Optimizing the Conquest: a Mathematical Model of Space Combat
« Reply #374 on: January 07, 2023, 03:10:25 AM »

Good news!  I have made the app into a searchable database.  Type in your mod_id or 'vanilla', type in your identifier, toggle ships or weapons, and hit search to fill a scrollable box with all its stats, including the .ship file contents if it's a ship.

It occurs to me that it is fine to assume infinite flux capacity while testing weapons, but we may not wish to do so for ship variants. Unfortunately the current code can't really handle weapon flux as the time series is no longer dependent on weapon only but is dynamic and also dependent on weapon angle.

The logic is, of course, fire only those weapons that can hit. Only fire if you can afford to. Otherwise delay firing until you can. What makes it dynamic is there is only one flux pool but several weapons. And also ammo will regenerate even when weapons do not fire.

I wonder if this would be a task more easily realized with these objects you have mentioned rather than arithmetic?

What objects do you mean?  Shot, Ship, etc.?

Quote
The basic mode of operation should still be fine - generate a time sequence of gunfire up to the time limit. However must devise a way to account for flux pool.

For ship versus ship combat, we would have to iteratively increment time and recalculate until the end of the fight.  Supposing we could get away with 10 increments per second and an average fight of 100 seconds, we would need an average 1,000 increments per fight.
Pages: 1 ... 23 24 [25] 26 27 ... 32