Fl0w3r

carpe diem

随机数在游戏中的应用

Posted on In
4.1k 7 mins.

引言

本章讲的主题是随机数在游戏中的应用，主要目的是通过这节课给大家一下随机数的基本概念和游戏中常见的随机策略，介绍随机数生成器，能够指出一些容易用错的地方防止大家出错，还有就是介绍一些随机数使用上的小技巧与随机数分布与应用方面的东西。

基本介绍

在游戏中使用随机数一般是为了增加一些随机性，防止过于重复。

随机数在游戏中的应用

作为游戏玩法的一部分

现在游戏中用到随机数除了增加一些随机性，还有很多方面，比如说玩网游的扔骰子、抽卡、开宝箱这些东西，都是作为游戏玩法的一部分。很多游戏里像龙与地下城 大富翁这种游戏扔骰子本身就是游戏的一部分。

模拟自然现象

许多自然现象中都带有很大的随机性，例如火焰效果在做的时候会做一个叫粒子发射器的东西，用于发射很多像火焰每一片和一些小的火苗和特效这样的东西。这些粒子的运行轨迹、何时发射都带有很大的随机性，由一些随机数来控制。
与此相同的除了火焰还有植被、生物群落等。

离线渲染

离线渲染 光线追踪的做法就是从光源往外发射许多随机方向的射线，当这些射线打中一个物体表面的时候，它才会根据这个物体表面的性质随机决定去反弹还是吸收。经过这样很多次（几千万次）累计叠加，然后最终得到一张效果图像，它可以达到非常高的渲染质量。

随机生成的游戏内容

我的世界 的整个世界都是拿随机数生成的，由一个种子根据一定的随机数算法来生成整个世界。

两种伪随机概念

生成原理上的真随机与伪随机

在电脑里没有真正的随机数。虽然电脑都是确定性的运算，没办法生成一些随机的运算。

  • 真随机 : 需要外部的随机性来源，如利用量子原理或者电路中的噪音来产生随机数。
  • 伪随机 : 用算法生成的”看似”随机的序列，数列本身是固定的，算法确定下来序列一定是一个确定的序列。

实际运用随机数规模控制在2的31-32次方的范围。游戏中可以应用自如，但安全性方面还是不够。

应用层面的真随机与伪随机
  • 真随机 : 每一次几率判断都是独立的。就跟抛硬币一样，前十次抛出正面在抛第十一次的时候正反概率还是50%。
  • 伪随机 : 指同一类的概率事件，彼此之间存在关联性，通常为了保证用户体验。比如连续抽十次卡都抽掉了游戏体验极差。王者荣耀通过幸运值让玩家保底。

游戏中常用随机策略

伪随机策略：保底法

王者荣耀中的买五次必得四到五级铭文。
有些游戏即使不标出来，内部也会有这样的策略在里面，保证玩家不会得到一个太差的游戏体验。

伪随机策略：PRD(Pseudo Random Distribution)

最早在war3及Dota中暴击的算法，在魂斗罗：归来中使用。
如果这次没有抽中，则增加下次抽中的概率：

  • 第N次成功出发的几率为 P(N) = C * N 其中C为初始概率
  • 如果期望是25%的暴击率，则第一次暴击率～8.5%，第二次～17%，第三次～25.5%…
  • 一旦发生暴击则概率重置为～8.5%

触发几率最高的是第三、四次，保证了第一、二次触发几率不会那么高，而到了第十次基本上肯定会发生一次暴击。该算法有效的把暴击分散开，不要太集中。

其它伪随机策略

  • 稀有道具的全服控制
    一种特别稀有特别珍贵的道具，运营方希望它每天产生三个。但如果我通过概率来控制，很有可能出现今天一个人没打出来或者这一天有十几个人都打出来了，这样就不利于运营来控制游戏节奏。后台会增加一个计数器，一开始的时候概率会稍高一点，达到目标数量就会关掉再也不会出了。

  • 洗牌算法
    音乐播放如果现在有十首歌，采取随机的方式播放有可能出现某两首歌连续播放或者是某一首歌很久没出现。洗牌算法就是先把它们的顺序打乱，然后再按打乱之后的顺序来给它播放从而保证每首歌都能听到一遍。

  • 二次随机

    • 第一次抽取决定是几级铭文
    • 第二次抽取决定是具体哪种铭文

随机数生成器

伪随机数生成器

算法 + 种子就能决定随机数的序列。下面介绍几种游戏中常用的算法：

线性同余

  • 递推公式
    $$X_{n+1} = (aX_n + c)\bmod m$$

  • 这个算法非常古老而且实现起来很简单，几乎在稍微老点的语言中内置的算法都是它，每种语言中对参数的使用有着不同的选择。

  • 演示

    m = 9	a = 2	c = 0	seed = 1
    output: 1 - seed
            2 - (1*2+0)mod 9
            4 - (2*2+0)mod 9 
            8 - (4*2+0)mod 9
            7 - (8*2+0)mod 9
                ......

  • 不同参数的比较

    (1) m = 9   a = 2   c = 0   seed = 1
        output: 
        1 - 2 - 4 - 8 - 7 - 5 - 1 ...

    (2) m = 9   a = 2   c = 0   seed = 3
        output: 
        3 - 6 - 3 ...

    (3) m = 9   a = 4   c = 1   seed = 0
        output: 
        0 - 1 - 5 - 3 - 4 - 8 - 6 - 7 - 2 - 0 ...

    这说明m、a、c这三个值的取值非常重要，不能随手取一个。早期项目中为了实现随机数算法时从网络下载源码，为了防止别人猜到规律随意更改了参数，后面发现这样做是不行的，不能随意更改别人给定的参数。

  • 要达到最大周期为m需要的条件：

    • c与m互质
    • a-1可以被m的所有质因数整除
    • 如果m是4的倍数，a-1也必须是4的倍数

  • 要达到良好的随机性，参数c还应该满足：

    • 是质数。
    • 接近 $(\frac{1}{2}-\frac{\sqrt{3}}{6})m$

在上面几个条件的约束下，可用的m、a、c就没有多少个了，所以在使用的时候尽量去找现成的参数，不要自己随便填一个数字进去。

  • 优缺点
    • 实现简单，速度快
    • 所需内存小
    • 用作N维空间的点坐标时，这些点多位于某些超平面上，看起来有些规律，因此不适合于用作蒙特卡洛采样
    • 当m为2的幂时，低阶比特周期较短，可以通过舍弃低位来缓解
梅森旋转

Mersenne是Makoto Mastsumoto（松本）和Takuji Nishimura（西村）于1997年开发的伪随机数产生器：

  • 该算法周期很长，在1～623的维度之间可以均等分布
  • 速度非常快
  • 需要的空间比线性同余算法大（TinyMT 2.5KiB）

随机数种子

给定的种子决定了后续随机数序列，一般程序启动时用当前时间作为种子进行一次初始化。

  • 错误用法

    • 没有调用初始化srand，导致每次启动游戏获得的序列是一样的，失去了随机的意义。
    • 每次调用随机数rand之前都初始化srand，这样得出的结果就会很有一定规律不是特别随机，违背了初衷。

  • 作用

    • 提供每次不一样的游戏体验（用启动时间作为种子）
      • 例如超级马里奥这种游戏每次敌人出现的位置是固定的，玩的次数多了甚至可以背下来，但如果增加一些随机数就可以更有趣味性和挑战性。红白机早期是没办法取到时间的，它的随机数是用一些奇怪的算法加上例如按键的时间长短来实现的
    • 在程序生成内容（Procedural Content Generation,PCG）中使用，用来确保两次计算结果相同
      • 比如用程序生成Minecraft这种地图每次进入是根据同一个种子来生成的，不然每次进入地图都不一样。玩家可以在网站上分享seed，根据该seed会生成相同的世界。
    • 在多人游戏中减小带宽占用（帧同步游戏机制）
      • 两人对战时暴击是随机的，但两边要保证随机出来的值是一样的，所以需要一开始把一方的种子传过去。种子一样，之后的计算步骤保持一致就能保证两端是一样的。
    • 使用非常小的录像文件来实现录像和回放功能（如游戏的录像机制）

  • 帧同步中的随机数
    在使用帧同步的游戏中，要求所有运算步骤严格依序执行

    • 通常会自行实现伪随机数生成器，第三方库无意的调用系统随机数很可能破坏同步状态。
    • 随机数种子需要同步，同步给第三方。

随机数分布与应用

均匀分布

  • VC的rand()函数范围是[0..32767]，如何取得一个[0..9999]的随机整数？
    • x = rand()%10000 分布不均匀（左侧偏大），因为32767不能被10000整除
    • 拒绝采样法
如何取得更大的随机数（0～1000000）
  • x = rand()*(RAND_MAX + 1) + rand()
  • 使用更好的随机数算法，比如梅森旋转
如何取得一个0～1的随机浮点数

  • x = rand()/(float)RAND_MAX
    不可以用x = (rand()%10000)/10000.0f 同样的原因也会导致分布不均匀

  • 针对浮点数的存储格式来生成，随机填充尾数域得[1，2)范围的随机数。
    符号位 - 指数域 - 尾数域(23bit)
    将指数域写死，尾数域用0或1进行填充，最后生成的随机数再减去1就可以得到0到1之间的浮点随机数。

正态分布

在某些时候用于生成更符合自然界规律的随机分布，比如：不同身高的人群、不同高度的树木等。

如何获得符合正态分布的随机数

  • 拒绝采样法
    采样两次分别用作x值和y值，只保留正态分布曲线以下的部分，输出的时候丢弃y值，只输出x值从而保证正态分布。缺点是浪费了太多的样本点。

  • Ziggurat：优化版拒绝采样
    先生成一些符合正态分布且面积相等的矩形，然后对矩形进行随机：如果在正态分布曲线下方则保留；否则再用拒绝采样法来判断一次，最后只保留曲线以下部分。该算法的主要目的是为了减少无效的运算。

  • 逆变换采样
    利用正态分布CDF的反函数做 Inverse transform sampling
    在y轴产生服从(0,1)均匀分布的随机数，水平向右投影到曲线上，然后垂直向下投影到x轴，这样在x轴上就得到了正态分布，拿正态分布的反函数来算。

  • Box-Muller算法
    选取两个服从[0,1]上均匀分布的随机变量 U1、U2，使X、Y满足：

    $X = \cos(2 \pi U_1)\sqrt{-2 \ln U_2}$

    $Y = \sin(2 \pi U_1)\sqrt{-2 \ln U_2}$

    则X与Y服从均值为0，方差为1的高斯分布。

  • 基于中心极限定理采样

    • 生成n个独立同分布的随机变量，求和即可
    • 当n趋近于无穷大时，它们和的分布都会趋近正态分布

形状采样

取得在圆形内均匀分布的点

  • 拒绝采样

  • 根据极坐标采样

    • 错误算法

      x = r * sin(theta)
      y = r * cos(theta)

    • 正确算法

      x = sqrt(r) * sin(theta)
      y = sqrt(r) * cos(theta)
洗牌算法 Fisher-Yates shuffle
  • 选中第1个元素，将其与n个元素中的任意一个交换（包括第1个元素自己）。这时排序后的第1个元素已经确定
  • 选中第2个元素，将其与n-1个元素中作任意一个交换（包括第2个元素自己）。
  • 重复上面步骤，直到剩1个元素为止。

Related Posts