[Feat]: 养成计划体力预估

[FlandiaYingman]

背景与动机

目前的养成计划只提供了：

• 材料清单：计算角色从目前练度，养成到预计练度所需要的材料。
• 背包物品：提供背包物品的统计。

（似乎背包物品和材料清单没有任何功能上的关联？例如：我的背包里有某个养成计划中所需的材料，不会改变材料清单上的数字。不确定是不是我使用方法有问题）



如图所示，我已在背包里设置了这些材料，但没有反映在材料清单功能中。

作为一个用户，我希望养成计划功能能够提供一些具体的方案（如下所示）来养成角色。因为这样可降低用户的思考量或计算量，使养成过程更加便捷。

想要实现或优化的功能

“具体的方案”如下：

1. 在材料清单中，显示“所需材料 (已有材料/总所需材料)”，如"10 (19/29)“。这样可使用户更直观地看到还需刷取多少材料。
2. 在材料清单中，添加面向材料获取方式的面板，而不是面向材料本身的面板。例如，我仍需要 93 个 「巧思」的哲学，那么在该面板中，应显示仍需刷取 精通秘境：妙语 Ⅳ 46 次 (920 树脂)。（数字是随手填的）
3. 在材料清单，面向材料获取方式的面板中，标识它们的开放时间。例如：假设今天是周一，那么应显示 （周二/周五/周日）精通秘境：妙语 Ⅳ 46 次 (920 树脂)，并用灰色字体或是 disabled 效果来标识今天无法获得此种材料。

[FlandiaYingman]

有用的链接：BOSS及秘境掉落数据统计

如果作者比较忙的话，我可以抽空写一个养成计划的原型

[FlandiaYingman]

Hi, @Lightczx

利用线性规划求解“通过所需的材料和背包里已有的材料，计算出最优的刷取特定秘境的次数和合成材料的次数”问题的 Demo：https://github.com/FlandiaYingman/Genshin.Planner.Demo

如果你需要某些特定形式的 API，我也很乐意修改这个 Demo，直到它满足需要为止。

我是第一次写 C#，所以代码可能会看起来有点迷糊 :D

[Lightczx]

@FlandiaYingman
需要不引入多余的第三方库：Google.OrTools

[FlandiaYingman]

@Lightczx
从头实现线性规划稍显困难，我会试一下

[FlandiaYingman]

@Lightczx
目前已经实现了无需第三方库的版本。然而，这么做会使运算时间上升到~20s左右。
目前，我的程序中包含了所有的合成配方（包括尘歌壶、食物等），经过测试，我认为是这些多余的配方拖慢了运算速度。
所以，你能提供一份胡桃启动器中，养成计划=>背包物品中所有养成材料的名称的列表吗？我会用它将多余的配方剔除。

换句话说，我需要这个界面中材料的名称。

[Lightczx]

自己实现的线性规划更慢？算法有问题吧？不然时间应该差不多

[FlandiaYingman]

@Lightczx
嗯，线性代数相关的算法需要矩阵运算的基础库支持才能写的更有效些。只用数组的话，实现简单的单纯形算法已经是我能力的极限了。
不过，慢十几秒有点夸张了，我猜想是许多无效约束造成的。我会同时试着在应用层面和算法层面剔除掉这些无用约束。

[Lightczx]

https://learn.microsoft.com/en-us/dotnet/standard/numerics
https://learn.microsoft.com/en-us/dotnet/api/system.numerics

[FlandiaYingman]

@Lightczx
你发的那些仅支持特定大小的matrix（3x2）（4x4)，没办法做大型线性方程组的运算。

[Lightczx]

那就自己实现吧

[FlandiaYingman]

那就自己实现吧

能力有限，无法实现

[Lightczx]

能把具体的运算过程讲解一下么

[FlandiaYingman]

@Lightczx

刚想讲解运算过程，在写的过程中发现了算法设计的问题。

你指出的“算法有问题”是对的😭。我为无上界的约束指定的上界是 double.PositiveInfinity，然而，直接在约束矩阵里去除上界更有效率些。

目前的运算速度：~ 1000 ms，相比于用第三方 native 库的 ~ 400 ms，我觉得时间上已经可以接受了。

纯 C# 实现已经推到 https://github.com/FlandiaYingman/Genshin.Planner.Demo 上了

[Lightczx]

目前没有办法获取秘境入口与秘境的对应关系
合成材料的元数据可以获取

[FlandiaYingman]

@Lightczx

我 project 里的 QuickType.DomainJson 里有一个 domainentrance，对应着各秘境的秘境入口。

数据来源于这个 API：https://genshindb-ia.netlify.app/

https://genshin-db-api.vercel.app/api/domains?
query=names&matchCategories=true&verboseCategories=true&resultLanguage=ChineseSimplified

[Lightczx]

元数据必须从 ExcelBin 中解析，不接受外界的数据，我们必须对数据源具有控制权

[FlandiaYingman]

@Lightczx

抱歉，ExcelBin 是什么？

如果无法获取秘境入口与秘境的对应关系，那么我认为跳过秘境入口名，直接显示秘境名也可以。因为我想大部分玩家都没有看到秘境入口名就能反应该刷哪个秘境的能力，大家都是点开某个材料然后跳转到秘境去的。

[Lightczx]

看了眼他的解析方式
https://github.com/theBowja/GenshinData-scripts/blob/main/extract/extractDomain.js
我觉得还是不能做秘境对应

[FlandiaYingman]

看了眼他的解析方式 https://github.com/theBowja/GenshinData-scripts/blob/main/extract/extractDomain.js 我觉得还是不能做秘境对应

只是没办法做秘境和秘境入口吗？有没有什么曲线救国的方式？

如果找不到方法的话就 close 吧

[Lightczx]

秘境的材料是可以做的，秘境入口不行

[FlandiaYingman]

秘境的材料是可以做的，秘境入口不行

那就先搁置秘境入口，这个不影响整体功能。毕竟只是一个 mapping 的事情，未来如果有方法了随时可以做

[Lightczx]

稍微描述一下算法吧

[FlandiaYingman]

@Lightczx

求解线性规划用的是单纯形法，不赘述了。

关于怎么构造的线性规划

由于有合成功能的存在，简单地将需求材料数乘以秘境掉落期望数的算法是不完善的。因而，我们需要找到一个最优解，使得消耗总树脂最低，即最大程度地利用背包里的材料。

设 x1, x2, ..., xn 为线性规划的变量，我们用各变量代表一个独立的行为（刷秘境或合成）。所以，线性规划求解完毕后，各个变量的最优值即是我们想要的结果（某个秘境刷 n 次，某种材料合成 m 个，etc.）。特别地，有一个 stock 变量恒定为 1，它的作用是代表背包里的材料。

注意，由于个别材料（例如，突破宝石）有不止一个合成方式，我为每个合成方式都赋了一个独特的 ID（就是合成产物名字后面跟一个计数器而已）。不过我的算法还没实现 BOSS 和掉落产物的对应，所以赋 ID 这一步可以省略。

然后，设 c1, c2, ..., cm 为线性规划的约束，我们用各约束代表各材料。每个材料的表达式是对每个会产出该材料的行为乘以该行为产出材料的期望值求和。注意有些合成行为是消耗材料的，所以该行为产出负数个此材料。最后再加上背包的材料，它用 stock 变量（即 1）乘以背包材料的数量来表示。（实际上 stock 变量放到约束里就是一个常数项而已）

如果我们不需要这个材料，那么在这个约束中，我们使这个表达式大于等于 0，这样就不会有负数材料的出现；如果我们需要这个材料，那么在这个约束中，我们使这个表达式大于等于需要材料数。

最后，使最优化函数=各行为需要消耗的树脂的数量的和，我们要使最优化函数最小。然后求解，结果就出来了

例子

约束 c1 代表“高塔孤王的断片”

这个材料有三种获取方式：

• 变量 x1：炼武秘境：水光之城 Ⅲ
• 变量 x2：炼武秘境：水光之城 Ⅳ
• 变量 x3：合成“高塔孤王的断片”

以及一种消耗方式：

• 变量 x4：合成“高塔孤王的碎梦”

那么，构造一个表达式，使它表达我们“高塔孤王的断片”的数量：

“高塔孤王的断片” = 0.22*x1 + 0.64*x2 + 1*x3 - 3*x4 + 背包里已有“高塔孤王的断片”的数量

其中 0.22，0.64 是刷一次对应秘境掉落“高塔孤王的断片”的期望值，1*x3 的意思是合成一次“高塔孤王的断片”可以获得 1 个“高塔孤王的断片”，- 3*x4 的意思是合成一次“高塔孤王的碎梦”会消耗 3 个“高塔孤王的断片”。

由于线性规划中不允许常数项的出现，我们使 stock 变量恒为 1，然后把背包里已有“高塔孤王的断片”的数量变为背包里已有“高塔孤王的断片”的数量*stock。

所以，最后的约束

c1: 0.22*x1 + 0.64*x2 + 1*x3 - 3*x4 + 背包里已有“高塔孤王的断片”的数量*stock >= 需要的“高塔孤王的断片”的数量

一些 Trick

• 设高等级的秘境比低等级的秘境消耗的树脂要稍微少一些（0.01），这样规划程序不会在刷任意一个秘境都满足条件的情况下刷低等级的秘境。
• 设合成也会消耗少量树脂（0.01）这样规划程序不会瞎合成不需要的材料。

这些树脂仅在最优化函数中表达，等我们最后计算需要多少树脂的时候，对 x1, x2, ..., xn 乘以对应行为需消耗的真实树脂求和，重新计算一遍就可以了。

[Lightczx]

低等级的秘境应该无论如何材料掉的都比高等级的少吧

[xTaiwanPingLord]

本人沒用過Hutao，也對C#不熟，單純朋友傳給我這個issue，我覺得挺有意思，想要發表一下我的淺見：

@FlandiaYingman
我不太懂為什麼一定要用線性規劃做，儘管線性規劃的確是求此問題的解。
問題似乎，好像沒有這麼複雜。大多數時候直接用期望值去估計，應該就能得到相對準確的結果了。
真的有必要為了精準的結果而耗費使用者大量時間，去用線性規劃做嗎？

在取樣少的時候，用什麼方法算意義都不大，刷本/合成送材料的隨機性，對於運氣好或不好的人都是"計算不准"，偏多或偏少；取樣多的時候就直接用期望值算，不會差到令使用者無法接受。
一名使用者可能刷到4藍4綠，也可能2紫4藍4綠，這樣差距超過40樹脂，此時用線性規劃做，真的會比直接套期望值精準嗎?
直接告訴使用者，大約需要8-10個濃縮（320~400樹脂）（舉例來說），讓使用者能有心理準備，實際情況會與計算出來的最佳解有誤差，這樣的作法，對於使用者是否有更大的幫助？
我認為與其討論用什麼方法實現，更有幫助的是能在使用者刷完本後，根據得到的新材料，生成新的預測，這樣可以盡可能的減低每次刷本偏多/偏少帶來的誤差。

@Lightczx
不可否認的，非官方提供的數據是不準確的，尤其在低等級的本，因為採樣低，誤差會比平常來得大。但真的有大到，超越隨機性帶來的誤差嗎? 追求精準時也應該要先訂定誤差容許範圍，當誤差在容許範圍內，就應該被接受，而不是因為有一點影響不大的誤差，放棄這個實用的功能。
我的看法是，因為刷本隨機性帶來的數值偏差遠大於玩家自行統計的期望值的誤差，所以在有標註數據來源以及明確告知使用者會有誤差的情況下，使用玩家自行統計的期望值是可被接受的。

最後:
我與班上同學日常在計算都是，假如說我需要20藍20紫，背包內有5藍3紫->說明我要15藍17紫(約等於66藍，計算送的10%就是60藍左右)
最高等級的副本平均掉落（我個人體感上，換算成藍色等級的）約6.5藍，就說明我大約需要刷9~10次這個本，約需要400樹脂，也就是我前一天存5濃縮樹脂，當天早上起床跟晚上睡覺前刷一下就可以刷完我需要的材料。
簡單來說過程是：
獲取所需資源列表->換算成好記算的單位（藍色等級天賦書）->套用期望值預估（需求量除以期望值）->規劃樹脂使用
簡單的過程卻非常實用

補充: 我的意思不是該功能並不實用，而是我認為用一個更簡單的方法實現，達成「幫助使用者預估需要多少樹脂」的目標就是好方法。

[FlandiaYingman]

@xTaiwanPingLord

我在一开始提出该方法时确实没有经过太多的实践，
经过这些天的实践，我赞同你对该方法过于复杂的看法，因为求出最优解的收益不大，不值得为此设计一个复杂的方法。

[GashByte]

误差是不可避免的 但是我们还是需要一些domian的Datas 我觉得 @FlandiaYingman 提供的算法example进过改良之后还是可以达到预期内的时间 我还需要一点时间来熟悉示例代码 我也需要寻找更多的能够维持正常更新的domain datas

[FlandiaYingman]

@Lightczx
https://github.com/UIGF-org/GenshinData 已经 404 了

[Lightczx]

@Lightczx https://github.com/UIGF-org/GenshinData 已经 404 了

Internal Only

[AZhrZho]

以当前胡桃的用户量，可以考虑通过胡桃收集副本挑战掉落材料，样本量充足且数据源可控。
具体实现，可以在胡桃中内置截图识别+上传，结合已有用户体系，可收集到的数据有：

• 挑战的副本及等级
• 掉落物及数量
• 挑战副本的时间（可进行时间相关性统计）
• 数据来源（方便洗去恶意数据）

同时可以结合胡桃云激励时长，鼓励用户上传副本数据。收集到充足样本后，使用简单的期望估计即可解决问题。期望值可以根据背包中物品数量进行迭代而不断修正

当然也可以选择更精确的统计模型进行计算，只要样本充足，都可以实现（实际上，基于大量样本的简单期望估计一定比线性规划更准确，理由是在精确概率不可知的情况下，参数越少受误差影响越小）

此外，可以视样本的收集率，选择一定长度的滑动时间窗口进行概率估计。此举可保证即使官方暗改了概率，应用也可以自适应概率的变化。更进一步，还可以对时间进行水平划分，通过大量样本计算是否存在所谓的“玄学时间”

[Lightczx]

以当前胡桃的用户量，可以考虑通过胡桃收集副本挑战掉落材料，样本量充足且数据源可控。 具体实现，可以在胡桃中内置截图识别+上传，结合已有用户体系，可收集到的数据有：

• 挑战的副本及等级
• 掉落物及数量
• 挑战副本的时间（可进行时间相关性统计）
• 数据来源（方便洗去恶意数据）

同时可以结合胡桃云激励时长，鼓励用户上传副本数据。收集到充足样本后，使用简单的期望估计即可解决问题。期望值可以根据背包中物品数量进行迭代而不断修正

当然也可以选择更精确的统计模型进行计算，只要样本充足，都可以实现（实际上，基于大量样本的简单期望估计一定比线性规划更准确，理由是在精确概率不可知的情况下，参数越少受误差影响越小）

此外，可以视样本的收集率，选择一定长度的滑动时间窗口进行概率估计。此举可保证即使官方暗改了概率，应用也可以自适应概率的变化。更进一步，还可以对时间进行水平划分，通过大量样本计算是否存在所谓的“玄学时间”

掉落概率其实是固定的，现在是元数据没准备好

[Lightczx]

Tracked by #1394

[github-actions]

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related topic.