[Jodavaho.io]

Optimizing Ship Load-outs for Highfleet: Problem Setup

Dec 13, 2023

Over-engineering Highfleet load-outs using Integer Programming

I built a highfleet ship optimizer by bundling a fast C optimizer, binding to a higher level language, and providing a web API. Then, Altho built a front-end. Try it at hfopt.jodavaho.io/optimizer

This post is about setting up the problem. See related posts.

Highfleet is an incredibly fun game. You take control of a small set of ships, raid and pillage and revolt your way to glory. Along the way you must carefully manage your resources to keep your ships repaired, and customize them to the situation at hand. Lovely time.

view full post

game-tools games highfleet math optimization

Over-engineering Highfleet load-outs using Integer Programming

I built a highfleet ship optimizer by bundling a fast C optimizer, binding to a higher level language, and providing a web API. Then, Altho built a front-end. Try it at hfopt.jodavaho.io/optimizer

This post is about setting up the problem. See related posts.

Highfleet is an incredibly fun game. You take control of a small set of ships, raid and pillage and revolt your way to glory. Along the way you must carefully manage your resources to keep your ships repaired, and customize them to the situation at hand. Lovely time.

The most addicting part, as is common in this genre¹, is the ship design and customization. You can fully tailor your fleet to your desired play style! Instead of rave about the gameplay, let’s talk about how you design ships.

Ship Design Problem statement

In Highfleet, you can “pre-design” ships before starting a campaign. You have a limited starting budget, so you need to balance power, weight, engines, guns, ammo types, layout, crew capacity, sensing, etc, to get the desired range, speed, firepower, survivability, and combat time, while minimizing cost. This problem is masterfully posed by the developers, and has hooked a small community for years.

I’m interested in automating this, to a certain extent. Can we at least come up with an optimal module set - and leave the layout / cosmetics to the creative user? Staring at the above paragraph, one might see this is a classic optimization problem². Words like “minimize”, “select”, “all while …”, “such that”, etc are clues.

We can re-state above as:

• Select zero or more whole modules from a list
• Such that the modules have all their requirements satisfied (e.g., engines have fuel, guns have ammo)
• all while minimizing cost
• and satisfying some desired final ship stats

Easy. Formulating the problem is half the battle.

Solving

To solve a problem like this you need the defining equations:

• A “cost” function. In this case, it’s literally the dollar value of each module - easily obtained by writing down the values from the game. This is also called the “Objective Function”.
• The “feasibility constraints”, which essentially answer: Is this a valid ship at all? Without these, we could choose modules that seem to satisfy constraints, but would never fly in-game. For example: “Do we have enough ammo feeds to keep the guns working”, this again we can copy down from in-game stats
• The “trade space equations”. In this case, we want to know the following: How does the selection of modules affect the desired final ship stats like Range, Speed, Firepower, etc. This turns out to be very hard, but doable with help.
• We also want the “desired stats”, which are just “constraints” we impose on the trade space. We’ll get this from the users as a set of valid ranges (e.g., speed is greater than X, weight is less than Y, blah blah)

Great - all we need to do is reverse-engineer how the in-game stats are calculated. easy right? Instead, I reached out to the game developer, and r/highfleet, to see what they could share. Everyone had some models, and Koshutin didn’t reply. So, I had to do it myself for the most part.

Reverse Engineering the Game Stats

For completeness, here is the list of relevant stats, obtained by parsing the ship files (which deserves its own post).

aavalue, airspeed, ammobox_need, ammobox_total, at_left, at_right, b.x, b.y, combatvalue, crew_capacity, crew_need, dynamic, dynamic_landing, dynamic_map, dynamic_map_repaired, firepower_guns, fss_capacity, fss_total, fuel, fuel_capacity, fuel_need, fuel_need_cr, fuel_on, hp, hp_integral, hp_max, mass, parts, parts_integral, power, power_need, power_real, power_total, power_total_repaired, price, r, signature, signature_ir, signature_rd, thrust_left, thrust_left_landing, thrust_left_map, thrust_left_map_repaired, thrust_right, thrust_right_landing, thrust_right_map, thrust_right_map_repaired, weapons_on

Some we can throw right out. b.x, b.y for example make no sense to me. Some (weapons_on) probably have more to do with the campaign mode than the performance. Some (airspeed, r) are exactly what we want to reverse engineer and optimize for.

My explorations were fairly crude. I’d download many of the fan-made ships from reddit or discord, check the stats, make a spreadsheet, and start plotting to see if the relationships were obvious. Some guesses were obvious (airspeed should be a function of thrust/weight, which it was). Some were not (range (r?), in particular).

For forming the equations, some unit analysis really paid off. For example, range ultimately (sensibly) was essentially:

$$ r \approx C_1 \cdot \frac{ \text{fuel_capacity} }{ \text{fuel_consumption} } \cdot \text{airspeed} + C_2 $$ which has units meters- note the unknown constants though³. Determining the constants is a job for linear regression! I won’t plot out the details, you can see them here.

At this repo you can see how it worked. Note this file with ship data, hand crafted! It has a sparses set of stats manually pulled from ships. Just enough to confirm the relationships. Once I had those I could pull up any ship from reddit or discord, and verify it. It was always close enough. Of course, I have to re-do this every time the game balances, but soon, I’ll automate this - another post to write.

I did discover some hidden features this way, did you know generators require fuel? Makes sense, but at the time this was undocumented.

So, that’s how I was able to pin down the relationshps for the “desired stats” from the game files. Next, we can formulate the optimizer.

Mr. Koshutin, if you are reading this, thank you for letting the community enjoy your game in this way. You certainly didn’t have to!