《关于大航海时代2 的一类常见 bug》
作者:horsepower7
发表时间:2014-01-18
本贴也许会让大多数人不感兴趣,主要为了回答某人关于招收航海士的问题:有些航海士,在爵位高的时候收不了,改国籍后爵位清零了反而能收,这是什么原因呢?
这其实是游戏中很常见的一种 bug。这里的“常见”,指的是在程序中常见,不是在游戏中常见。
其实原理说来很简单,就是“数据溢出”。以下介绍相关的计算机知识。
==============================================================
大家都知道,计算机的运算数据有“字节”,“字”,“双字”等区别,一个“字节”是 8 位,能表示 0 到 255 的数字;一个“字”是 16 位,能表示 0 到 65535 的数字;一个“双字”是 32 位,能表示 0 到 4294967295 的数字。
溢出,就是这样一种情况:比如一个字节 a 等于 200,另一个字节 b 等于 100,我们如果计算 a + b,算出来结果是 300,写成 2 进制是:100101100。但这个结果是 9 位,超过 8 位了,要想把这个结果存进一个字节里的话,计算机不得不把超过 8 位的部分扔掉,而只保存最后 8 位。这样一来,如果进行字节操作 c = a + b,最后结果会变成 c = 00101100(2 进制)= 44。
上面举的例子是加法溢出。乘法同样会溢出,而且更容易发生。如果字节 a = 20,字节 b = 15,我们计算 a * b 并存入字节 c,就会得到 c = 44,计算结果就错了。
一般来讲,程序员都应当特别注意这些问题,避免因溢出而产生错误结果。
然而有些程序员的编程是体育老师教的,就会忘记考虑这些情况。
==============================================================
我们现在来看一下我在前贴中给出的航海士招收判断算法。这里只摘录相关的重点步骤,详情请看前贴:
http://tieba.baidu.com/p/2820245810==============================================================
4、找出该人的 7 项能力值中最高的一项(有并列的取排在前面的),计算一个数:A = (该人 7 项能力的最高值) * (该人的航海等级 + 该人的战斗等级)
5、计算另一个数:B = (主角的相应能力值) * (主角的航海等级 + 主角的战斗等级),这里“主角的相应能力值”指的是要招收的那人的最高能力值的那项,比如那人最高的能力值是“知识”,在这里就要用主角的“知识”来计算
6、再计算 C = B + (B * 主角的爵位) / 10,然后取一个 [0, 20) 的随机数 X(记号 [0, 20) 表示大于等于 0 小于 20),比较 A + X 和 C,如果 A + X >= C,会说“对不起,我不去.再积累些经验吧!”,招收失败
==============================================================
好吧,也许你会有疑问,为什么我所有的贴子里的公式都写得那么复杂,像是 C = B + (B * 主角的爵位) / 10 这样,为什么不把 B 提出来,写成更简洁直观的 C = B * (1 + 主角的爵位 / 10) 这样呢?
原因就是,我写的公式,是按照计算机的计算步骤来的。计算机在算乘法的时候,可能发生之前说的溢出问题;而在算除法的时候,会把余数舍掉,只取整数部分。
比如,如果做字节操作,计算 100 * 3 / 3,算出来是多少呢?答案完全不是 100。
首先算 100 * 3,得出 300,但因为是字节操作,溢出了,结果会变成 44。
然后再算 44 / 3,结果是商 14 余 2,余数会被舍掉,结果变成 14。
我在公式里没有写出每一步是字节操作还是字操作还是双字操作,因为不想把公式弄得太复杂;但乘除法的顺序绝对不能换的,比如 C = B * (1 + 主角的爵位 / 10),由于主角的爵位永远小于 10,所以 主角的爵位 / 10 永远等于 0,这样算出来会变成 C = B,公式就不对了。
也许你已经发现了为什么有时候爵位高反而招不到航海士——原因就是溢出。实际上,在这些公式里的操作,全都是字操作,就是说最大不能超过 65535——这个上界明显很不够,当主角的相应能力值达到 100,航海和战斗等级都达到 100,而爵位等于 9 的话,这时算出的 B = 100 * (100 + 100) = 20000,再计算 B * 爵位,会溢出得一塌糊涂。
这样,之后的所有计算当然也都是错的了。而当爵位清零之后,变成 C = B,又回到 20000 以下,不存在溢出问题了,就又能招收了。
这种潜在的 bug,在游戏中比比皆是,我完全没有办法总结一下全列出来。在此再举一例:
==============================================================
金钱的上限是 600000000(6 个亿),以一个双字(32 位)存放。而在王宫被捕会扣掉 4/5 的金钱(这里有另一个算是小 bug 的问题,就是银行贷款也会扣掉 4/5…… 当然你也可以说这很合理),这个扣钱的计算过程,如你所想,是这样的:钱 - 钱 * 4 / 5。
如果钱是满的(6 个亿),当计算 钱 * 4 的时候,会得到 24 亿——看上去好像没有超过 32 位的上限,但问题在于,下一步计算 除以 5 的时候,是按有符号数来算的,也就是说,首位为 1 被认为是负数。而 24 亿 超过了 32 位的上限的一半,首位为 1,就成为负数了。
这样一来,如果以 6 个亿的现金去王宫被抓住,扣的钱就会出问题。不会出问题的临界值是 2^31 - 1 = 536870911,也即是说钱大于这个数字之后,进王宫被捕,钱的计算就会出问题。
==============================================================
正如之前所说的,程序读得越透彻,越感觉这个游戏变得丑陋起来…… 很纠结。
补充说明一下,我上面举的王宫的例子,其实问题更复杂,还牵涉到 neg 0x8000 的问题,总之大家了解大概原理就行了。