如何设计一款FF14生产求解器？

这篇文章是关于网游《最终幻想XIV》中『能工巧匠』玩法的超级碎碎念，谨作为本人对游戏机制理解的分享，如果觉得不错请在评论区夸我，如果哪里说的有问题请私信我讨论（？）

目前国服版本更新完大半个月了，不知道大伙有没有搓新出的、会发光的『莫雯卓越工具』？反正本人是前两天才突然想起来更新了这么个东西，手忙脚乱的跑去水晶都体验了一番……结果接错了任务，被一只羊骗去伊尔美格开了个安登老主顾。

看到这里可能有些误打误撞跑进这篇文章的朋友们还不知道我在说什么玩法，我简单介绍一下，制作就是把一个或多个物品，通过一些步骤，变成另一个物品的玩法。

(资料图)

能工巧匠能够制作武器、工具、防具、饰品、食品、药品以及制作时用到的素材。
——灰机Wiki

当然并不是任意物品都能被制作，能工巧匠只能按照一些固定的配方进行生产。生产的素材我们叫做『素材』，而制作出来的物品叫做『制作出来的物品』（啥啊）。

出于吸引可能存在的讨论算法而来大佬的目的，我接下来会简单的介绍一下各个技能的效果。

点击“开始制作作业”按钮之后，玩家的游戏角色蹲下进入制作状态。并且游戏弹出一个窗口面板显示当前状态。玩家的生产技能此时处于可用状态，使用不同的技能有不同的效果。

与战斗玩法不同，生产属于休闲类型，不需要短时间行云流水地噼里啪啦把技能叽里呱啦地全按出来、Buff也不会倒计时结束后消失。留给玩家充足的思考时间的同时技能的顺序却被设计得特别重要。

要成功制作一个配方，我们需要把『进展』条推满，这样就会获得一个普通品质的物品，称作NQ。如果我们额外把『品质』条也推满，则会100%得到优质物品，称作HQ。一般情况下，我们制作的装备、食物、强化药等物品需要HQ提供更高的属性，而时装、鸟甲、乐谱等配方则不需要HQ。

在当前版本，所有生产职业的技能名称和效果都完全一致，只有图标随职业略微变化。我们可以把技能大致分为两类：『作业系』和『加工系』

『作业系』的技能会消耗耐久度，并提高作业进展，而『加工系』的技能会消耗耐久度，并提高品质。

基础的『制作』和『加工』分别消耗10点耐久，随着等级的提升，玩家会习得一次消耗20点耐久的『坯（pī）料』技能：『坯料制作』以300%的效率推动进展，而『坯料加工』以200%的效率推动品质。

乍一眼看上去好像很赚！既节约了步骤，又能提供更高的效率？请看图标左下角的白色小数字，它代表了使用该技能需要消耗的『制作力』，简称CP。

作为核心机制中第二种资源，『制作力』的引入将生产从“单资源，双目标”的规划问题变成了“双资源，双目标”的规划问题，而这为玩家带来了不小的挑战性。

关于机制设计的分析我们后面再讲，随着等级的提升，玩家会习得消耗耐久减半的『俭约』系技能，即『俭约制作』和『俭约加工』：

写到这里，我意识到到逐一介绍技能实在是非常繁琐且无聊，上面这张图我憋了两三天才做出来。所以我决定最后介绍两个技能『精修』和『掌握』，然后插播一些其他的东西。

精修和掌握都是用于回复耐久度的技能，它们无一例外都十分消耗制作力：

两个技能的本质都是将制作力转换为耐久度。经过简单的计算可知，『精修』恢复10耐久平均需要制作力，而『掌握』只需要24制作力，单纯比较数值的话掌握更合算。但是精修有总制作力更低、立即生效更灵活、无需做职业任务即可习得的优势。实际使用的时候还是需要灵活选择。而这种灵活则会导致玩家（和求解器）的决策难度更高。

说到这里不知道大家有没有注意到一个问题：

这玩意哪里好玩了？

要站在游戏机制设计者的角度回答这个问题，让我们看看SE都往里面塞了什么东西：

物品分为普通（NQ）和优质（HQ）两种品质，HQ的物品属性更高。

制作有『进展条』，使用技能把进展推满就能制作成功。

制作有『耐久条』，耐久用完进展没有推满就会制作失败。

制作有『品质条』，提高品质可以提升获得HQ物品的概率。

最后是『制作状态』，随机出现并且会影响下一步技能的效果（球色）。

『进展』推满 = 玩家获得制作成功的奖励，『耐久』引入了该玩法的挑战性机制，『品质』的引入增加了游戏的复杂度，而『制作状态』为游戏引入了随机性。

清晰的目标、及时的奖励、一定的挑战性、充足的复杂度以及随机性，构成了生产玩法的核心要素。接下来我们来尝试解析一下背后设计的逻辑。

整个玩法的核心是进展条和品质条：进展决定了制作的成功或者失败，而品质条决定了物品做出来是NQ还是HQ。

这时候设计者引入了耐久，在进展和品质之间合理分配耐久变成了一个需要玩家做出决策的问题。

一种理论认为优雅的游戏设计，机制彼此之间存在大量的连接。而不优雅的游戏则连接比较稀疏。也就是低内聚、高耦合（？

具体来说，精修和掌握建立了制作力转换为耐久的连接、秘诀和集中加工集中制作建立了球色和进展跟品质的连接、高难配方彩球的引入将制作状态的随机性和作业、耐久、制作力之间的连接。

所以整个生产机制给人的感受是一个完善的体系，而不是随意拼凑起来的玩法。

插播的内容就写到这里，现在开始回归标题，怎么做一个生产求解器？之所以要谈论这个话题，是因为我已经开发了一款效果超越以前所有的新的求解器，并且完成度足够日常使用。

在我自己看来仅仅当做生产模拟器使用也是非常精良的作品了。

非常明显的一点是，我们有多个不同的视角来看待这个问题本身。对我来说，从数学和工程的角度来看这是一个『最优化问题』。使用什么生产技能是参数，玩法机制是约束，进展条和品质条是指标。

在模型是已知的前提下，解决最优化问题最直接的方法是『穷举法』。尝试所有可能参数，再模拟出每种参数的结果，然后选择能最大化目标的即可。

插播一下我们可以这样判断两个宏哪个更优：

分别模拟两个宏的最终结果，得到两个状态：s1和s2。

比较s1和s2的进展，进展更高的宏更优（因为进展更低的那个一定没搓满）。

进展相同，比较s1和s2的品质，品质更高的宏更优。

品质相同，比较s1和s2的工序，工序更短的宏更优。

工序也相同，两个宏是等效的。

附代码：

朴素的穷举法有一个非常严重的问题，那就是参数空间太大，导致求解时间太长而使整个方法变得不可行。我们可以做个简单的计算，从生产职业的31个技能中排除掉一些不会在宏里使用的技能，再排除掉仅在作业开始时使用的技能，剩下22个生产技能，再假设技能序列总长度为15（这也是单宏能写下的最多的步骤数）：

需要注意的是，简单的指数运算并不能反映真实情况。工程上通过许多剪枝操作可以排除大部分明显不可行的技能序列，从而将搜索空间降低数个数量级。但即便如此，搜索这个级别的参数空间可能也非常的离谱。

好消息是，『搜索空间会随步骤长度增加指数级扩大』反过来说就是『搜索空间会随步骤长度减小指数级缩小』。如果把搜索深度限制到6步，即使考虑全部31个技能，搜索空间也会瞬间缩小

在我的设备上，使用穷举法搜索6步之内的最优解仅需3秒，而搜索7步之内的最优解需要1分14秒（测试仅做了一次），据此粗略估计，求解15步内的最优解仅需大约一百万年。

当然了，三秒能求得6步内的最优解也是一个不错的成果了，相关的功能我也有放到我的生产模拟器里给大家使用。

朴素的穷举法如此的局限，我为什么还大费周章为此做了一整套生产模拟器的程序呢？这事还得从两年前说起。

那时候我还没开始玩FF14的能工巧匠，但却想自己搓最新的战职制作装。托亲友帮忙买了理符升级包和一套当时最好的生产装备，但是却不知道生产要怎么用技能。我看到几十个技能描述就头大，这怎么学？这时候一个天才般的想法进入了我的脑子：只要有这么一个程序，只要我把所有技能的描述输入进去，然后让它计算按什么顺序使用这些技能不就可以了吗？

经过了长达几个星期的思考，以及对生产机制的审视，在考虑各种可能的方案、特别是意识到生产问题与另一个经典的数学问题之间有多么接近之后，我认为一种叫做『动态规划（Dynamic Programming）』的算法最有希望。

朋友，那就是数学家们已经研究了一个多世纪的背包问题。

假设你有一个能装W千克重的背包，以及N个物品，每件物品都有它的『质量』和『价值』。你可以把物品都装到背包里，但是总重量不能超过背包的极限W，请问选择那些物品装入可以让总价值最大？

……好吧我特别不想在这里讲一遍背包问题和动态规划，能看到这里的读者早就知道这些都是什么玩意了，如果你不懂……不用百度，看下面这个《背包问题九讲 V2》：

/tianyicui/pack

敲重点：『二维费用的背包问题』，生产问题可不就是一种二维费用的背包问题吗？每个技能都是一个“物品”，初始的制作力和耐久度就是“二维的重量”，进展和品质就是“价值”。

在意识到这个关系之后，剩下的展开就水到渠成了，我们只需要套用背包问题的算法……才怪。

最大的问题是我们在求解背包问题时，物品和物品之间没有顺序，不会互相影响。而生产的技能和技能之间不仅会互相影响，而且顺序特别重要。判断一个问题是否能用DP求解，最重要的是能否找到一个最优子结构，而这也是设计DP算法最难的部分，我也一度认为生产问题可能找不到最优子结构。

在几天的冥思苦想之后，还是给我找到了。方案非常简单：不要按技能递推，而是按资源递推。而这也牺牲了『那个空间复杂度优化』。

这里的cp是制作力，而du是耐久度。为了满足计算的依赖顺序，我们必须认为制作力是单调递减的，而耐久度不是。这样计算制作力更低的情况时就无需依赖制作力更高的情况的数据。所以我们先计算完制作力为0的全部情况、再计算制作力为1的全部情况……直到玩家的最大制作力为止。

举例来说，假设当前剩余20耐久和100制作力用于加工。我们依次尝试每个可行的技能：

先试试『加工』，消耗18点制作力和10点耐久，把『加工能推动的品质』加上剩余『10耐久和82点制作力能推动的品质』就能得到现在使用加工能获得的品质。