游戏设计中的算法题——计算宝物升级所需的资源数

当今社会,智能手机的飞速发展。使得可以做到人手一部智能手机。而各种应用层出不穷。

手游(手机游戏)的出现,满足了人们对打发碎片时间的需求。

 

而在游戏中,宝物升级是最常见的剧情元素之一。而优秀的游戏设计师,在设计宝物升级系统时,要难易适中,要能把用户黏合在自己的游戏中,既不能太难,也不能太简单。那么如何设计宝物升级中的各项参数就是重中之重。

 

本文重点介绍,给定宝物的设计系统的各项参数,计算宝物升级所需的资源数。

 

问题:

某宝物初始是0级,现在要升级

从0级升到1级,所需的资源数为1,成功概率为90%,成功升1级,失败还是0级;

从1级升到2级,所需的资源数为2,成功概率为80%,成功升1级,失败降1级,降为0级;

从2级升到3级,所需的资源数为3,成功概率为70%,成功升1级,失败降1级,降为1级;

从3级升到4级,所需的资源数为4,成功概率为60%,成功升1级,失败降1级,降为2级;

从4级升到5级,所需的资源数为5,成功概率为50%,成功升1级,失败降1级,降为3级;

问:某宝物从0级升级到5级,所需要的资源数平均是多少?

 

定义一个函数F(N,M),M≥N。表示该宝物从N级升级到M级所需的平均资源数。本题中就是计算F(0,5)

很明显

F(N,N)=0;即F(0,0)=0,F(1,1)=0

F(N,M)=F(N,K)+F(K,M),N≤K≤M,F(0,4)=F(0,2)+F(2,4),即F(2,4)=F(0,4)-F(0,2)

 

用简便表示函数F(N),即F(N)=F(0,N),那么本题就是计算F(5)

 

定义PN,为从N-1级升到N级的成功的概率

本题中,P1=0.9,P2=0.8,P3=0.7,P4=0.6,P5=0.5

定义LN,为从N-1级升到N级所需的资源数

本题中,N1=1,N2=2,N3=3,N4=4,N5=5

 

言归正传,下面分析如何计算F(N)

先分析F(1)

从0级升到1级,所需的资源数为L1。其中(1-P1)的会失败,还是停留在0级,这些还是需要从0级升到1级。那么,就有个分析公式

F(1)=L1+(1-P1)×F(1)

F(1)=L1÷P1=1÷0.9=1.111

 

再分析F(2)

从1级升到2级,所需的资源数为L2。其中(1-P2)的会失败,降级到0级,这些还是需要从0级升到2级。那么,就有个分析公式

F(2)=F(1)+L2+(1-P2)×F(2)

F(2)=(F(1)+L2)÷P2=(1.111+2)÷0.8=3.889

 

再分析F(3)

从2级升到3级,所需的资源数为L3。其中(1-P3)的会失败,降级到1级,这些还是需要从1级升到3级。那么,就有个分析公式

F(3)=F(2)+L3+(1-P3)×F(1,3)

F(3)=F(2)+L3+(1-P3)×(F(3)-F(1))

F(3)=(F(2)+L3-(1-P3)×F(1))÷P3

F(3)=(3.889+3-(1-0.7)×1.111)÷0.7=9.365

 

再分析F(4)

从3级升到4级,所需的资源数为L4。其中(1-P4)的会失败,降级到2级,这些还是需要从2级升到4级。那么,就有个分析公式

F(4)=F(3)+L4+(1-P4)×F(2,4)

F(4)=F(3)+L4+(1-P4)×(F(4)-F(2))

F(4)=(F(3)+L4-(1-P4)×F(2))÷P4

F(4)=(9.365+4-(1-0.6)×3.889)÷0.6=19.682

 

再分析F(5)

从4级升到5级,所需的资源数为L5。其中(1-P5)的会失败,降级到3级,这些还是需要从3级升到5级。那么,就有个分析公式

F(5)=F(4)+L5+(1-P5)×F(3,5)

F(5)=F(4)+L5+(1-P5)×(F(5)-F(3))

F(5)=(F(4)+L5-(1-P5)×F(3))÷P5

F(5)=(19.682+5-(1-0.5)×9.365)÷0.5=39.999

 

 

结论是

从0级升到1级,平均所需的资源数为P(1)=1.111

从0级升到2级,平均所需的资源数为P(2)=3.889

从0级升到3级,平均所需的资源数为P(3)=9.365

从0级升到4级,平均所需的资源数为P(4)=19.682

从0级升到5级,平均所需的资源数为P(5)=39.999

 

下面是通过计算机模拟宝物升级的过程,并做了统计,再求平均数。一共做了五组,每组1000000次。

 

  理论值 第1组 第2组 第3组 第4组 第5组
P(1) 1.111 1.111 1.111 1.111 1.111 1.111
P(2) 3.889 3.889 3.890 3.890 3.889 3.889
P(3) 9.365 9.367 9.365 9.368 9.363 9.364
P(4) 19.682 19.685 19.690 19.692 19.681 19.682
P(5) 39.999 40.000 40.002 40.001 39.996 39.988

 

从上表的数据来看,理论值和实际统计值差别不大了。说明我们分析的理论值是合理的。

 

综述:

F(1)=L1÷P1

F(N)=(F(N-1)+LN-(1-PN)×F(N-2))÷PN,当N≥2时。

 

再给一题:

某宝物初始是0级,现在要升级

从0级升到1级,所需的资源数为1,成功概率为100%,成功升1级;

从1级升到2级,所需的资源数为2,成功概率为85%,成功升1级,失败不降级;

从2级升到3级,所需的资源数为3,成功概率为75%,成功升1级,失败不降级;

从3级升到4级,所需的资源数为4,成功概率为65%,成功升1级,失败不降级;

从4级升到5级,所需的资源数为5,成功概率为55%,成功升1级,失败降1级,降为3级;

从5级升到6级,所需的资源数为6,成功概率为45%,成功升1级,失败降1级,降为4级;

从6级升到7级,所需的资源数为7,成功概率为35%,成功升1级,失败降1级,降为5级;

从7级升到8级,所需的资源数为8,成功概率为25%,成功升1级,失败降1级,降为6级;

从8级升到9级,所需的资源数为9,成功概率为20%,成功升1级,失败降1级,降为7级;

从9级升到10级,所需的资源数为10,成功概率为15%,成功升1级,失败降1级,降为8级;

问:某宝物从0级升级到10级,所需要的资源数平均是多少?

 

你的答案是多少?我的答案是7763.564285

上一篇:解读 V8 GC Log(一): Node.js 应用背景与 GC 基础知识


下一篇:arguments 对象的老历史