Creating the Past, Present, and Future with Random Walks

John Manslow

2.1 Introduction

  随机性在许多游戏中扮演着重要的角色，它增加了游戏的可玩性，迫使玩家去适应不可预测的事件。它通常采用随时间变化的随机数值，也称为随机游走（random walks）。这些变量可能会影响天气模拟中的能见度或云量、NPC的情绪或商品价格。

  本章将描述正态分布随机游走的统计特性，并将展示如何对其进行塑造和操作，以便它们在受到脚本约束和响应玩家交互的同时保持随机性。

  我们首先描述如何生成一个简单的随机游走，并讨论它的一些局限性。然后，我们将展示如何利用随机游走的统计特性来克服这些限制，以便在随机游走的过去和未来的任意时间点上有效地进行采样。

  接下来，我们将讨论如何在特定时间点确定随机游走的值，如何控制随机游走在区间内的走势，以及如何将随机游走的值限制在特定的范围内。最后，我们描述了如何生成具有任意概率分布的随机游走，并且能够与玩家充分交互。本书的网站包含了本章所描述的所有的文档和C++源代码。

2.2 Problems with a Basic Random Walk

  简单的随机游走包含一个初始变量 x=x0，之后在游戏中的每个时刻 t，都会从一个正态分布函数上采样一个样本（随机取一个值进行计算）。这个方法是快速而有效的，生成的随机游走将从一个初始值开始，然后每个时刻随机的变化，可能上升，也可能下降。

  这种方法并非没有问题。

  例如，我们如何计算出两天后x的值是多少？ 同样地，玩家在两天前观察到的某个特定的x，这个x的值现在又是什么样的？ 假如玩家两天前刚好拜访过一个星球，又该如何去模拟这个星球的商品价格变化？

  这就是随机游走可能会出现的问题。

2.3 Solving the Extrapolation Problem Using Statistical Methods
  解决外推问题的一种方法是快速模拟随机游走的缺失部分。然而这种方法常受到计算性能的制约，比如在游戏中模拟经济系统，这种需要同时建模大量随机游走模型的时候。

  幸运的是，我们可以使用统计方法，只需要基于两天前最后一次观测到的x值，就可以精确计算出x在之后这两天里的分布情况。具体地说，中心极限定理告诉我们，如果x在时间t0时具有值x0，那么在时间t时，x的分布函数为：

  这是一个正态分布，具有以下两个特征：均值x0，即最后一次观测值；方差（t-t0）σ^2xx，其中（t-t0）是自最后一次观测以来的时间；σ2是一个参数，用于控制随机游走偏离起点的速度。事实上，由于分布是正态的，所以 x 在大约95%的时间里取值范围都是：

  图2.1a显示了使用上述等式生成的随机游走，x0 = 90， σ2 = 1

  图2.1b显示了将σ2的值增加到5会使随机游走变化的更迅速。

  我们可以通过从p(x)中取样来为x选择一个特定的值，虽然这个x在技术上来讲，与用随机游走模拟两天的值不同，但鉴于大多数玩家并不具备相应的数学知识，且真实值和采样值具有相同的统计特性，因此玩家不大可能分辨出差异。

  方程2.1实际上为我们提供了一种比前面提到的简单方法更好的随机游走生成方法。特别是，因为 t-t0 表示连续样本之间的时间，所以我们可以在模拟游戏世界的时间步的同时，以一种恒定的方式更新随机游走；即使不同平台的更新间隔时间不同，随机游走的统计特性也不会发生变化。

  要使用方程2.1生成随机游走，首先为x0选取一个用于p(x)的初始值，接着，从p(x)中采样以获得下一个值x1；然后，可以令x0 = x1，接着从p(x)中采样x2；然后，继续令x1 = x2，从p(x)中采样x3，以此类推。

  在每种情况下，时间间隔应该是随机游走两次观察的间隔，也可以是游戏世界两次更新的间隔，但如果玩家没有注意到这种变化，也可以设置成不规则的。

  方程2.1的一个有趣的特点是，它是时间可逆的，因此生成过去的x跟生成未来的x一样容易。考虑一下，如果玩家第一次访问一个星球，需要查看商品价格的历史记录。公式2.1可用于生成表示历史价格的一系列样本。这与在时间上向前生成样本的方式完全相同，只是x1将被解释为x0之前，x2将被解释为x1之前，依此类推。

  虽然能够在时间上向前和向后推断随机游走是非常有用的，但是我们经常需要做更多的工作。例如，如果玩家观察到一个变量的值，但我们需要确保它在一小时后有其他特定的值，会发生什么情况？

  这种情况时有发生，比如一个规定好一定会出现的事件----比如一场战争后商品价格发生波动，打雷下雨前一定乌云密布。由于我们现在在随机游走中有两个固定点，即最近观测到的值和一个指定的未来值，所以外推方法已经不足以完成这个任务，需要通过内插方程来实现。

2.4 Using Interpolation to Walk toward a Fixed Point

  到现在，我们已经可以从与单个固定值相关联的随机游走中生成样本，而要实现内插方法，只需要将随机游走与两个固定值相关联即可。我们通过计算x相对于每个固定值的概率分布，然后将它们相乘来实现这一点。由于公式2.1表示正态分布，我们可以很容易地写出插值点的概率分布：

  这里x0是第一个指定值，出现在时间t0；xn是第二个指定值，出现在tn；x是任意时刻t的随机游走插值。和以前一样，为了获得x的特定值，我们需要从这个分布中取样。插值x保证在t0时从x0开始，在t0和tn之间随机游走，在时间tn时收敛到xn。

  因此，插值使得在特定时间点精确地确定随机游走的值成为可能，同时使随机游走可以自由地在两者之间游走。

  要使用公式2.2生成一个随机游走值，可以用从p(x)从采样得到的x0和xn去生成x和x1的下一个值。接下来，使用x1代替x0并再次从p（x）中采样以生成x2，依此类推，这可以在时间上向前或向后进行。插值方程具有分形性质，无论插值区间有多小，都会揭示同样多的细节。

  这意味着它可以递归地应用于解决一些问题，比如允许玩家查看某一特定商品的25年历史价格，同时也允许玩家放大任一时间线，来查看微小的价格变动。

2.5 Restricting the Walk to a Fixed Range of Values

  到目前为止，随机游走还有一个潜在的不受欢迎的特征：只要时间t足够长，它可能会便宜到原理起始点的任意一点上。但是在实践中，我们通常希望它的值处在一个合理的范围内。这可以通过添加一个统计约束来实现，它约束x的值在无限长的时间内必须遵循某一特定的概率分布。

  如果我们选择均值x*和方差σ*2的正态分布，则外推方程变成：

插值方程变成：

  根据这些方程式生成的随机游走在大约95%的时间里都被约束在 x*±1.96·sqrt(σ*2) 这个范围内。只有十亿分之一的概率会超过 x*±6.11·sqrt(σ*2)。

  图2.2a显示了根据等式2.3生成的随机游走，其中x* = 90，σ*2 = 100。

  如果十分明确必须将随机游走的值保持在固定边界之间，则最好使用无约束外推和内插方程，并对它们生成的值进行后置处理。如果这是通过判断随机游走的值是否越界来完成的，则随机游走将有一条很重要的统计特征，即其行为对用于生成它的时间步是不变的。要了解这在实际中是如何工作的，我们将生成一个限制在[0,1]区间的随机游走。 

  这可以通过使用无约束外推和内插方程生成一个变量x*来实现，但要向玩家呈现一个x，需要遵守以下规则：

  x将在区间[0,1]内表现出我们需要的随机游走的性质，并且从长期来看将趋向于均匀分布。图2.2b显示了在使用此技术生成的区间[0,1]里面的随机游走。如果我们简单地要求x是非负的，那么取x*的绝对值就足够了；这样做会产生一个总是非负的随机游走，从长远来看，它也会趋向于均匀分布。

2.6 Manipulating and Shaping the Walk with Additive Functions

  到目前为止，我们已经描述了如何使用带有一个或多个不动点的内插方程来操纵随机游走。内插方程保证了随机游走一定会经过我们需要的点，但我们无法控制它在一个区间里的行为----无论它是沿着一条直线，还是沿着一条曲线，或者是多次突然跳跃。有时我们想要的正是这种控制，实现它的一种方法是简单地将随机游走添加到另一个函数中，该函数提供了我们想要的随机游走的基准模型。在这种方式下，随机游走提供了随机性来改变该函数的分布变化。

  假设有一个游戏，游戏里有一个商品的价格为90美分，这个商品的价格在一小时后会涨价到110美分。我们可以简单地使用内插公式，来让随机游走在两个固定价格点之间生成一系列的值，如图2.3a所示。

  或者，我们可以选择另外一个增长曲线符合要求的函数-----从90开始到110结束，并将其添加到由内插方程（起始结束均为0）约束的随机游走模型上。

  例如，我们可能希望价格在固定点之间大致呈线性移动，因此我们将使用线性函数来提供基准模型：

  为了方便起见，这里对t进行了缩放，使其在开始时为0，在结束时为1。通过将被内插方程（起始结束均为0）约束的随机游走添加到该线性函数生成的值x上，就能生成符合要求的增长曲线，如图2.3b。

  当然，我们并不总是需要使用线性函数来提供基本形式。其他有用的函数是阶跃函数，它产生一个突然的跳跃，平滑阶跃函数提供一个平滑的曲线：

和四分之一圆函数，该函数先迅速上升，接着趋于平稳：

基于方程2.6和方程2.7的随机游走如图2.3c和图2.3d。

2.7 Using Additive Functions to Allow for Player Interaction

  我们现在知道如何外推和内插随机游走，并以有趣的方式控制它们，但我们如何使它们相互作用，以便玩家可以影响它们的变化？幸运的是，玩家交互只是随机游走被操纵的另一种方式，因此已经描述的所有技术都可以用来产生玩家交互。

  例如，玩家可能会启动一项研究，该研究将在15分钟内将某个特定武器的基础价格降低25%。该效果可以通过随机游走模拟价格来实现，该随机游走添加了一个加上零均值的表示平均价格的函数，使整个研究过程平均价格下降了25%。这将产生一个随机上下变动的价格，但一旦研究项目完成，通常比开始前低25%。

  类似地，一个玩家如果短时间内大量抛售特定商品，我们可以通过价格的暂时性下降来模拟出供大于求的影响。这可以通过下面两种方法来实现：

• 在人为降低价格后立即记录该行为产生的变化，并通过外推方程来生成未来价格

• 通过从商品价格中减去一个指数衰减函数，用随机游走的随机性来隐藏该函数

  就上面那个研究项目而言，我们必须永久性地记录玩家的行为及其对价格的影响，因为这种影响是永久性的。在供过于求的情况下，这种影响本质上是暂时的，因为指数衰减将确保它最终会变得很小以至于可以忽略不计；在这一点上，游戏选择性的遗忘它，除非玩家在未来的某个时间点上需要用到这个历史价格。 

2.8 Combining Walks to Simulate Dependent Variables

  到目前为止，我们已经讨论了如何生成独立的随机游走，并提供了一些简单的工具来控制和操控它们。

  实际上，我们可能需要生成一些互相关联的随机游走：也许我们需要两个同时上下移动的随机游走，或者一个在另一个下降时上升，反之亦然。通过将随机游走相加和相乘，以及使用虚拟变量，可以很容易地实现这些效果。

  假设我们需要模拟电子零件和机器人产品的价格。由于电子产品是机器人产品的核心组成部分，如果电子产品的价格上涨，我们预计机器人产品的价格会上涨，但这两种价格都不能准确地跟踪彼此的价格。通过使用随机游走对电子产品的价格进行建模，然后使用另一个随机游走对虚拟变量进行建模，该虚拟变量表示电子和机器人产品的价格差异或其比率。

  如果我们决定使用虚拟变量来表示价格之间的差异，我们可以使用x* = 100和σ*2 = 100的随机游走来建模电子产品的价格，使用x* = 25和σ*2 = 100的随机游走来建模电子产品和机器人产品的价格差异。由于机器人产品的价格是这两个随机游走的值之和，所以它也是一个随机游走，它的x* = 125，σ*2 = 200，并且会随着电子产品的价格波动而波动，如图2.4所示：

  随机游走的组合可以变得非常复杂。例如，航天器的价格可以是其各种组件的价格加上表示实际销售价格与组件总成本偏差的虚拟变量值的加权和。

  一般来说，如果一个随机游走是由N个随机均值x1...xN和方差σ*相加，且对应权重为w1...wN，那它可以表示为：

  它可以是玩家可以观察到的总和中所有、部分或全部组件的值。例如，我们可能希望在距离较近的恒星系统中使不同文明的星际商品价格更为相似，一种方法是在每个系统中使用虚拟变量来表示玩家无法观察到的虚拟价格。玩家在任何特定系统中看到的价格将是相邻系统的虚拟价格的加权和，其中较大的权重被分配给较近的系统。

  值得注意的是，如果等式2.8中的一个分量具有负权重，则它产生负相关；也就是说，当其值增加时，它将倾向于减小和的值。当随机游走表示的是两个互相冲突的交战国家时，这种情况是十分有用的。

2.9 Generating Walks with Different Probability Distributions

  如果根据有界外推方程生成随机游走，则在很长一段时间内，它将是一个具有均值x*和方差σ*2的正态分布。对大多数游戏来说这已经足够完美了，但我们有时候希望生成一个具有不同分布的随机游走。

  例如，利用对数正态分布对股票进行建模，我们可以通过将外推函数解释为自然对数函数来生成对数正态分布随机游走，并用指数函数生成实际价格。

  更一般的，逆采样变换方法通常用于，通过应用非线性变换将均匀分布在零和一之间的随机变量，转换为具有特定目标分布的另一个随机变量。例如，以均匀分布在0和1之间的随机变量的自然对数为例，生成一个具有指数分布的随机变量，该指数分布可用于真实地模拟多个随机事件之间的间隔时间。

  尽管本章中描述的随机游走具有正态分布，但可以通过将其强制限制到固定的间隔（如前所述），或使用累积正态分布函数对其进行变换，来使其均匀分布。

  具体来说，如果随机游走的样本x具有均值x*和方差σ*2，我们可以计算变量：

  其中F是累积正态分布函数。变量y将均匀地分布在0和1之间，因此可以与逆变换方法一起用于生成具有广泛分布的随机游走。例如，y的线性变换可用于产生在任意值范围内均匀分布的随机游走，而取自然对数则产生具有指数分布的随机游走。

  需要注意的是，当使用逆变换方法改变随机游动的分布时，随机游走采用的步长将与其值无关。例如，用逆变换方法约束的随机游走分布在0到1的范围内，当其值接近其边界时将比远离边界时采用更小的步长。

2.10 Solving the Persistence Problem with Procedural Generation

  计算机生成的随机游走的核心是一个随机数生成器，它可以通过应用一个种子来生成和复制特定的数字序列。通过记录用于构造随机游走某些部分的种子值，可以在需要时精确地重现这些部分。

  例如，有个玩家第一次拜访一个星球，并查看了过去一年中某个商品的历史价格，那么可以通过将玩家拜访时间当成种子应用到随机数生成器上，然后反向应用外推方程来生成这部分历史价格。如果玩家几个月后回到这个星球上，想要查看这段历史，只要根据相同的种子就能重现，而不需要存储这部分历史数据。

  这性质对大型开放世界游戏十分有用，因为这类游戏往往需要将大量细节和历史信息保存在随机游走模型中。  

2.11 Conclusion

  本章为生成和操作随机游走提供了一些简单而强大的技术。这些技术使利用随机性质和重现随机浮动的值这些方法成为可能，同时还提供必要的控制，以便在需要时使其既是脚本化的，也是交互式的。

  文档和源码中演示了文章中所描述的关键概念，以便使读者可以快速上手，应用于实践。

文章来源：http://www.gameaipro.com/

如有侵犯版权，请联系译者删除。 

翻译不易，读者若需要转载，请注明出处。 

若有错误，欢迎指正。