如何設計一款FF14生產求解器？
這篇文章是關于網游《最終幻想XIV》中『能工巧匠』玩法的超級碎碎念，謹作為本人對游戲機制理解的分享，如果覺得不錯請在評論區(qū)夸我，如果哪里說的有問題請私信我討論（？）
目前國服6.35版本更新完大半個月了，不知道大伙有沒有搓新出的、會發(fā)光的『莫雯卓越工具』？反正本人是前兩天才突然想起來更新了這么個東西，手忙腳亂的跑去水晶都體驗了一番……結果接錯了任務，被一只羊騙去伊爾美格開了個安登老主顧。
看到這里可能有些誤打誤撞跑進這篇文章的朋友們還不知道我在說什么玩法，我簡單介紹一下，制作就是把一個或多個物品，通過一些步驟，變成另一個物品的玩法。
能工巧匠能夠制作武器、工具、防具、飾品、食品、藥品以及制作時用到的素材。
——灰機Wiki
當然并不是任意物品都能被制作，能工巧匠只能按照一些固定的配方進行生產。生產的素材我們叫做『素材』，而制作出來的物品叫做『制作出來的物品』（啥?。?。
出于吸引可能存在的討論算法而來大佬的目的，我接下來會簡單的介紹一下各個技能的效果。
點擊“開始制作作業(yè)”按鈕之后，玩家的游戲角色蹲下進入制作狀態(tài)。并且游戲彈出一個窗口面板顯示當前狀態(tài)。玩家的生產技能此時處于可用狀態(tài)，使用不同的技能有不同的效果。
與戰(zhàn)斗玩法不同，生產屬于休閑類型，不需要短時間行云流水地噼里啪啦把技能嘰里呱啦地全按出來、Buff也不會倒計時結束后消失。留給玩家充足的思考時間的同時技能的順序卻被設計得特別重要。
要成功制作一個配方，我們需要把『進展』條推滿，這樣就會獲得一個普通品質的物品，稱作NQ。如果我們額外把『品質』條也推滿，則會100%得到優(yōu)質物品，稱作HQ。一般情況下，我們制作的裝備、食物、強化藥等物品需要HQ提供更高的屬性，而時裝、鳥甲、樂譜等配方則不需要HQ。
在當前版本，所有生產職業(yè)的技能名稱和效果都完全一致，只有圖標隨職業(yè)略微變化。我們可以把技能大致分為兩類：『作業(yè)系』和『加工系』
『作業(yè)系』的技能會消耗耐久度，并提高作業(yè)進展，而『加工系』的技能會消耗耐久度，并提高品質。
基礎的『制作』和『加工』分別消耗10點耐久，隨著等級的提升，玩家會習得一次消耗20點耐久的『坯（pī）料』技能：『坯料制作』以300%的效率推動進展，而『坯料加工』以200%的效率推動品質。
乍一眼看上去好像很賺！既節(jié)約了步驟，又能提供更高的效率？請看圖標左下角的白色小數字，它代表了使用該技能需要消耗的『制作力』，簡稱CP。
作為核心機制中第二種資源，『制作力』的引入將生產從“單資源，雙目標”的規(guī)劃問題變成了“雙資源，雙目標”的規(guī)劃問題，而這為玩家?guī)砹瞬恍〉奶魬?zhàn)性。
關于機制設計的分析我們后面再講，隨著等級的提升，玩家會習得消耗耐久減半的『儉約』系技能，即『儉約制作』和『儉約加工』：
寫到這里，我意識到到逐一介紹技能實在是非常繁瑣且無聊，上面這張圖我憋了兩三天才做出來。所以我決定最后介紹兩個技能『精修』和『掌握』，然后插播一些其他的東西。
精修和掌握都是用于回復耐久度的技能，它們無一例外都十分消耗制作力：
兩個技能的本質都是將制作力轉換為耐久度。經過簡單的計算可知，『精修』恢復10耐久平均需要29.33制作力，而『掌握』只需要24制作力，單純比較數值的話掌握更合算。但是精修有總制作力更低、立即生效更靈活、無需做職業(yè)任務即可習得的優(yōu)勢。實際使用的時候還是需要靈活選擇。而這種靈活則會導致玩家（和求解器）的決策難度更高。
說到這里不知道大家有沒有注意到一個問題：
這玩意哪里好玩了？
要站在游戲機制設計者的角度回答這個問題，讓我們看看SE都往里面塞了什么東西：
物品分為普通（NQ）和優(yōu)質（HQ）兩種品質，HQ的物品屬性更高。
制作有『進展條』，使用技能把進展推滿就能制作成功。
制作有『耐久條』，耐久用完進展沒有推滿就會制作失敗。
制作有『品質條』，提高品質可以提升獲得HQ物品的概率。
最后是『制作狀態(tài)』，隨機出現并且會影響下一步技能的效果（球色）。
『進展』推滿 = 玩家獲得制作成功的獎勵，『耐久』引入了該玩法的挑戰(zhàn)性機制，『品質』的引入增加了游戲的復雜度，而『制作狀態(tài)』為游戲引入了隨機性。
清晰的目標、及時的獎勵、一定的挑戰(zhàn)性、充足的復雜度以及隨機性，構成了生產玩法的核心要素。接下來我們來嘗試解析一下背后設計的邏輯。
整個玩法的核心是進展條和品質條：進展決定了制作的成功或者失敗，而品質條決定了物品做出來是NQ還是HQ。
這時候設計者引入了耐久，在進展和品質之間合理分配耐久變成了一個需要玩家做出決策的問題。
一種理論認為優(yōu)雅的游戲設計，機制彼此之間存在大量的連接。而不優(yōu)雅的游戲則連接比較稀疏。也就是低內聚、高耦合（？
具體來說，精修和掌握建立了制作力轉換為耐久的連接、秘訣和集中加工集中制作建立了球色和進展跟品質的連接、高難配方彩球的引入將制作狀態(tài)的隨機性和作業(yè)、耐久、制作力之間的連接。
所以整個生產機制給人的感受是一個完善的體系，而不是隨意拼湊起來的玩法。
插播的內容就寫到這里，現在開始回歸標題，怎么做一個生產求解器？之所以要談論這個話題，是因為我已經開發(fā)了一款效果超越以前所有的新的求解器，并且完成度足夠日常使用。
在我自己看來僅僅當做生產模擬器使用也是非常精良的作品了。
非常明顯的一點是，我們有多個不同的視角來看待這個問題本身。對我來說，從數學和工程的角度來看這是一個『最優(yōu)化問題』。使用什么生產技能是參數，玩法機制是約束，進展條和品質條是指標。
在模型是已知的前提下，解決最優(yōu)化問題最直接的方法是『窮舉法』。嘗試所有可能參數，再模擬出每種參數的結果，然后選擇能最大化目標的即可。
插播一下我們可以這樣判斷兩個宏哪個更優(yōu)：
分別模擬兩個宏的最終結果，得到兩個狀態(tài)：s1和s2。
比較s1和s2的進展，進展更高的宏更優(yōu)（因為進展更低的那個一定沒搓滿）。
進展相同，比較s1和s2的品質，品質更高的宏更優(yōu)。
品質相同，比較s1和s2的工序，工序更短的宏更優(yōu)。
工序也相同，兩個宏是等效的。
附代碼：
樸素的窮舉法有一個非常嚴重的問題，那就是參數空間太大，導致求解時間太長而使整個方法變得不可行。我們可以做個簡單的計算，從生產職業(yè)的31個技能中排除掉一些不會在宏里使用的技能，再排除掉僅在作業(yè)開始時使用的技能，剩下22個生產技能，再假設技能序列總長度為15（這也是單宏能寫下的最多的步驟數）：
需要注意的是，簡單的指數運算并不能反映真實情況。工程上通過許多剪枝操作可以排除大部分明顯不可行的技能序列，從而將搜索空間降低數個數量級。但即便如此，搜索這個級別的參數空間可能也非常的離譜。
好消息是，『搜索空間會隨步驟長度增加指數級擴大』反過來說就是『搜索空間會隨步驟長度減小指數級縮小』。如果把搜索深度限制到6步，即使考慮全部31個技能，搜索空間也會瞬間縮小
在我的設備上，使用窮舉法搜索6步之內的最優(yōu)解僅需3秒，而搜索7步之內的最優(yōu)解需要1分14秒（測試僅做了一次），據此粗略估計，求解15步內的最優(yōu)解僅需大約一百萬年。
當然了，三秒能求得6步內的最優(yōu)解也是一個不錯的成果了，相關的功能我也有放到我的生產模擬器里給大家使用。
樸素的窮舉法如此的局限，我為什么還大費周章為此做了一整套生產模擬器的程序呢？這事還得從兩年前說起。
那時候我還沒開始玩FF14的能工巧匠，但卻想自己搓最新的戰(zhàn)職制作裝。托親友幫忙買了理符升級包和一套當時最好的生產裝備，但是卻不知道生產要怎么用技能。我看到幾十個技能描述就頭大，這怎么學？這時候一個天才般的想法進入了我的腦子：只要有這么一個程序，只要我把所有技能的描述輸入進去，然后讓它計算按什么順序使用這些技能不就可以了嗎？
經過了長達幾個星期的思考，以及對生產機制的審視，在考慮各種可能的方案、特別是意識到生產問題與另一個經典的數學問題之間有多么接近之后，我認為一種叫做『動態(tài)規(guī)劃（Dynamic Programming）』的算法最有希望。
朋友，那就是數學家們已經研究了一個多世紀的背包問題。
假設你有一個能裝W千克重的背包，以及N個物品，每件物品都有它的『質量』和『價值』。你可以把物品都裝到背包里，但是總重量不能超過背包的極限W，請問選擇那些物品裝入可以讓總價值最大？
……好吧我特別不想在這里講一遍背包問題和動態(tài)規(guī)劃，能看到這里的讀者早就知道這些都是什么玩意了，如果你不懂……不用百度，看下面這個《背包問題九講 V2》：
https://github.com/tianyicui/pack
敲重點：『二維費用的背包問題』，生產問題可不就是一種二維費用的背包問題嗎？每個技能都是一個“物品”，初始的制作力和耐久度就是“二維的重量”，進展和品質就是“價值”。
在意識到這個關系之后，剩下的展開就水到渠成了，我們只需要套用背包問題的算法……才怪。
最大的問題是我們在求解背包問題時，物品和物品之間沒有順序，不會互相影響。而生產的技能和技能之間不僅會互相影響，而且順序特別重要。判斷一個問題是否能用DP求解，最重要的是能否找到一個最優(yōu)子結構，而這也是設計DP算法最難的部分，我也一度認為生產問題可能找不到最優(yōu)子結構。
在幾天的冥思苦想之后，還是給我找到了。方案非常簡單：不要按技能遞推，而是按資源遞推。而這也犧牲了『那個空間復雜度優(yōu)化』。
這里的cp是制作力，而du是耐久度。為了滿足計算的依賴順序，我們必須認為制作力是單調遞減的，而耐久度不是。這樣計算制作力更低的情況時就無需依賴制作力更高的情況的數據。所以我們先計算完制作力為0的全部情況、再計算制作力為1的全部情況……直到玩家的最大制作力為止。
舉例來說，假設當前剩余20耐久和100制作力用于加工。我們依次嘗試每個可行的技能：
先試試『加工』，消耗18點制作力和10點耐久，把『加工能推動的品質』加上剩余『10耐久和82點制作力能推動的品質』就能得到現在使用加工能獲得的品質。
再依次嘗試其他技能，如『精修』，可以看作消耗88點制作力和-30耐久……
以及其他的技能
使用這個方法，我們的搜索空間可以降低至1,260,000（假設制作力為600，耐久度為70，技能數為30）。
是不是感覺問題已經迎刃而解了？然而并沒有……
仔細想想就會發(fā)現，制作力×耐久度并沒有完整覆蓋整個狀態(tài)空間，只靠它們并不能區(qū)分不同掌握層數的狀態(tài)。但是這也好辦，把掌握Buff看作一種初始為0的資源即可。同樣要被看作一種資源的還有：
內靜層數
改革次數
闊步次數
儉約次數
加工連擊狀態(tài)
觀察注視連擊狀態(tài)
所以事實上，在動態(tài)規(guī)劃視角下生產問題不是一個簡單的二維費用背包問題，而是一個至少九維的最優(yōu)化問題。
九維狀態(tài)的運算需要保存九維信息的數據結構，具體來說我們需要一個九維的『數組』，在一般的編程中常用的是一維的數組，二維數組都用的極少，三維以上的數組則幾乎見不到。在我掌握的編程語言里只有C#對多維數組有專門的支持，而這個項目中我使用的十分先進的Rust語言則更是……
Rust編譯器對多維數組的支持存在Bug
倒不是說編譯出來的程序有什么問題，而是一旦代碼中存在多維數組，編譯器會花費多得多的時間進行優(yōu)化，詳情可以查看一個我提了兩年仍沒有進展的issue:
https://github.com/rust-lang/rust/issues/88580
作為替代方案，ndarray根本不支持九維的數組，我最后找到了這個crate：
https://github.com/TudbuT/micro_ndarray
雖然這個micro_ndarray使用者不多，但是卻小巧精悍，使用了一個叫『常量泛型』的語言功能，提供了任意維度多維數組的支持，性能不俗。我剛開始用那會還有一些小問題，但是提了幾個Issues和Pull?Request之后作者響應迅速，很快就把問題全解決了，感天動地。
關于動規(guī)求解器的部分原理還沒有闡釋清楚，例如如何做到先搓品質再推滿進展，如何避免將當前進展乘進狀態(tài)空間等等……這些都只能等以后有時間的時候再寫。
我原本準備一篇文章就將生產求解器的全部原理解釋清楚，并且吸引有能力的大佬對現有的問題提供改進意見，但是現在看來難度有點頗高?？傊疀]人看也沒關系，我就算為了自己開心也得寫出來。
我開始開發(fā)求解器的時候還是學生，兩年過去現在都已經工作了。當我寫下這行文字的時候已經是星期天的晚上，周一到周五白天要上班，晚上還要打絕亞。這篇文章無論行文有多么雜亂無章，都沒有時間去改了，所以就成了現在這個樣子。
最后放上求解器的下載地址：https://gitee.com/Tnze/ffxiv-best-craft
祝大家游戲快樂?????
