《Game AI Pro》 高斯随机、过滤随机与柏林噪声
关于《Game AI Pro》 Advanced Randomness Techniques for Game AI: Gaussian Randomness, Filtered Randomness, and Perlin Noise 的学习笔记。主要是三种随机的简介。
高斯随机
介绍
高斯分布广泛存在于我们的身边。学生的身高、体重、成绩等变量都遵循高斯分布。当我们需要随机生成这一类变量时，简单地使用我们熟悉的均匀随机rand()是不符合要求的。这时我们就需要利用高斯随机生成符合高斯分布的随机数。
原理
虽然高斯分布的表达式非常复杂，但是实现高斯随机非常简单。由于中心极限定理，受到多个互为加性的均匀随机因素影响的随机变量即符合高斯分布。例如，掷出三个骰子，它们的和便遵循高斯分布。这个和受到三个骰子各自的均匀分布且具有加性的点数影响，所以为高斯分布。
具体实现中，我们可以类似地生成近似的高斯随机，将几个rand()生成的均匀随机变量加起来即可。例如将三个[-1，1]的均匀随机变量相加，得到的即为分布在[-3，3]中的高斯随机，且标准差σ为1，均值μ为0。其中100%落在 [μ-3σ，μ+3σ] 即 [-3，3] 中，95.8%落在 [μ-2σ，μ+2σ] 即 [-2，2] 中，66.7%落在 [μ-σ，μ+σ] 即 [-1，1] 中。在更为精确的模拟中可能需要模拟落在三倍标准差以外的小概率事件，但是游戏中通常不需要。
其他
高斯随机最经典的用途之一是弹道偏移。大部分fps游戏中都需要模拟弹道偏移以增添真实感，而在弹道偏移量上简单地使用均匀随机得到的效果并不好。如果使用均匀随机，角色打靶的弹痕将均匀分布在靶心附近的一个圆上，圆的大小取决于均匀随机的范围，看起来并不真实。合理的方案是先使用均匀随机得到一个偏移的方向，再在这个方向上使用高斯随机得到偏移的距离。这样角色打靶的弹痕分布将在靶心较为密集，边缘较为稀疏，符合常识。
过滤随机
介绍
小样本的随机事件看起来并不随机。当玩家发现自己被敌人连续暴击三次击杀时，玩家最先想到的通常并非“敌人的暴击率为30%，我被连续暴击三次的概率为2.7%，还算正常”，而是“这破游戏针对我，退坑！”。为避免这种玩家莫名流失的情形，便可以采用过滤随机，“修复”这一“bug”。
原理
过滤随机的实现更为简单，只需在生成随机数时存储最后生成的一段数列，生成最新一项时进行检查，出现一些引发玩家迷惑的组合时考虑重新随机或调整。以下为一些示例
掷硬币
- 如果最新的值会导致连续的四个或更多相同值，75%的概率翻转该值。
- 如果最新的值导致出现了四个值的重复排列，例如11001100，翻转该值（即变为11001101）
- 如果最新的值导致出现了111000或000111，翻转该值
示例
过滤前：0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0
过滤后：0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0
整数
- 出现连续数字，例如 7，7
- 出现连续数字被另一数字隔断，例如 8，3，8
- 出现4个或更多递增或递减的数字，例如 3，4，5，6
- 最后若干个数均较大或均较小，例如 6，8，7，9，8，6，9
- 两个数字的组合在最后十位重复出现，例如 5，7，3，1，5，7
- 某一数字在最后十位出现次数过多，例如 9，4，5，9，7，8，9，0，2，9
浮点数
以[0，1]为例
- 连续两个数差小于0.02，重新随机，例如0.875和0.856
- 连续三个数差小于0.1，重新随机，例如0.345，0.421，0.387
- 5个数连续递增或递减，重新随机，例如0.342，0.572，0.619，0.783，0.868
- 最后若干个数均较大或均较小，重新随机，例如0.325，0.198，0.056，0.432，0.216
高斯随机
由于高斯随机与浮点数随机较为相似，上述的规则仍然可以沿用。除此之外，如下规则也可作为参考
- 连续四个数均靠近或均远离0
- 连续四个数位于2σ与3σ之间
- 连续两个数位于3σ之外
其他
以上的一些策略仅为示例，这并不意味着需要在游戏中使用类似的所有策略。事实上，上述的策略可能过于严苛以至于破坏游戏中随机数的数学完整性。在使用过滤随机时，我们需要仔细思考规则，还可以使用开源程序ENT测试规则下生成的随机数的随机程度。
现在的网游中暴击、抽卡、开箱等事件通常使用更复杂的随机策略。例如假设玩家的暴击率为5%，则第一次击中的暴击率将低于5%。随着连续击中而没有触发暴击，玩家的暴击率逐步上升，在第20次时达到100%。如果中途触发暴击，则暴击率将还原至初始值。这需要设计一条概率曲线，它的增长幅度合理且最终总的暴击率仍为5%。如果概率曲线设计合理，这种策略将使得暴击的触发更为分散，也符合广大玩家“暴击率5%意味着20次必暴击一次”的认知。开箱中的“幸运值”，“保底”等机制也类似如此。
柏林噪声
介绍
柏林噪声通常被用来产生平滑的随机，例如生成起伏的地表，平滑的随机移动，游戏角色的心情变化。一维的柏林噪声即可生成2d地图中的地表，生成类似我的世界的游戏地形则需要二维的柏林噪声。一维柏林噪声大概长下图这样。
原理
实现柏林噪声，我们需要得到一条随机的平滑曲线。对于一条简单的随机曲线，我们可以使用随机数与插值得到，但是这样的曲线过于单调，不满足我们的使用要求。这时，我们可以将一些曲线叠加在一起，得到更具有变化性的曲线。
为了叠加曲线，首先我们需要引入倍频（octave）和持续度（Persistence）两个概念。在生成之前，我们需要选择你的柏林噪声使用几个倍频，这取决于你的精度要求和性能。倍频决定了你的柏林噪声由几个基本曲线合成，以及这些曲线的频率和振幅。其中倍频为n的曲线的振幅为持续度的n次方，而频率为2的n次方。例如如果取倍频为4，持续度为0.5，则我们便要将倍频为1，2，3，4的生成曲线分别乘以0.5的1，2，3，4次方并相加得到最终的柏林噪声，其中倍频为1，2，3，4的生成曲线频率分别为1，2，4，8倍。
那么每一个倍频的曲线该如何生成呢？此处以横纵坐标上限均为1，倍频为4，持续度为0.5为例。对于倍频1的曲线，我们只需要在[0，1]中随机取起点和终点的值，使用缓和函数插值即可。最早的缓和函数为3t2 - 2t3 后来被改进为现在通常使用的6t5 - 15t4 + 10t3，因为这一函数的二阶导连续。而更高倍频的只需如法炮制，不同的是倍频越高，为使频率能够翻倍就需要额外取一些随机数作为插值的依据。其中，倍频1使用2个随机数，倍频2使用3个随机数，倍频3使用5个随机数，其规律为2n - 1 + 1，当然这些随机数都需要间距相等。
生成完毕后，便可以合成为所需的柏林噪声曲线。下图即为一个示例。
其他
柏林噪声在图形学上也有许多应用，可以用于生成火焰，熔岩，大理石等纹理，有许多可以深入研究的地方。这里仅为对文章内容的简单总结，如需更深入了解在图形学上的应用，可以阅读这篇文章。