我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)

我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)，哪吒游戏网给大家带来详细的我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)介绍，大家可以阅读一下，希望这篇我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)可以给你带来参考价值。

本文作者zzzz（@ustc-zzzz），使用CC-BY-SA 4.0协议授权。

合成表（又称配方）自然是 Minecraft 玩家非常熟悉且频繁使用的东西了，玩家会通过一个持有 3x3（有时为 2x2）物品槽的界面中添加特定的物品，从而在添加的物品满足一定条件时得到特定的输出。Minecraft 中的合成表分为有序合成和无序合成两种。

原图来自 Minecraft Wiki，使用 CC-BY-NC-SA 3.0 协议授权。

上图中上方是南瓜派的合成表，其中三个物品可以任意放置，而上图中下方是曲奇的合成表我的世界合成表，只能通过把三个物品摆成一排合成得到，且三个物品的次序不能发生变化。

有序合成的实现相对简单不少，本篇文章主要关注的是无序合成的实现。

基于一对一的合成

我们可以把南瓜派的合成表简记为“[南瓜, 糖, 鸡蛋]”。这三种物品本身是没有次序的，但是物品输入一定存在一个遍历的次序。

这种情况下，匹配无序合成非常简单——遍历输入，然后逐个匹配配方中的元素即可。考虑“[鸡蛋, 南瓜, 糖]”这一输入次序：

这本质上和判定两个元素为 n 的集合是否等价是一样的。我们只需要通过稍高于 O(n) 的时间复杂度和 O(n) 的空间复杂度便可完成匹配。

Minecraft 1.12 及更早的版本使用的便是这一方法。这一方法在所有原版的无序合成中并未出现问题，而 1.12 也不允许玩家自定义合成表。但是基于 Forge 的 Mod 存在大量自定义合成表，因此有人率先发现了问题。

基于多对一的合成

然而现实并非那样简单。游戏中存在着很多按种类划分的物品，比如说蘑菇既可以是红蘑菇，也可以是棕蘑菇，木板有包括但不限于橡木、云杉等品种。Minecraft 允许在配方的某个成份中声明某种特定类型的物品，而满足条件的任意物品均可参与合成。

如果我们再使用之前的方式匹配，很快就会遇到麻烦。考虑“[木板, 橡木木板]”这样一个合成表，和“[橡木木板, 云杉木板]”这一输入次序：

这便是现实。只需要把“[橡木木板, 云杉木板]”这一输入次序颠倒过来便可成功完成匹配的合成表，在这种情况下竟然不能匹配了。事实上，Forge 的出现更是大大增加了这件事的复杂度。Forge 引入的矿物辞典机制使得游戏中几十种物品属于同一类的情况时常发生，而这些物品却会大量出现在合成表里。

我们现在手头有什么？

我们据此可以得到输入物品和配方组成成分之前的关系图。对相关算法了解的同学应该能够立刻意识到——这是二分图的最大匹配问题。

匹配与匈牙利算法

匈牙利算法是一种相对高效的解决最大匹配问题的算法。该算法对于两个元素为 n 的集合及 m 个边的情况下，能够通过 O(mn) 的时间复杂度解决问题。

上面的 GIF 大概还原了匈牙利算法的进行过程。

匈牙利算法的核心是增广路径。科学家已经证明：当且仅当没有增广路径的时候，对应的是二分图的最大匹配。

增广路径的定义是二分图中第一个和最后一个边均为未匹配边，而中间路径中未匹配边和匹配边交替出现的路径。显然，增广路径中第一个和最后一个顶点均为未匹配点，而其中所有顶点均为匹配点。

匈牙利算法本质上是通过不断地寻找增广路径扩大匹配的数量。我们将增广路径中未匹配边和匹配边交换，便能立刻使已有的匹配数加一。

我们考虑“[红砂岩, 砂岩, 錾制砂岩, 切制砂岩]”这样一个合成表我的世界合成表，和“[錾制红砂岩, 切制红砂岩, 切制砂岩, 砂岩]”这一输入次序。显然，只需要从二分图的一个部分遍历增广路径便可完成匹配，因此我们这里从第一个物品开始。

Minecraft 在新版本内部便是使用的匈牙利算法。自然，对于二分图的最大匹配而言，有更高效的 Hopcroft-Karp 算法，不过 Minecraft 本体并未采用。笔者个人认为，九宫格的规模很小，使用 Hopcroft-Karp 算法可能也没有太大的必要。

虽然 Minecraft 从 1.13 开始允许玩家使用原版自定义合成表了，不过错误的实现只持续到了 Minecraft 1.12，因此对于原版玩家而言这是透明的。就 Forge 而言，他们在某个提交修复了这个问题。

鸣谢

总结：以上内容就是针对我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)详细阐释，如果您觉得有更好的建议可以提供给哪吒游戏网小编，我的世界合成表(游戏中的算法——从 Minecraft 的无序合成说开去)部分内容转载自互联网，有帮助可以收藏一下。