MinimumQuotaFinder

Co-created by @Luesewr and @riceisacereal

This mod calculates and highlights the minimum total value of scraps that you can sell to still reach the quota. The default key to trigger the mod is H, but this can be changed in the settings.

The same in essence as: ScrapCalculator
Scrap auto-selling mods: SellMyScrap, SellFromTerminal

✨ 𝓦𝓱𝓪𝓽 𝓸𝓾𝓻 𝓶𝓸𝓭 𝓭𝓸𝓮𝓼 𝓫𝓮𝓽𝓽𝓮𝓻

• Always finds the most optimal answer quickly (5ms to 1s depending on quota and number of items) using an optimized algorithm.
• Cool highlighting shader

Quirks of the way the mod works

• When you're on the company moon, all scrap in the environment is taken into account (including scrap on the counter), unless its y-value is under -30 (somehow dropped over the railings). Otherwise only scrap within the ship is considered.
  • Pros: You can take items outside the ship on the company moon and they will still be included in the calculation.
• Calculation assumes that you are selling when the company is buying at 100% (it's too complicated otherwise due to rounding per batch requiring you to sell in a specific order of batches, and we don't want to go down that road).
• This is a client-side mod, which means that there is a small chance of different items being highlighted for different people. We have several methods in place to prevent this from happening, but you never know.
  • If this happens, report an issue and tell us how it happened.

Explanation of Algorithm

The problem

The problem this mod tries to solve - finding the most optimal combination of scrap that is the closest to the quota, is a variant of the subset sum problem and has a computational complexity of NP-Hard, which in a very generalized way of saying means that there is no easy formula to get the answer right away and that we have to find it by "trying every combination".

The number of possible combinations for all the scrap you have grows exponentially, by the time you have 20 pieces of scrap you will have to check over 1 million combinations, and 1 billion when you have 30 pieces of scrap. When you're up to 5k+ quota it will take half your lifetime to check all combinations with even if you check 1 million combinations per second.

Algorithms for NP-hard problems utilize ways to ignore certain combinations, and storing the results of calculations that are repeated multiple times. An example of the former would be, if you have a quota of 1000, and we know that the highest value a scrap can have is 210, we could ignore any combinations that have less than 5 pieces of scrap, since they would never reach the quota (4 * 210 = 840 < 1000).

The Algorithm

The algorithm we've implemented is very similar to the solution to the 0-1 knapsack problem which uses dynamic programming and memoization. The only difference is that the knapsack problem tries to find the maximum <= a threshold, and since we need the minimum of >= quota, we ran the knapsack solution on a threshold of (total value of scrap owned - quota) to find what we should exclude. (Thanks to this Stackoverflow answer for the idea.)

Computation Time Scaling

The 2 factors that determine how long it takes to calculate an answer are the value of the quota, the number of scrap, and the total value of that scrap. The algorithm goes through a table the size of (total value of scrap owned - quota) * number of scrap, so the bigger the difference between your quota and the total value of all your scrap, and the more scrap you have, the longer it takes to calculate.

Performance Impact

To prevent the game from freezing while doing large calculations, the mod makes use of coroutines. These coroutines spread out the calculations over multiple frames and limit the number of computations ran per frame.

Credits

This mod was built using the BepInEx mod template. Part of ShipLoot mod's code was taken as a starting point. InputUtils was used to make the keybinding. This Wireframe Shader was used as a basis for the custom wireframe shader.

Installation

Thunderstore link

Changelog

v1.1.4

• Fix bug where direct target would be taken as actual target to calculate leading to suboptimal results

v1.1.3

• Fix edge case where the lowest valued scrap would be highlighted when the quota was already reached

v1.1.2

• Remove scrap spawning functionality used for debugging that was accidentally left in

v1.1.1

Features

• Shotguns, Ammo, and Gifts will no longer be taken into account for the calculating/highlighting.

v1.1.0

Features

• Added instruction for highlighting to the HUD tooltips (top right corner) when first joining a file and when scanning within the ship or on the company moon
• Made it so that highlighting can not be triggered when outside the ship on non-company moons (you can still unhighlight)
• Made it so that scrap on the counter at the company moon is counted as sold directly as these can't be taken off the desk
• Added auto-recalculation when the wrong scrap is put on the counter

Optimizations

• Added direct target calculation with greedy approximation on top of inverse target calculation
• Added a way for the algorithm to terminate early if an optimal solution has already been found

Bug fixes

• Fixed render distance of wireframe material on all scrap items
• Fixed wireframe material on moving parts of scrap items
• Made highlight button spam proof
• Stopped highlighting on company moon when buying rate is not at 100% to avoid inaccuracies

Documentation

• README
  • Added instructions in case of selling wrong scrap
  • Added more explanation and justification for assuming 100% buy rate
• Add CHANGELOG

v1.0.1 2024-1-30

Structural

• Changed file structure
  • Moved wireframe out of AssetBundle folder and into root because Thunderstore somehow got rid of the folder and placed it in root

Documentation

• Emphasized the keybind in README
• Changed description and version number in .csproj

v1.0.0 2024-1-29

• Initial version