CEDEC南梦宫：从历代作品分析随机算法的进化和应用

游戏开发者的盛会CEDEC (日本电脑娱乐设计者大会)今年在日本神奈川的横浜举办，9月4号是展会的最后一天，今天的演讲主题为“推动游戏世界骰子的正体：从往年南梦宫作品中学习随机算法的进化和应用”。

万代南梦宫 HE技术部的加来量一先生

登台演讲的是万代南梦宫 HE技术部的加来量一先生。

此次演讲采用了一个有趣的方式，以随机选取往年南梦宫作品的视点来回顾。HE技术部的设计师加来量一先生，为大家一一分析了南梦宫时代初期的50款作品，而这些作品在各自的时代是以何种随机的方式被选定的呢?下面为大家带来此次演讲的精彩内容。

上图是1980年代南梦宫街机作品的随机技术一览表。每个程序员都有自己独到的随机生成法。有的是线性合同法(LCG)，有的是线性反馈移位寄存器(LFSR)，也有将两者相结合使用的。

为何要用随机的理由，加来先生认为，随机产生的偶然性才是游戏的本质。所谓随机，就是生成随机产生乱数，就好比骰子一样。每次掷出的数字都不同，由偶然性孕育游戏性。

在游戏里面，随机也担当着重要的任务。敌人的动向、AI的行动等等每次都会有变化。为了使它们不再单一，那就全靠随机来帮助。随机也可以有两种说法，一种是不知道会出现哪种变化的“真随机”，另一种是根据某种规则来实现的“假随机”。目前的游戏采取的都是“假随机”。为何呢?因为如果用了“真随机”，那么一些游戏内容就无法进行二次重启功能。

CEDEC南梦宫：从历代作品分析随机算法的进化和应用

上图是真随机和假随机，现代游戏多采用后者。

与时俱进的“随机”

混沌时代

加来先生表示，南梦宫最初的作品在随机技术里面可归为“混沌时代”。那时CPU的处理能力、内存的限制等各方面因素导致了程序员在不断摸索如何产生随机的方法，也在各个作品中以不同的手法进行尝试。

加来先生用C语言解释了在吃豆人里，采取了一定的乱数生成方式

线性合同法(LCG)时代

在这之后，乱数生成法里出现了线性合同法(LCG)。LCG是以C语言算法生成随机数而闻名。简单的来说就是加法和乘法的组合。当时的CPU(Z80)还无法进行完整的乘法，所以要用连续的加法来模拟出“疑似乘法”，实现LCG。其实，限制还是非常大的。

线性反馈移位寄存器(LFSR)时代

装载简单，还能生成随机数，LCG过后用的就是线性反馈移位寄存器(LFSR)。大家可以看看南梦宫以往的作品《小蜜蜂》中背景里闪烁的星星，其实就是LFSR乱数生成的结果，由LFSR乱数决定哪些星星有颜色或者无颜色。

说到乱数生成，那么这里一定要提一下南梦宫的另外一款旧作《迷宫塔》。本作内容很简单，主人公基路需要通过60层的迷宫来完成挑战。如果放在现在的游戏中，这60层迷宫的地图数据都会存储在游戏程序里。但是《迷宫塔》完全没有这个概念。从玩家进去迷宫一开始音乐响起时，里面的迷宫全部由乱数生成。

LCG+LFSR的时代

因为两个乱数生成的算法中都有各自的优点和缺点，到了80年代中期，我们主要是以两者相结合使用为主。这样一来就增加了游戏乱数算法的稳定性。

Table时代

到了80年代末，因为内存从KB转到了MB，Table方式的随机算法成为了主流。

C语言时代

90年代初开始盛行用C语言开发游戏。前面讲过C语言是以标准程序库生成随机数，所以自制的随机也从此消失。而标准程序库的随机算法是根据LCG来的，那么LCG的问题再次曝出，直到现在我们采用了新的算法。

最后加来先生谈到：“根据乱数使用方法的不同，可以像《迷宫塔》一样，给游戏加点作料。了解随机的性质，在游戏中多多利用吧”!