Detecting conservation, loss, or gain in a crafting game with items and recipes

Question

Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\rightarrow I\times\mathbb{N}$, that is they take some items with non-negative integer weights and produce an integer quantity of another item.

For example, the recipe for cake in Minecraft is:

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

... and the recipe for torches is:

1 stick + 1 coal $\rightarrow$ 4 torches

Some recipes could even be reversible, for example: 9 diamonds $\leftrightarrow$ 1 diamond block

If there's some combination of recipes we can repeatedly apply to get more of the items that we started with then the game is poorly balanced and this can be exploited by players. It's more desirable that we design the game with recipes that conserve items or possibly lose some items (thermodynamic entropy in the real world - you can't easily un-burn the toast).

Is there an efficient algorithm that can decide if a set of recipes will:

• conserve items?
• lose items to inefficiency?
• gain items?

Is there an efficient algorithm that can find the problematic recipes if a game is imbalanced?

My first thoughts are that there is a graph structure / maximum flow problem here but it's very complex, and that it resembles a knapsack problem. Or maybe it could be formulated as a SAT problem - this is what I'm considering to code it at the moment but something more efficient might exist.

We could encode recipes in a matrix $\mathbf{R}^{m \times n}$ where rows correspond to recipes and columns correspond to items. Column entries are negative if an item is consumed by a recipe, positive if it's produced by the recipe, and zero if it's unused. Similar to a well known matrix method for graph cycle detection, we could raise $\mathbf{R}$ to some high power and get sums of each row to see if item totals keep going up, stay balanced, or go negative. However, I'm not confident this always works.

Any discussion, code, or recommended reading is very appreciated.

Answer 1

This should be solvable with linear programming.

Background and setup

Let the state vector be a vector of the count of number of each item you have. If the possible items are milk, wheat, sugar, egg, cake, diamonds, then the rule

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

affects the state vector by adding $(-3,-3,-2,-1,1,0)$ to it. So, let $a_i$ denote the change vector for the $i$th rule.

Gaining items

I claim that there exists a way to gain items without bound iff there exists a feasible solution to the linear program

$$a_1 x_1 + \dots + a_n x_n \ge (0,0,\dots,0), x_1 \ge 0, \dots, x_n \ge 0$$

such that $a_1 x_1 + \dots + a_n x_n>(0,0,\dots,0)$. Here $\ge$ is defined on vectors pointwise (i.e., $u \ge v$ iff $u_i\ge v_i$ holds for all $i$) and similarly for $>$. This can be expressed as a linear program: you maximize the sum of the coordinates of $a_1 x_1 + \dots + a_n x_n$, subject to the inequalities above. Therefore, you can solve it in polynomial time using a linear programming solver. This tells you whether there is a way to gain some item without bound.

Why is the claim true? Well, if there is a feasible solution to the linear program, then it provides a way to grow the number of some item without bound. In particular, if you start with a very large number of each item, then apply rule 1 $x_1$ times, rule 2 $x_2$ times, etc., you'll end up with a new state vector that differs from where you started by $a_1 x_1 + \dots + a_n x_n$, which is at least as large in each component and is strictly larger in at least one component. Moreover, if you start with a sufficiently large number of items, you'll never "go negative" at any intermediate step of application of the rules. Note that if there is a solution to this linear program, there is a solution in the rationals, which yields a solution in the integers (multiply by the appropriate constant to clear denominators).

Conversely, if there is a method to grow the number of some item without bound, then there is a solution to the linear program: just let $x_i$ count the number of times rule $i$ is applied in that method, and you'll see that this yields a valid solution to the linear program.

Losing items

I believe that there is a similar equivalence: there exists a way to lose items without bound iff there exists a feasible solution to the linear program

$$a_1 x_1 + \dots + a_n x_n \le (0,0,\dots,0), x_1 \ge 0, \dots, x_n \ge 0$$

such that $a_1 x_1 + \dots + a_n x_n<(0,0,\dots,0)$. You should check my reasoning as I have not checked this carefully.

Conservation

Finally, if there is no way to gain items without bound or lose items without bound, then I think it follows that value is conserved.

Answer 2

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$.

(Notice that the order of the operations doesn't matter: Running them in some order might cause the quantity of some item to dip below zero, but we can just look for the low-water-mark and suppose that we have at least that many of each item to start with.)

I think this can be solved by linear programming: Make a variable for each coefficient, add $\ge 0$ constraints for each element in the output vector (each element is a dot product of coefficient variables and constant coefficients from recipes), more $\ge 0$ constraints for each coefficient variable, and set the function to maximise to be the sum of all elements. To make it bounded, set the sum of coefficient variables to some constant, e.g. 1. Iff the solution value is $> 0$, you have non-conservation!

Note that fractional values are not an issue: They must be rational, so you can always multiply through by all denominators to get a pure-integer solution.