【GAD翻译馆】游戏编程中的数学：基于噪音的随机数字生成

翻译：王成林(麦克斯韦的麦斯威尔) 审校：黄秀美（厚德载物）

大家早上好！欢迎来到GDC 2017。感谢大家周一早晨来到这里听我们演讲！这个演讲是关于游戏开发者们所用到的数学知识的。今天一天的演讲都是关于游戏中的数学的，将涉及到很多方面，所以请随意听你感兴趣的内容。提醒一下大家，请将你们的手机静音，另外如果你是毒品贩子请关上你的呼叫机。在演讲结束后，如果你之前没有参加过GDC，那么你会收到一封要求你复习讲课内容的邮件，其中包含一些反馈问题，请耐心填写，只需花费很短的时间即可完成。我们很重视这份反馈，会认真地阅读。

今天的日程是这样的：

上午我们有两个1小时的演讲，演讲者是我和Mike Acton。然后是午餐时间。下午有一些半小时的演讲。我们按照这个日程走好了。

好。首先我想稍微了解一下大家。第一次参加GDC的朋友们请举手。不错，大约占了2/3。好，请放手。然后之前参加过GDC但是第一次听这个数学系列教程的人请举手。好。看来大部分人都是第一次听。如果你是一名学生请举手。只有几个。教育家？也有几个。全职游戏开发者？不错，大部分人都是。

我的演讲题目是基于噪音的随机数字生成工具（Random Number Generator，RNG）。主要讨论“为什么在有噪音的情况下还需要随机数字？”，以及“任何使用随机的程序，使用噪音效果会更佳！”

我是一名游戏开发者，程序员。我从Apple IIe那时就开始编程了。我是物理专业的学生。我作为一名游戏开发者已经很长时间了。我作为GDC的演讲者也很长时间了。我是SMU Guildhall的一名讲师，SMU Guildhall是一所培养游戏开发者的研究所。

我曾在很多公司中工作过，担任技术指导。或者在这些公司中主持开发过项目。去过很多公司，参加过很多项目。

那么今天我们要讲的是随机数字生成工具，包括rand（）以及其它函数。我们将探讨一些噪音函数，包括一些光滑的以及分形的噪音，比如柏林噪音和simplex噪音。我会介绍几种噪音比随机数字生成更加重要的情况。然后我们当然会介绍一些相关的应用。

这个演讲的受众很广，包括那些：

最近热点话题PCG（Procedural Content Generation，程式化内容生成）感兴趣的人。

当然还包括那些想要通过投骰子得到随机结果的人。

如果你使用rand（），这个演讲绝对适合你。

即使你使用Mersenne Twister甚至一些你认为更复杂的函数，这个演讲也适合你。

或者你正在使用在StackOverflow上面找到的一些哈希函数，例如MD5，SHA-1，那么这个演讲也适合你。

下面我们介绍它的一些用途，因为只有知道如何使用它才是最重要的不是吗？

一个随机数和噪音最常见的用处是程式化生成不同的世界。比如随机生成高度贴图，生成山脉以及湖泊，或者在rogue-like游戏中随机生成地牢。我们还可以随机生成很多东西，比如星球，村庄，宇宙飞船，花朵，拥有随机性别、个性、背景、职业的NPC，甚至随机任务。除了山脉以外还有很多我们想要随机生成的东西。

有一些更加复杂的问题，Shay Pierce会在下午的演讲中谈到，就是我们希望在一个很大的（近似无穷的）世界中创建或者放置一些不同的事物。例如在《我的世界》中你可以一直向前跑，不过你会时不时地看到一些重复的树木或者村庄，那么由于这是个无穷的世界我们该如何决定这些物体的位置呢？

我们希望做一些粒子特效，其中包含成千上万个粒子，每个粒子的运动是随机的，如果设置不当粒子的运动会很奇怪。

目前有一些AI算法也需要随机性，比如要用到马尔可夫链，遗传算法，MCTS（蒙特卡罗树算法）等等。

回到《我的世界》这个例子中。我们希望以随机顺序生成不同的地形。比如一名玩家向西走，他发现了一座山。很好，西边有了一座山。他只看到了山的一部分，这时山只有右半部分被生成。然后玩家向南走，绕过这座山，来到了另一侧。这座山应该仍然在那，而且山的左边应该能和右边对应上。

我们希望可以交换种子。我希望朋友试玩某个种子数生成的地图，这张地图中在森林深处有一座高塔。

随机数生成以及噪音可以成为网络压缩的最终形式。我生成了22G的数据，如果我将秘钥发给你，那么就相当于是将无限大的数据压缩成1个数字。这是一个巨大的优势。

硬盘压缩也如此。如果我生成了一些山坡，只要它们没有发生变化，我不需要将它存储在硬盘上，我可以随时根据需要生成它们。所以这也是压缩的最终形式。

好了，总结一下。我想要谈谈这些：

我们对RNG有哪些要求，

我们应该使用哪些RNG以满足不同的需求，

RNG的一些局限性，

噪音函数及其替代物，

以及有没有可能使用噪音制作一个RNG，

或者使用RNG制作一个噪音函数，

最后还有一些建议。

我们对RNG有哪些要求呢？

首先，我们对RNG有哪些要求呢？一个好的RNG有哪些特点呢？我觉得相关学者们会说“这样取决于其周期……”。错，实际上取决于谁问的问题。如果你是国家安全局的，你需要不同的算法来满足各种需要。如果你是《我的世界》开发者，那么你需要使用RNG制作其中一个赌场小游戏。因此取决于问问题的人。

那么我，作为一个对程式化内容生成感兴趣的游戏开发者，对RNG有哪些要求呢？

我希望得到公平的，足够随机的统计分布。我非常希望如此。另外，99%的公平性要比95%的公平性要好得多，并一定非要100%，但是当其降到95%时我们能看出区别。

我们不希望它发生重复，不是吗？比如投掷一枚硬币，我们得到头尾尾头头头头头头头……我们不希望这种情况发生。事实上，这种情况可能发生，而且如果它能发生我们就希望它发生。

我们希望它的重复周期非常长。如果我们运行随机数字生成器，我们希望它在太阳毁灭后才结束循环周期。如果它的周期上亿了，那么谁还在乎呢？我一会儿再讨论它的最大值问题。

不过我们一定要确保它不会重复地太快。只要序列能达到百万-十亿级别，那么基本就没有问题了。大部分你使用的RNG的序列长度都达到了十亿，所以不是什么大问题。

我们希望可以使用种子，比如使用15生成的世界和使用17生成的世界完全不同。我希望种子数也很多，比如32位的种子可以多达四十亿，这已经很多了。很多RNG对于种子的数值很挑剔。例如不要使用偶数，使用大质数，千万不要使用0……我不希望它对于种子有过多的限制。

有一些RNG有一个“热身”阶段，你在得到不错的数值前会得到一些不好的数。实际上一些最有名的RNG这一点都很糟糕，这可不是我想要的，因为有的时候我想要输入一个种子然后得到5个数字，或者输入另一个种子然后得到20个数字。我要的是序列靠前的那些数字，因此我不喜欢这个“热身”阶段。

从统计上讲，我希望这些种子是彼此独立的。假设你给我32个随机位，那么应该有50%的概率为1,50%的概率为0。它们应该彼此不相关。这是空间上的彼此独立。还要在时间上彼此独立，意味着下一个结果应该和上一个结果无关，至少不应该被人观察到相关。

平台独立性——我绝对想要这个性质。比如安卓客户端，iOS客户端和Mac客户端之间互相传输种子，那么我使用你发给我的种子生成的内容一定要和你使用它在你的设备上生成的内容一样，即使你的CPU和我的截然不同。比如你用的是32位的ARM而我用的是64位的Intel。

我希望它拥有顺序独立性（即随机获取），既可以取序列前面的数又可以取后面的数。比如获取序列的第75个数。不幸的是，RNG在这一点做的不是很好。我们后面会更加详细地谈到。

我需要它的可复制性（确定性）。假如我输入种子数17，那么下次我输入种子数17时应该得到相同的内容。这一点至关重要。

RNG的速度有多重要呢？我们也许会生成非常多的随机数，且我们希望在实时中生成它们。一些有趣的算法可以生成上百万的随机数，所以速度也很重要。另外我们可能会实例化成千上万个RNG，每个RNG会输出一个随机数字。因此我们可能也对RNG实例化的速度有所要求。

内存占用。每个RNG占用多少内存？如果同时运行上万个RNG，它们的内存占用会如何？会不会占用很多空间？

它们可以并列运行吗？如果我有很多个线程，它们可以同时生成随机数字吗？是否线程安全？我是使用一个RNG为每个线程生成数字，还是在每个线程中创建其自己的RNG？

我们应该使用哪些RNG呢？

好了，那么现在网络上都有哪些RNG，我们可以使用哪些呢？这一部分我会讲快一点，使大家稍微了解一下它们的基础原理。最简单的一些RNG是这些，它们的基础原理都显示在这里。

通过代码你可以看到，它们其中含有一些内部的状态（即数字），然后乘以某个奇怪的数字，比如一个大质数，得到了新的状态，然后将其作为结果返回。你在下次调用它时，它会使用这个新的状态，进行更多的计算，然后将结果返回。所以它的状态在不断地变化。这个RNG很不好，因为如果我输入0作为种子（即状态为0），那么0乘以任何数字都是0，它就会卡在0上了。

Numrical Recipes对其进行了改进，将其命名为混合同余生成器（Mixed Congruential Generator），其中他们将状态先加上某个数字，然后再做乘法。我之前以为这就是rand函数所用的方法，但是后来发现我错了。

那么为什么不使用rand呢？它一直作为标准，大家都知道怎么使用它。

大家也许知道，rand不会给你太多的数字，它的范围只有从0到32767。如果我要32位的rand，我直接将三个rand拼接在一起不就可以了吗？比如使用位移的方法。所以我们可以制作一个TripleRand。

能看到我的鼠标吗？这15位是rand的结果，最后这两位在统计上不稳定，我们不管它。我们只需使用rand生成结果，将结果位移几位，使用rand生成结果，将结果位移几位，然后将它们混合在一起，得到一个32位的结果。

不幸的是，当调用次数达到百万级别时，rand函数的速度就没有那么快了，而调用TripleRand只会更慢（相当于调用rand三次！）。

另外在统计上来讲，rand的结果并不理想，因为它生成的随机数分布非常均匀。TripleRand生成的结果还好。

另外rand还使用了一个全局状态，如果我有16个不同的线程，我可以使用srand将种子设为17，然后我调用rand。如果其他线程也在进行同样的操作，那么线程之间会发生冲突，会对我的数列造成破坏，因此就多线程而言，这绝对是一个最糟糕的性质。

以上是rand的一部分问题。

让我们来看一看根据这些RNG的结果和速度得到的量化等级。Identity是一个RNG：每当你要求它输出一个结果时，你会得到1,2,3,4……就这样。很明显，它的结果不是很好。后面这几组数字是我做的一系列测试的结果，我们可以在后面详细地谈谈，不过我先简要介绍一下：

BitsAvg：结果中平均每一位为1和0的概率是否相同。

BitsIndie：平均上，结果中的位是否彼此独立。

NextIncr：下一个数字是否可能更大，每一次应该有一半的概率更大。

ByteDist：每个字节是否在各概率区间的正确分布？

ModDist：如果我多次使用不同的数字对其求余，结果是否分布均匀。比如我计算rand（）%7，那么我面前这七个篮子里是否有同样多的数字。

从这些数据中你可以看出，大部分早期的RNG功能有限，在这些统计测试中结果很不理想。不过还好这个TripleRand函数表现很好。我们观察一下上面的调用次数，你会发现我可以在一毫秒钟调用这些函数很多次。虽然TripleRand每毫秒调用的次数最少，不过10k 已经是一个很大的数字了，除非你需要调用它上百万次。总的来说TripleRand是目前最好用的了。

另外还有一些，我就不详细介绍了。如果你现在就要离开这个演讲的话，那么我建议你至少要知道这个xorshift1。

它和rand相似，不过不会出现rand的问题。这是一个简单的算法，你可以自己设置位移并进行异或运算。多次重复这些运算，你会得到很好的统计结果，绝对出乎你的意料。另外这个算法还有一些其它的变体。

到目前为止，大家肯定在想：天啊！你为什么不介绍我们大家都知道且都在使用的Merseinne-Twister（梅森旋转算法）呢？这是最好的算法且C 标准也已支持。那么让我们看看吧！

首先它并不简单。如果我调用屏幕右边的Rand，它会做很多事，其中就包括调用屏幕左边的Twist函数，也是一大堆内容，其中包含一个for循环，看上去速度会很慢。实际也是如此，我们一会儿详细地说。

Intel在网上发布了很多很酷的RNG，这是我从他们网站上找到的一个。

大家应该都能明白它的代码吧。

那么我们来看看这些RNG的效果如何。

注意在所有这些RNG中，TripleRand下面的成绩都很好，MT分数为98，稍微差些。对于这些RNG我们还进行了一些其他测试，一会儿我们会讲到。这些测试更加简单，更加直观。这里MT实际上不是最好的，这些xorshift成绩更佳。如果我们观察它们的调用次数，我们发现MT的速度非常快，而xorshift的结果质量更佳，同时速度也更快。这很有趣。另外还有一点也很有趣：MT的种子设置时间要比其它的RNG慢了上百倍，要为它的结构设置种子太困难了，另外还要占用很大的内存。

所有这些函数都是基于递归关系函数的核心概念，即所有这些RNG的原理基本相同：

使用你输入的状态，对其做一些神奇的运算，然后返回结果。在下一次运算中使用这个结果作为状态，然后对它做一些神奇的运算……因此，只要你的运算方法足够神奇，你会得到一长串有趣的结果。

最后我稍微提一下，有个新函数叫做std::random_device，我忘了是否是在C 11中添加进来的了。

你不应该使用它来进行随机数字生成。它的随机性是基于物理真实的，我不知道是基于CPU核心的温度还是其它什么，不知道他们如何使用计算机实现这一点。它输出的结果是真正意义上的随机，而不是伪随机。对于游戏而言不是很实用，如果你想要“超级随机”的内容，你只能抛弃你的RNG了。

接下来我想谈谈RNG的局限性，包括上面我们介绍的那些。

它们中有很多都对种子有限制，就像我之前说的，如果你使用偶数或者0作为种子，那么有一半结果会发生错误。另外有些还有奇怪的要求，如种子必须是质数，或者必须是一个形如2^n-1的质数。假如我想要根据不同的ID生成星球或者NPC，比如一个NPC的ID为12，我们使用12作为种子生成一个NPC，在这种情况下如果该种子不适用于RNG怎么办？我们会得到一个糟糕的NPC还是很多重复的NPC呢？还有一个更大的问题：关于“RNG所使用的种子”这种说法可能会造成人们误解。种子并没有生成一个新的数列，它只是改变了同一数列中的起始点。所以如果数列中有数亿的长度，我们可以使用一个种子从中间开始，或者使用一个不同的种子从三分之一处开始。而数学家们对于像MT这种拥有超长循环周期的数列感到非常激动，因为你不太可能找到和之前一样的区域。不过种子并不意味着一组完全不同的数列，它们只表示不同的起点。

我刚才提到了RNG缓慢的“热身阶段”。包括MT在内，在得到不错的结果之前先会生成一些（从统计学来讲）较弱的数值。如果你使用RNG进行科学编程，需要上百万的结果，那么从统计学来讲就没有问题。但如果只想投六次骰子随机生成一个NPC，那么结果会很糟糕。

线程安全，这一点非常重要。大多数RNG，包括MT都使用了一个内在的状态，所以并不是线程安全的。每一次调用RNG都会改变它们。不过你可以在每个线程中都实例化一个RNG，每个线程都包含一个它自己的RNG，这样做是可以的。不过仍然可能遇到这种情况：一个线程的种子为5，另一个线程的种子为7，一个线程生成数字的速度要比另一个线程更快。事实上由于我们生成的是同一个数列中的数字，这两组RNG有可能会同步，产生重复的结果。另外我们强调不要跨线程使用rand，因为它有一个全局状态。

顺序依赖性——这是我对这些RNG感到最不满的地方的了。每一次调用都会影响下一个结果，所以我们生成物体时必须严格按照一定的顺序。比如我只给你种子数17，这是不够的。你需要生成同样的NPC，纹理块，地图，武器，掉落的装备，粒子效果，顺序必须和我的一样，否则数列会被打乱。所以它是严格按照顺序生成的。如果我们想要不按照顺序无限地生成物体，这就糟糕了。为了解释这一点，假设我们有一个无尽的世界。

【插入视频：island】

我可以一直向前走，这个世界在不断地生成。假如我看到这里有一座岛屿，不知大家看没看见在远处有一座部分生成的小岛。我们退回来点，然后来到这个位置进行一番探索。然后我们从东边而不是南边接近刚才那座小岛，我一定还要遇到刚才的那座小岛。所以我们不能提前使用随机数字计算出所有的岛屿位置，因为岛屿数量是无穷的，我要能以任意顺序看到它们。

糟糕的随机访问。你如何在数列中往后跳100个数呢？对于许多传统的RNG，你必须重复生成一百次才可以。你想要往前跳3个数？抱歉，你不能这样做。如果你知道使用种子数2261进行了 1400次调用，那么你需要重新设置种子然后进行1397次调用，这太荒谬了！因此RNG的随机访问这一点很糟糕。

非普通实例化。如我所说，在程式化生成中包含很多有趣的算法，因此需要实例化几千，几万甚至数十万个不同的RNG。如果它们的速度很慢，且内存占用量很大，那么我们能够使用的RNG就很有限了。

缺少时间/空间的连贯性。假如你想生成一个拥有随机高度的平缓的斜坡，你必须提前生成斜坡上的点才能使其在各点之间平缓过渡，你不能询问之前用于生成的数字，太晚了。因此你需要写一些额外的代码来储存额外的数据。

MT:

如果你仍旧执着于MT，那么我直接引用维基百科了：占用内存缓存、速度有些慢、测试失败、不适合蒙地卡罗模拟、在很多迭代中输出几乎相同的数列。

我不是说MT差，我只说打个比方，在大街上随便和一个游戏开发者搭讪，你问他对于RNG有何了解，他会说“rand很差，你应该使用MT”，他们只知道这一点。我说这不一定是真的。

你生成的每个RNG内存占用都达到了2K 。真的使人难以相信。

它的实例化过程缓慢。我很确信一部分原因就是它占用了那么多的内存！

它还有糟糕的成本摊销。假设我们在生成随机数，那么时不时地要获取一堆新的数字。因此次数甚至都不一致。

它有一个“冷”开始，意味着你会得到糟糕的数字。

它严格地按照顺序生成数列。

对于种子的数值很敏感。不要使用0或者其它的一些数字。即使是一个有很多0位的数字也可能使其混乱。

另外它还极度的“缓存不友好”。当你在内存中进行2K的模拟测试时，你的缓存行是64字节，你不会成功地进行随机数字生成。

不过至少它们的质量还不错，不是吗？

好了，让我们讨论一下噪音函数，将它们和RNG做一个比较吧。

噪音函数就像是一张无穷的表格，其中含有很多数字。我输入7，我得到0.09。如果我输入4，我得到0.13。如果我再次输入7，我会再次得到0.09。所以它实际上就是一张查找表。但由于它是个数学函数，它就像一张无穷大的表格，不会占用任何字节。它们的原理基本上是这样：你输入一个位置，比如7，它会对所有的位做一系列的计算，最后返回一个随机数字。

不过整个过程基于7这个数字，所以总会得到同样的结果。所有这些噪音函数基本上都相同，它们会使用你输入的数字做计算。

它没有状态值，因此我们实例化上百万个都可以。事实上我们不需要实例化它们，因为它们是函数，我们只需要调用它们。

没有递归关系。它没有使用一个状态来计算得到下一个状态。没有剩余的状态。

这意味着它完全的线程安全。你可以同时在一千条线程上调用它，不会有任何问题。

现在我们可以真正地随机访问了。你想向后跳？没问题，只需查找表格中107对应的多少。想要向前跳3个？只需查找104对应的数字就可以了。你可以在任意时间以任意顺序询问表格中对应的值。

最后我们可以将真正的种子整合到这里了，不是查看一组数列的不同部分，而是每一个种子都会给我们一组完全不同的（几乎）无穷的数列。

我们还可以使用2D噪音，3D噪音，基本原理是相同的。

我们把它想象为一个关于x，y的（几乎）无穷的查找表格。我可以输入任意x和y值，例如（2,0），我会得到0.05，或者我可以输入（0,2）然后得到一个不同的数。因此对于不同的xy的组合我希望得到一个稍有不同的数字，而对于相同的xy组合总能得到相同的数字。所以它就像是一张无穷的2D表格，不会占用任何字节。

不幸的是，噪音只适用于特定情况，我们不经常使用它:

也许在一款RPG游戏中我们希望草地有不同的纹理图案，那么对于纹理的位置我们可以使用噪音查找得到草地类型3，草地类型2，等等。

如果你使用柏林噪音，你应该知道它要用到一个噪音函数作为基础，所以为此我们需要有一个噪音。

以上几乎就是人们使用噪音函数的所有情况了。

我们可以在更多情况下使用它！首先就像草地那个例子，我们可以使用噪音让事物更加富有生机。假如你要生成1万个兽人，每个兽人都使用它独有的ID来决定它是否偏矮，前肢是否稍长，皮肤是否稍红，牙齿是否稍长，现在你就有了一支长相各异的兽人大军了！就拿这张草丛图片来说吧，如果我加入一些噪音，它看上去更加富有生机了。

微小的变化会变得完全不一样。

幸运的是，我们可以跳跃到数列中的任意位置，这非常有助于生成世界，星球，村庄，NPC。我们可以以任意顺序生成它们，因此无所谓玩家是否先来到这座村庄和村民对话，然后再到另一个村庄（我们按照需要生成的这个村庄）。如果你以相反的顺序访问村庄你会得到相同的结果，因为村庄不是使用数列生成的，而是由噪音函数生成的。

这还意味着如果我们想要知道物体的位置，我们不需要提前生成所有内容，而是按照需要生成它们。它们永远是连贯的。由于我们可以以任意顺序生成它们，意味着x顺序或y顺序，这是对于RNG来讲是一个非常困难的问题。

另外不需要存储大量的数据，因为我们总可以生成它们。事实上，你的电脑会越来越快，而不会占用任何内存。事实上，当前很多情况下计算要比寻找查找表中的内容速度更快，尤其是那些非常大的查找表。不要害怕增加CPU的工作量！

另外它还有助于在一个无穷空间中放置散落物体。这是一个非常困难的问题，如果你有很多程式化生成的内容，你会遇到这个问题。

【插入视频：wave】

我们来举个例子。这里，不知道大家能不能看到，一个生成随机数值的随机函数。如果你熟悉柏林噪音——之前我们的很多演讲都涉及过——柏林噪音比这个函数更神奇，它将简单平滑的噪音层层叠加，最终得到了这样的噪音图案。这个函数（表示的地形）没有尽头，和《我的世界》中的一样。现在我需要在地形上放置一些树，村庄等物体。如果你使用噪音函数，尤其是一个平滑的噪音函数，你可以寻找函数的局部最大值的位置。大家能看到这些蓝色的直线吗？如果我调整一下视图，你们可以看到山坡的数量变多了。如果我增加噪音的噪音程度，我会得到更多的峰值，这座山顶就有两个峰顶了。所以我可以轻松控制树木的数量变多或减少以及调整它们的间距。甚至在平原地区树木稀疏，而随着你进入森林区域，我可以缓慢地增加树木的密度，因此会出现更多的树木。所有树木的位置已经由数学公式提前确定了，无论你从哪个方向接近，我们都知道它们的位置。在任何一部分世界中，我们都可以预先知道树木以及村庄的位置。

这个局部最大值方法非常好，虽然它只适用于噪音，不过你也可以在像这样的平面噪音中使用该局部最大值方法确定树木的位置。

图中的这一点可以是一棵树，这一点可以，这一点也可以。而如果我们对诸如柏林噪音的平滑噪音应用该算法，我们可以得到更佳的结果。我们可以找到局部最大值，我在图片上将它们标记出来了。

我可以调整噪音的密度使其更多或者更少，这个函数会一直持续生成。

所以我们可以使用这个局部最大值的技巧，这是个很好的方法。如果使用的是平滑噪音，那么效果会更好。你可以很容易地调节密度，例如在某个区域生成很多的宝藏。

我们还使用了真正的种子，我们不是跳到了数列的某个地方，如果你使用种子17，你会得到一个和我的完全不同的无穷数列查找表，因此也完全解决了数列偶尔会同步的问题。

好了，现在我们试着将RNG和噪音联系在一起，并分析它们之间的相同和不同之处。基本上所有的RNG都和上面这个函数的原理相似，它们都有一个状态。你想得到一个随机值，你调用这个函数rand。它会对它的内部状态做一番处理然后将结果返回给你。基本上所有的RNG原理都是如此。

噪音函数的原理几乎相同，只不过有点细微的差别。噪音函数没有状态，没有类，没有对象。我们只需输入位置，噪音函数也会进行一系列神奇的计算，不过会立刻返回结果。唯一的不同之处就在这了，没有任何神秘之处。

那么，我们可以使用RNG构建一个噪音函数吗？

虽然你不太可能这样做……这里是一个RNG：它和我说的一样——对状态进行一系列计算，然后返回状态。

我可以使用它构建一个噪音函数：我使用你输入的位置作为种子，然后我返回数列中的第一个数字。这样做完全可以。在这个方法中你可以使用Rand，MT，XORshift等来生成类似《我的世界》中那样的世界。不过这种方法速度并不快，因为你一直在构造这些东西。如果你不想构造它们，你可以使其成为一项本地统计数据，不过现在你破坏了它的结构，现在其中含有一些闲置的状态，因此它严格意义上不算一个噪音函数。那么结论是我们可以这样做，不过效果并不好。而且速度也不快，我们需要调用构造函数、初始化函数，设置种子以及调用rand本身（或者我们使用的那个RNG）！我们讲过，对于诸如MT这样的RNG速度根本不快。

那么另外一个方向呢？我们可以使用噪音函数构建一个RNG吗？

同样，我们不应该进行这样的尝试，不过我们还是看看它的效果如何吧。屏幕上的这个东西是一个类，这是一个我基于噪音制作的RNG。

它拥有一个状态，即当前的位置，该状态从0开始，另外它还包含一个函数Rand。该Rand函数根据位置进行了一番神奇的计算，然后将位置前进1。这其实就像是你从无穷的噪音查找表中一个接一个地获取随机数。

事实上它的速度非常快，过程简洁，且不会发生重复。因为没有使用自己的状态，它不会陷入一些奇怪的循环，比如输入0会得到0，或者输入1得到7，输入7得到2，输入2得到1……因为这个方法是基于不断增加的位置，它几乎不可能陷入这样的循环（因为它不是基于这种递归关系的函数）。那么，它很简洁，速度很快，到底有多简洁？速度有多快？当然不会比实际的RNG速度快了，很明显这和你选取的噪音函数有关。

让我们回到噪音函数，我想为大家展示几个例子。假设我有一些噪音函数，对于这个演讲我假设它们都是这个样子的：你输入一个位置，你得到一些被打乱的随机的位，就好像是在想象中的查找表中获取数值一样。我们有很多方法可以实现这一点：

我们可以乘以一些大质数。为什么是质数呢？如果乘以12，那么我知道结果一定是3或4的倍数。如果乘以2或者任意偶数，那么结果一定是偶数。因此一般我们都乘以质数。我们希望乘以大质数，因为这样可以打乱所有位的顺序，使其完全发生变化，我们希望如此。

我们还可以加上一些数字，不过这样做的效果不如乘以大质数的效果明显。

我们还可以对其平方，这样得到的结果不太可能和输入值有任何线性关系。

我们可以使用XOR系列的方法，对数字各位进行异或位移，这个方法对于打乱数字拥有惊人的效果。

无论我们做什么，基本上都是对数字进行打乱处理，然后返回结果。结果严格依赖于你输入的值。

好。那么你可能觉得我说的这些方法很酷炫，而当你离开的时候把我说的都忘了，然后上StackOverflow搜索噪音函数，然后你得到了这个。

它只会返回奇数，还不错。

还有LibNoise。

LibNoise是一个非常棒的C 库，它和StackOverflowNoise一样，只不过使用了不同的位移数字，不同的常数。

想一想，其实噪音函数就是哈希函数的一种特殊形式，不是吗？对于传统的哈希函数，我可以输入一整段文字，或者一些文件数据，然后它对其进行一番处理，最后得出一个神秘的数字，可能是CRC或者类似的。如果我们希望输入一个整数然后得到一个随机数字，我们可以将其视为一个哈希函数。

这里有一些哈希数字。当Ken Perlin第一次发表柏林噪音时，这是他推荐使用的哈希函数。

首先有一些数字，范围从0到256，顺序被打乱了两次。然后他进行了一系列的查找操作。稍微解释一下这里：这个p代表的是查找表，所以这里是在表中查找数字，然后有一个偏移，然后再在表格中查找，然后偏移，不断地嵌套。那么如果这个表格中有512个字节，那么我们的L2缓存会有一部分的丢失，或者类似情况的发生。

好了，我们来看看它们的表现吧。

Identity我们之前提到过，它是最无聊的那一个。Bernstein，LibNoise，StackOver，PerlinHash，我们看到它们基本都是D或者F。令我感到意外的是在质量方面Bernstein居然比Identity分数还低，也挺不容易的了！这些函数中PerlinNoise的分数最高，不过和其它函数相比它的速度太慢了。

不过我们还有更好的办法。啊哈！我们有真正的哈希函数，为什么还要用这些自己造的垃圾呢？我们来使用MD5和SHA1吧！这周我们才刚刚碰到SHA1的第一个真正的128位碰撞。它们的过程就像这个样子，只不过这里不是散列一个文件，而是散列一个整数。

然后它进行一番神奇的运算，使用的算法极其复杂（SHA1好像是NSA参与开发的）。

好了，我们来看看它们效果吧。

这里有很多哈希函数，我基本上是根据性能对它们排序的。你可以看到上面这些函数很垃圾，尤其LibNoise和StackOverflow，以及我搜索到的那些。其它的像MD5很好，SHA1很好，CRC很好，这些Murmur函数也很好。关于MD5和SHA1这两个一提到哈希函数就能想到的函数，它们的速度很慢。和下面这些哈希函数相比，它们不是慢了2倍，而是100倍！如果我使用其它的哈希函数也能得到优秀的结果，那我为什么还要用这两个呢？ 和我们简单的用途相比，MD5和SHA过于偏向于工程使用了。它们可以适用于任何大小的数据体，得到的结果从密码学角度来讲异常可靠。我们不需要这样，只希望输入一个数字然后得到一个不错的随机数就可以了。所以不要使用这些函数，杀鸡焉用宰牛刀嘛，除非你希望在安全保密领域使用它们。

我自己也写了一个哈希函数，尝试了几个，这是我写的第3个。

上面这些是质数。我使用它们乘以位置，然后位移等等。在我写完这个函数后，c 11发行了。它们加入了std::hash，要比我的这个更简单些。也许我应该使用它。让我们看看它们的性能吧。

在最下面就是CPPHash了，你可以看到它们的效果还不错。且它们的速度要快很多，要比上面这些快了3倍。而我写的这个也很快，甚至比这两个CPPHash还快。到目前为止看上去还不错，我选择使用我自己的哈希函数！

不过如果你不想下载我的函数库，或者不信任我的代码，或者其他什么原因，你可以相信std::hash<int>的作者。

它的速度很快，效果很好，如果你想选择一个很好的噪音函数，那么我推荐你使用它。

其它速度又快又给力的函数基本上就是这两个CPPHash和我自己写的这个函数了。在所有哈希函数或者噪音中这些是最快的了。

在强调一遍，MD5/SHA1这两个严格符合工业标准的函数你绝对不需要，没必要多花费200倍的时间得到几乎质量相同（可能稍微好点）的结果。

我选择使用我自己的函数，因为我知道它的原理，而且知道它在所有平台上都能平稳运行。我比较懒，还没有去阅读std::hash<int>的介绍，也许它保证它的算法永远不会改变，我严重怀疑这一点。也许它保证在所有平台上的运行效果均一致，我也严重怀疑这点。我反正知道我的函数能正常运行。学着如何使用这些函数还是有很大好处的。

我刚才说过，我们可以在噪音函数中使用种子，而且它们不是普通的种子，而是非常好的种子，一个种子可以给出一整张不同的数字表。所以噪音函数中的种子相对简单，我们不需要建立像RNG中的状态，我们只需包含一个数字的破坏与计算过程即可。

另外，根据我做过的实验来看，如果我在前面将种子添加到数列中作为计算过程的一部分（不过不能放在第一步，因为这样的话种子和位置的作用没有区别了），那么我会得到不错的结果。这是我使用的方法。

当然了，如果我们想使用std::hash<int>，我们也可以轻松地加入种子。哈希函数有一点好的，你可以散列任何东西。所以你可以定义一个将位置和种子作为输入参数的哈希函数，对它们同时进行散列，而结果实际上还很不错。

好了，我们刚才说到我们想要2D、3D噪音，主要用于柏林噪音或者用来确定地形上树木的位置。假设我们有一个1D噪音函数，它需要输入一个位置参数以及一个可有可无的种子参数，我们可以如何得到一个2D位置呢？有很多种方法，我们可以写几个不同的自定义算法，以不同的方式利用XYZ位置。不过你可以在StackOverflow上找到的一个标准的方法是将Y坐标乘以某个质数然后加上X坐标。事实上这个方法得到的结果还不错，在x或y方向上几乎不可能有任何可识别度。所以它有效地将X和Y混合搅拌得到了一个1D位置，然后我们使用这个位置在表中进行查找（这里表格指的是噪音函数的）。

3D也类似，我们将XYZ进行混合，其中用到了不同数量级大小的质数使它们远离彼此，因此任何有关XYZ细微的变化都能导致巨大的差异。

好了，我们总结一下。我们可以使用噪音函数构建一个RNG吗？当然了！而且它占用空间很小，速度很快，另外还不会重复，线程安全……有多小、有多快呢？取决于你使用的噪音函数。我现在使用std::hash以及我自己的哈希函数来构建RNG，然后我们将它们和其它RNG例如MT做一下比较。

你可以看到很多下面的RNG的总体分数都很高。如果你想从数列中获取一个数字，你会发现CppHash实际上效果稍差。所以在统计上来看它的表现没有那么好，不过也是不错的。如果你仔细观察一下屏幕上方它们的速度，这列速度表示的是每一秒我可以调用rand的次数。我自己写的噪音在所有函数中速度最快。它的种种子的速度很快，调用rand的速度很快，因此很明显生成噪音的速度也很快（因为它是基于以上二者实现的）。而对于MT，如果我使用种子跳到一个位置得到一个数值，然后使用种子跳到另一个位置得到一个数值，这个过程速度极其缓慢，比其他的慢了1000倍。

好了，我们来总结一下今天演讲的重点吧。

噪音非常有用。我希望你能记住这一点。噪音非常好，要学会使用它。噪音能做很多RNG不能做的事。对于RNG不能做的事，或者修改RNG使其假装和噪音一样，为什么不直接使用噪音呢？

巧合的是，使用噪音制作的RNG要比RNG本身效果更佳！我不是一名学术研究者，不过我对于如此貌似明显的事实还是惊呆了。如果会场内有任何研究者想要在演讲结束后联系我，我们可以更多地谈谈这个问题，看看我是否错过了某些东西。不过我之前使用它生成了很多很多东西，而它的表现不俗。

另外一条建议，不要使用Rand（）。我知道它很方便，不过不要使用它！它的效果很差，你花五分钟时间可以写出一个比它的速度更快，性能更佳的函数！

我曾经对MT寄予厚望，现在不对它抱有任何期待了。不太确定你是否需要它。

总的来说，我的建议是尽量使你的函数占用空间小，简单，快速，灵活，可以调控它们以便完全了解它们的功能。

所以使用噪音吧！！

最晚下周我会将今天演讲中所有的幻灯片都上传到mathforgameprogrammers.com上，如果你感兴趣可以去看看。其中包括这个，我简单地介绍一下它。这是基础的噪音函数，另外我还有一个函数库其中包含一些简单的噪音函数，我可以使用它们得到2D、3D、4D噪音，有可以返回浮点数的函数，还有将返回结果限制在-1到1（或者任何你想要的范围）内的函数。

另外我使用这些函数构建了一个RNG，你可以设置种子，修改种子，快进或者重复等，或者你可以仅使用它返回一个随机浮点数，一个随机字节，或者一个随机方向向量，或者其它。有很多像RollRandomChance这样的函数你可以放在你的函数库中，以便写入或者调用更加方便。RollRandomChance，你只需输入返回是的概率。你有多少次需要自己写代码来检验投骰子得到某个数字的概率？为什么不使用函数检验以增加代码的可读性呢？

好了，我的演讲结束了，非常感谢大家！

现在是问答时间，如果大家有问题的话，请用这个麦克风讲话。另外不要忘了填写反馈表，感谢合作！另外，Mike Acton的演讲在20分钟以后开始，他讲的是关于codingame的挑战。

问：你好，我在制作一款学习游戏，所以我需要知道孩子们在游戏过程中正在回答哪一道题。我在设计时将这些题目的顺序打乱，所以它们应该是随机出现的。不过我遇到了一个问题：某些正在回答的题目会影响下一题的结果，所以我来到这个演讲想听听我该如何使用噪音，使孩子们在游玩整个关卡时不会预先知道后面的题目是什么。

答：这是你自己开发的软件吗？

问：是的。

答：理想状态下每道题的生成应该是互相独立的。如果他们正在做的一道题影响了后面题目的结果，这通常意味着你有一个RNG，你正在使用它生成随机数字，然后你就不管它了，继续使用它生成别的数字。所以至少，在不改变任何内容的情况下，你可以重新设置RNG的种子以生成新的题目，这样之前的种子就不会有任何影响了。不过使用噪音也可以。在这个情况下你只需经常变化种子就行了。

问：你好，我只是好奇为什么不将种子作为函数中的另外一个维度呢？

答：这是个很好的问题。一个简短的答案是我们可以这样做。更加详细的理由在于我希望将种子更深地混合在噪音函数中。我比较懒，将XYZ以一种简单的方式混合在了一起。我希望种子更深地参与到随机数字生成过程中去，这样我们得到的数字表和只用位移方式得到的数字表完全不同。我感觉你那样做也没问题。实际上我一直使用2D柏林噪音，只需稍作改变就能得到一个完全不同的数列。

问：你好，我想问一下对于特殊的哈希函数（比如2D、3D）该如何选择好的互质数？因为它们太大，溢出问题开始对结果产生影响了。我们该如何选择它们呢？

答：所以你想问如果我在混合X和Y，我应该将Y乘以多少？

问：没错，溢出会使得结果具有某种规律性。

答：如果你想乘以一个质数，溢出的话它会舍弃结尾的几位。事实上，大部分的RNG都依据一个事实，即乘以溢出的质数得到的结果仍然是随机的。所以根据我的理解大质数不会产生问题。如果不是质数的话，那么你应该规定它的奇偶性。而如果数值很小，那么结果可能会有规律性。因此实际上如果它没有溢出，你应该对此抱有怀疑。乘以一个溢出的质数很难在以后进行跟踪。

还有其他问题吗？好的，谢谢大家！请20分钟以后回来！

【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。