开发笔记(27) : 公式计算机
我们的项目的第二里程碑在中秋前结束了。这次耗时三个月的开发周期，堆砌了大量的游戏特性，大部分任务都是在追赶进度中完成的，导致最终有很多问题。
所以，节后我们决定调整一个月，专门用来重构不满意的代码以及修理 bug 。好在这次我们的代码总量并不算太大。服务器部分，所有已有的 C 底层之外的代码，全部 Lua 代码，总量在五万行左右。这是一个非常可控的规模。即使全部重写，在已有的开发经验基础上，都不是什么接受不了的事情。所以我对改进这些代码很有信心。
有部分代码有较严重的性能问题，节前我给底层增加了一些统计和检测模块，发现部分逻辑模块，单条消息的处理居然超过了一万条 Lua 指令。比较严重的是 AI 和怪物管理模块，以及战斗的 buff 和属性计算。
这几个问题，接下来我会一个个着手解决。这两天在优化属性计算的部分。
在半年前，我曾经参于过这部分的设计与实现。参见之前的一篇开发笔记 。
不过在写完这个模块后，我的工作从这部分移开。其他同学接手正式实现策划的需求时，并没有使用我实现好的模块。因为策划的需求更为复杂，最终采用了更间接和可配置的方案。相关的实现我未能跟进，Mike 同学就用 Lua 实现了一个基本等价的东西。
到目前，各种参于战斗的属性个数已经到了 200 个左右的规模，它们相互依赖，用一些属性计算出另外一些来。这使得在 Lua 中计算这些公式变成了相当大的负担。但另一方面也有一些好消息，就是很多原来预想的需求并没有被具体使用。比如在属性计算这个层次上。策划并不需要做任何查表运算（那是在上一层，Buff 处理中用到的）。这些需要计算的属性虽然量很大，但它们类型单一，可以全部用浮点数表示，并用基本的四则运算就可以搞定。并不需要更复杂的功能。
我想了一下，干脆把这一整块东西封装到 C 模块中。给 Lua 提供一个基于寄存器模式的纯函数式计算器即可。上层只需要构造一个表达式组的对象，输入若干简单的四则运算表达式，由模块本身做拓扑排序后，得到公式间的相互依赖关系。以及每条公式用到的寄存器号。然后，我们就可以通过简单的寄存器访问接口更新指定寄存器的值，就可以自动去做相关的公式运算得到那些最终需要通过计算得到的其它寄存器的值了。
对于 C 模块，它处理的公式中的变量只是一系列的寄存器编号。用 Lua 做一个简单的封装，把原始公式中的可读的属性名转换成内部编号，仅仅是一个简单的文本替换工作。
整个任务需求非常清晰，实现也不难。不需要动用 tcc 这种重量的外部库。只需要把策划提供的表达式转换为规整的逆波兰形式。计算的时候，一遍扫描就可以得到结果。
ps. 我在设计内部数据结构的时候取了一个巧。内部公式中只保存正的浮点常量（负常量可以通过正常量加一个取负的一元运算替代），然后用 union 来保存寄存器变量或操作符。这样，任何一个逆波兰表达式都可以用一个浮点数组来表达了。
作为惯例，我把花了一天时间实现的这个模块开源了。有兴趣的同学可以去 github 上拿到源代码 。
不太需要多解释，如果你运行这样一段程序：
local attrib = require "attrib"
local e = attrib.expression {
"攻击 = 力量 * 10",
"HP = (耐力 +10) *2",
"FOO = 攻击 + HP",
}
local a = attrib.new(e)
a["力量"] = 3
a["耐力"] = 4
for k,v in pairs(a) do
print(k,v)
end
会得到这样的输出：
力量 3 攻击 30 FOO 58 耐力 4 HP 28
做完这个以后，Mike 同学觉得能在底层把游戏中最常用的一个特性顺带实现了比较好。
简单说是这样：
往往，游戏中 “力量”这个值有一个基础数值。另外，各种装备和 Buff 有可能给这个数值加上一个数字，以及乘上一个比例。我们最常改变的是这个递增值，以及递增比例。有时候，还需要把力量设置为一个绝对值，不受前面那些值的影响。也就是说，默认会有一组公式：
力量 = ( 基础力量 + 力量增加 ) * (1 + 力量增比) if ( exist 力量绝对值) then 力量 = 力量绝对值 end
同理，其它属性，比如智力，敏捷，都有相关的公式。如果能隐藏这些细节会更好一些。
我觉得，这个需求应该在 Lua 层封装好，自动生成“力量增加”这样的中间属性，并给出对应的接口去修改它们。不用在目前的模块中增加代码。至于力量绝对值这种设置，借助一些小技巧。增加一个变量“设置力量”，默认为 0 ，可以改写为 1 。然后：
力量公式 = ( 基础力量 + 力量增加 ) * (1 + 力量增比) 力量 = 力量公式 * (1 - 设置力量) + 力量绝对值 * 设置力量
在不增加新特性的前提下，这也算是一个折中的解决方案了吧。
Comments
斗胆回复一下上面各位的疑惑。
以前我在另一篇blog里错评过这个公式计算系统。现在脑筋转过来了，也想明白了。
一般大型MMO的数值系统是十分复杂的，据我经验一般数值计算要经过一级属性、二级属性、战斗属性至少这三层计算。
如果说一开始能写清楚逻辑，那么经过一段时间的需求改动，过一两年这块代码几乎是只有个别人能看懂了，而且根本不敢轻易修改，一改必错。
云风的方案是用一个公式处理器，用数学方法彻底透明化了整个计算过程。只要策划设计公式时，能把依赖关系表画清楚，那么一定能得到又快又好的结果。
而且策划可以放开想象力，在游戏初期任意修改其公式，管你是一层计算、三层计算还是十层计算，到了公式模块里只是依赖变深了，没有任何区别。
如果这个方案被证明效率ok，那么这可以说是属性计算方面的银弹级模块了。
Posted by: mayao11 | (21) August 5, 2015 10:07 AM
请检查循环依赖
Posted by: Cloud | (20) August 31, 2013 09:06 AM
偶尔的。大约有 40%的情况 会出现
Detected circular reference in topo sort。
不知道是什么原因引起的。求教。
Posted by: 龚辟愚 | (19) August 30, 2013 11:56 PM
@fish1725
因为策划要求公式写在 excel 里可配置.
Posted by: Cloud | (18) June 12, 2013 12:33 AM
为何属性计算公式会写到lua里？这相比于把公式写在项目里编译好+数值配置文件反而费力不讨巧啊。云侠能否就此问题解决一下我的疑惑。
Posted by: fish1725 | (17) June 11, 2013 04:27 PM
直接生成lua的源代码吧....这样感觉说不定会好一点儿...在生成的时候先做好替换。策划能用的数值都是你已规划好的，不管是哪种方案...
Posted by: ten | (16) November 1, 2012 09:10 AM
刚刚看了下源码，一如既往的漂亮，赞！但是在失去了部分灵活性的前提下，性能提升的空间真的很大么？迷惑
Posted by: k | (15) October 21, 2012 12:19 AM
不知道具体提高了多少效率，但使用数学模式来解决逻辑问题，我看行
Posted by: Fydol | (14) October 15, 2012 12:26 AM
不是很明白，为什么需要这个东西？
用lua函数实现也很简单啊。
这些数值应该不会出现相互依赖的情况吧？比如：攻击需要知道力量才能计算，而力量也需要知道攻击才能计算。
function getAttack()
return player.strength*10
end
player.strength = 3
像这样不行吗？不是很理解。
Posted by: niubility | (13) October 14, 2012 02:31 AM
如果可能，我希望游戏中的人物出招招式可以按照个人宏的设计编排，招式可以多样化呢……
Posted by: 海豚 | (12) October 13, 2012 05:01 PM
"折中的解决方案"看起来不错，将程序判断转化成数据状态，不错的思想。
Posted by: eRay Jiang | (11) October 12, 2012 06:03 PM
看来明年可以看到游戏的测试了，加油！看看比暴雪如何
Posted by: tonyhu | (10) October 12, 2012 02:11 PM
呵呵,虽然我不做c和lua,但是也来围观下,学习下游戏经验.
Posted by: lite3 | (9) October 12, 2012 10:02 AM
新博客 mark
Posted by: ctx | (8) October 12, 2012 09:55 AM
改天风哥把魔兽争霸和魔兽世界都实现了
Posted by: orange | (7) October 12, 2012 08:01 AM
一直看博客，很多内容理解不是很深刻，没有实际操作经验。
Posted by: campolake | (6) October 11, 2012 09:24 PM
lua就是干逻辑脚本的，自己写解释表达式会快么
Posted by: neil | (5) October 11, 2012 08:09 PM
请问云大侠，lua里面的循环效率很低，你们是怎么解决的？
Posted by: Anonymous | (4) October 11, 2012 07:01 PM
支持分享所思的心态
Posted by: Peter | (3) October 11, 2012 05:11 PM
终于等来新博文了，mark了慢慢看
Posted by: haxixi_keli | (2) October 11, 2012 05:03 PM
开源的就是好,学习
Posted by: 云上听风 | (1) October 11, 2012 04:57 PM