Post
by **jcranmer** » Sat Jun 08, 2019 5:07 pm

If you want to understand how stuff like Kirk Mcdonald's calculator works, here's the actual math that goes down. (I've built a similar tool to his tool for personal use, so I have very good knowledge of the underlying details).

Let's start with a simple example. Suppose you want to make a red science pack. How many resources does it require? We can write down some equations:

1 red science = 1 iron gear + 1 copper plate

1 iron gear = 2 iron plate

With basic algebra, we can substitute the second equation in the first equation to get it in terms of our input resources:

1 red science = 2 iron plate + 1 copper plate

Green science looks more intimidating:

1 green science = 1 inserter + 1 yellow belt

1 inserter = 1 green circuit + 1 iron gear + 1 iron plate

2 yellow belt = 1 iron gear + 1 iron plate

1 green circuit = 3 copper cable + 1 iron plate

2 copper cable = 1 copper plate

Nevertheless, algorithmically, we can arrive at the answer by rewriting complex items in terms of simpler items and substituting as much as possible. There are lots of calculators out there for Factorio, and all of them will use this very basic core. Each recipe is an equation, and each item is a separate variable.

You'll note that I did the math here using units of resources. A lot of the use of calculators is for determining how many machines you need, which requires units of resource per time. To get those equations, we just divide the equation of a recipe by the crafting time of the recipe; since red science takes 5 seconds to craft, we arrive at an equation of ⅕ red science per second = ⅕ iron gear per second + ⅕ copper plate per second. Assemblers also have crafting time, which requires multiplying the equation by the crafting speed, and speed modules interact in the same way. Productivity modules require multiplying only one side of the equation--the outputs--by the productivity boost, which is not a linear effect and why they're so powerful.

If you step back a bit, what we're solving here is a set of linear equations, so we can apply linear algebra to the mix. We're trying to solve a matrix equation Ax = b, where b is a vector of the desired output in terms of resources per minute, x is a vector of the number of required factories, and A is a matrix which encodes all of the recipes. In the matrix A, each column corresponds to a recipe, each row an item, and each value is positive if the corresponding recipe produces that item, negative if it consumes it, or 0 if it's not directly involved. The recipe matrix is a sparse (nearly) triangular matrix, and the algorithm I discussed above is how you go about solving sparse triangular matrices.

There is one big wrinkle, though. I said that the recipe matrix is nearly triangular, and the "nearly" part matters in a big way. In vanilla Factorio, there are two violations of triangularity: oil and uranium. These violations means that we can't satisfy all desired output constraints: it's impossible to produce 10 heavy oil/second and no petroleum gas/second, for example. So we have to slacken our request for equality into an inequality; we want to solve for Ax ≥ b instead of Ax = b. It's now clear that we can have potentially infinite solutions to the inequalities, so we also want to pick the best solution, defined as minimizing c·x for some cost vector c. A reasonable cost vector for Factorio is to use the power consumption of each recipe; you can also minimize raw resource consumption with a balancing factor for the easy availability of water, but power consumption tends to automatically factor that in. This process is known as linear programming; it also adds in by default constraints that x≥0, but that's precisely what we want anyways (negative factories don't make sense).

So then, the most correct way to do the calculation is to create a linear program with the recipe matrix, desired final production rates, and cost vector, and then pass it to a tool capable of doing sparse linear programming. I will not get into the math of how solving linear programs works (it's very much in the category of "don't code this yourself"), but I will close with a useful tidbit. Solutions to linear programs must exist on one of the vertices of the polytope implied by the constraints. It turns out that the oil submatrix in vanilla Factorio produces 4 outputs (solid fuel, heavy oil, light oil, petroleum gas) for 8 recipes (3 refining recipes, 2 cracking, and 3 solid fuel recipes). Any vertex can only include 4 of these eight recipes. Considering that solid fuel consumption requires one of those recipes, and you need a refining recipe, that means you're either doing both cracking recipe (and converting only one oil type to solid fuel), or converting multiple things into solid fuel in lieu of cracking.