Disclaimer: I am by no means an expert in this sort of thing so please do correct me if I get things entirely wrong! I should also warn you that, whilst I’ll try to keep this as accessible as possible, some prior programming/comp-sci knowledge is recommended.
Back in 2018 (geesh, how time flies!) I wrote about how Autocrafting in Minecraft was NP-hard, by reducing the Boolean satisfiability problem (SAT) to Minecraft recipes. While this shows a lower bound, it does not show an upper bound.
Since then, I’ve found something a little more horrifying. Minecraft recipes are equivalent to Petri nets.
An introduction to Petri nets
Wikipedia does a far better job than I could, but in summary Petri nets are a special kind of graph, composed of two kinds of node: places and transitions, edges between these nodes, and a marking.
- Places are a store of a resource we call tokens. Each place can hold any number of indistinguishable tokens.
- Transitions move tokens between places. Transitions consume a specific number of tokens (possibly zero) from each place and convert them to a new set of tokens which we can store in a different place.
- Markings describe how many tokens are at each place. A Petri net starts with an initial marking, and the marking changes as transitions move tokens about.
This might be easier to demonstrate with a diagram. Here we’ve got a Petri net with the following:
- Three places, , and .
- A single transition , which takes 2 tokens from A and 3 from B. It then produces 1 token, sending it to C.
- Place A contains 3 tokens, B has 5 and C has 0. This is our initial marking.
After our transition fires once, our Petri net ends up with a new marking. There is now 1 token at A, 2 at B and 1 at C.
Crafting with Petri nets
If you squint a little bit, you can see how this is a bit like a crafting recipe, with places corresponding to items and transitions corresponding to recipes. Let’s swap out our places and transitions with something from Minecraft, and see what our network might look like then:
Then, if our storage system contains three sticks and five cobblestone, we’d put three tokens on our stick place, and five on our cobblestone place - just like the original figure!
It’s pretty simple to see how we could extend this for all of Minecraft’s crafting recipes, building one absolutely massive Petri net of items and recipes. We could even extend this network to contain other recipes (such as smelting) or even other resource types (fluids, exp, etc…), to build an incredibly complex model of Minecraft’s crafting system.
It’s worth mentioning here that while we’ve (informally) shown that we can reduce crafting recipes to Petri nets, we haven’t gone the other way round: can we generate crafting recipes from arbitrary Petri nets?
Technically, no. Unlike crafting recipes, Petri nets can have more than 9 inputs, and any number of outputs, and so there’s no simple bijection between the two. However, we’re going to ignore this distinction here1.
Autocrafting with Petri nets
It’s definitely nice to know that crafting recipes and Petri nets are equivalent. And, given Petri nets are of great interest to many computer scientists, surely there’s some nice tricks we can do to build powerful auto-crafting solvers?
Well, before we get onto that, let’s look at one of the common properties of petri nets, and see how it’s useful for us.
The reachability problem for Petri nets asks us whether, given a Petri net and an initial marking, if it’s possible to reach a different target marking just by firing our transitions. Or, in Minecraft terms, is it possible to craft this item given the items available to us?2.
This is definitely useful to know! In fact, it sounds just like what we’re looking for. And, even better, reachability in Petri nets is a useful problem in many domains, and so there’s been lots of research into it.
Alas, things are not as ideal as they might be. It turns out the complexity of determining reachability in Petri nets is even worse than that of SAT. Much worse.
Infinite powder, infinite states
Let’s backtrack a bit and talk about a classic Minecraft dupe bug: blaze rods and blaze powder. Vanilla Minecraft contains a recipe to convert one blaze rod into two blaze powder.
Some Minecraft mods also add a recipe to reverse this, such as using transmutation or a compressor. Other mods may also add a more efficient way to get blaze powder, turning one blaze rod into 3 or 4 powder.
We can abuse this interaction between the two extra crafting recipes to obtain infinite blaze powder. First convert one blaze rod into three powder, and then two powder into one rod. For each cycle, we get one powder left over.
If we were to put these recipes into our autocrafting system, we could then ask it to magic up 100 blaze powder from a single rod. But what would that actually involve?
As a human, it’s easy to describe: just repeat the two recipes a few hundred times until you’ve got enough. But an autocrafter doesn’t have this sort of luxury; instead it has to apply each step, one at a time. And what starts off as a simple request (100 of this item please) can explode into a solution exponentially longer than the original problem.3
As a bit of a general rule4 in complexity theory, if the solution to a problem is pretty big, then it took even longer to actually find the solution. Indeed, solving the reachability problem doesn’t take exponential time (EXPTIME), or even exponential space (EXPSPACE). Instead, it instead lives beyond the realm of primitive-recursive functions, in a complexity class best described as 5.
Autocrafting with Petri nets, pt 2
Well, here we are, at a disappointing end, finding that autocrafting is a near-impossible and intractable problem. And yet, Applied Energistics and Refined Storage don’t seem to have got the memo - they still appear to work fine!
I mentioned this in the previous rambling, but I think it’s worth stressing again: in practice, none of this really matters. While you can express some really wacky problems with crafting recipes, this sort of weirdness just doesn’t show up in normal play. Aside from storage blocks (iron blocks to iron ingots), I’m not even sure vanilla Minecraft has any loops!
That said, I do think it’s fun to talk about these things. I do still think there’s scope for improvement in the world of autocrafting6, and hopefully this inspires someone. And failing that, I at least hope you’ve learned something!
As mentioned at the top, I’m definitely not an expert in any of this! If you do spot a mistake (or a typo!), please let me know on the issue tracker or get in touch directly.
I conceed that “we’re going to ignore this” isn’t very compelling.
It’s definitely possible to handle more than 9 inputs in a reasonable way: given a transition with 10 inputs, we can convert that into two recipes: one which consumes 9 of the inputs and produces a unique item, and a second recipe which consumes this unique item and the one remaining input item to produce our final output.
An example decomposition of a transition with 10 inputs and one output. The original transition is split into T1 and T2, using a unique item α as an intermediary. However, it’s less clear how to hande Petri nets with multiple outputs. The Forge modding API offers the ability to provide “remainder items” from a crafting recipe. While it’s originally intended for things like turning full buckets into empty ones, you could (ab)use it to implement multiple outputs. Though at that point, we’re no longer really in the vanilla+datapacks world.↩︎
Technically it’s a bit more nuanced than that. The reachability problem considers a specific marking , and so considers all items in the storage system, when we only care if the marking contains a specific item.
We could avoid this problem by adding transitions which can discard spare items, and then defining our target marking as containing just the desired item. It’s an ugly solution, but technically correct.
Another option would be to consider crafting as a liveness problem. This asks whether a specific transition is reachable. However, liveness is also in EXPSPACE, so isn’t any more practical to solve.↩︎
There is a lot of over-simplification going on here, both in the theory of complexity, and in the specific case of Petri-nets and auto-crafting. See the disclaimer at the top of this post!
In such a closed system, it should be perfectly possible for an auto-crafter to optimise for this sort of cycle. However, it’s always possible to build a more complicated system where some optimisation no longer applied. For instance, maybe crafting blaze rods from blaze powder consumes a small amount of durability of a catylst. Now you’ve got to keep track of that, maybe craft a new catalyst (which then is a whole sub-problem your autocrafter needs to solve), etc…↩︎
Again, over-simplification. And at this point making a lot of assumptions about the fact that some complexity classes are strict subsets of others.↩︎
Update from 2023: I had previously missed this, but in 2022 reachability was shown to be Ackermann complete. Thank you to this excellent blog post for pointing that out!↩︎
I do really want to fiddle around with implementing something like this paper. Though I can’t say I’ve really groked all the details.↩︎