游戏开发 · 文章

游戏中的随机数:洗牌、加权随机与伪随机分布

“25% 暴击率,我连续 15 刀都没暴!”——玩家感受到的随机和数学上的随机不是一回事。这一章讲可复现的随机数生成器、正确的洗牌、掉落表,以及让随机“感觉更公平”的伪随机分布。

问题:随机,但要“对的随机”

游戏里的随机数无处不在:暴击、掉落、地图生成、AI 决策、洗牌发牌。但“调用一下 rand()“会带来一连串问题:

  • 无法复现:玩家报告“种子 12345 的地图第三层有 bug”,你却生成不出同一张地图

  • 偷偷有偏:洗牌算法看起来很随机,某些排列的出现概率却明显更高

  • 感觉不公平:数学上完全正确的 25% 暴击,玩家却总觉得“脸黑”

这一章逐个解决。


可复现的随机数生成器

计算机里的随机数几乎都是伪随机:由一个确定的算法从“种子”推导出一串看起来随机的数。同一个种子,永远得到同一串数,这恰恰是游戏需要的特性:程序化地图、录像回放、帧同步联机都依赖它。

为什么不用标准库

rand() 的范围可能只有 0~32767,质量也参差不齐,还是全局状态,多个系统共享时互相干扰。std::mt19937 本身是确定的,但 std::uniform_int_distribution 等分布的实现没有标准化:同一个种子在 MSVC 和 GCC 上可能得到不同结果。需要跨平台复现时,应该自己掌控从生成器到分布的每一步。

本系列使用 PCG32:只有 16 字节状态,速度快,统计质量好,代码不到 20 行:

// PCG32(pcg-random.org):小、快、统计质量好,并且可以用种子精确复现。
// 游戏里需要"同一个种子生成同一张地图""回放录像"时,就不能用 rand() 或 std::random_device
class Pcg32 {
public:
    explicit Pcg32(uint64_t seed = 0x853c49e6748fea9bULL, uint64_t stream = 0xda3e39cb94b95bdbULL) {
        state_ = 0;
        inc_ = (stream << 1u) | 1u;
        next();
        state_ += seed;
        next();
    }

    uint32_t next() {
        uint64_t old = state_;
        state_ = old * 6364136223846793005ULL + inc_;
        auto xorshifted = static_cast<uint32_t>(((old >> 18u) ^ old) >> 27u);
        auto rot = static_cast<uint32_t>(old >> 59u);
        return (xorshifted >> rot) | (xorshifted << ((~rot + 1u) & 31u));
    }

    // [0, bound) 内的均匀整数。直接 next() % bound 会有偏差,这里拒绝掉"凑不满一轮"的那部分
    uint32_t below(uint32_t bound) {
        uint32_t threshold = (~bound + 1u) % bound;  // = 2^32 mod bound
        for (;;) {
            uint32_t r = next();
            if (r >= threshold) return r % bound;
        }
    }

    int range(int lo, int hi) { return lo + static_cast<int>(below(static_cast<uint32_t>(hi - lo + 1))); }  // 闭区间
    float nextFloat() { return static_cast<float>(next() >> 8) * (1.0f / 16777216.0f); }      // [0, 1)
    double nextDouble() { return static_cast<double>(next()) * (1.0 / 4294967296.0); }       // [0, 1)
    bool chance(double p) { return nextDouble() < p; }

private:
    uint64_t state_;
    uint64_t inc_;
};

注意 below 的写法。直接 next() % 6 是有偏的:2³² 不能被 6 整除,余下的那部分会让小的点数多出现一点点。正确的做法是把“凑不满一整轮”的那部分结果丢掉重抽。


洗牌:一个看起来对,其实错的算法

把一副牌打乱,很多人可能会这样写:遍历每一个位置,和任意一个位置进行交换。

// 错误示范:每个位置都和"任意位置"交换。看起来很随机,但 n^n 种执行路径无法均分到 n! 种排列上
template <class T>
void naiveShuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = 0; i < items.size(); ++i) {
        size_t j = rng.below(static_cast<uint32_t>(items.size()));
        std::swap(items[i], items[j]);
    }
}

问题出在计数上:n 张牌,每步有 n 种选择,共 nⁿ 种执行路径,而排列只有 n! 种。6 张牌时是 46656 条路径对应 720 种排列,46656 不能被 720 整除,所以不可能每种排列概率相等。

正确的做法是 Fisher–Yates:从后往前,每个位置只和“它自己或它前面”的元素交换。这样恰好有 n! 条路径,一一对应 n! 种排列:

// Fisher–Yates 洗牌:从后往前,每个位置只和"它自己以及它前面"的元素交换。O(n),且每种排列概率相等
template <class T>
void shuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = items.size(); i > 1; --i) {
        size_t j = rng.below(static_cast<uint32_t>(i));  // j ∈ [0, i-1]
        std::swap(items[i - 1], items[j]);
    }
}

三个标签页:shuffle 对比两种洗牌,热力图显示每张牌(行)落在每个位置(列)的频率;crit 对比独立随机和伪随机分布的暴击;loot 是一个加权掉落表。按“重置”会得到完全相同的随机序列。

在 shuffle 页让演示多跑一会儿(可以把速度调到 8×)。Fisher–Yates 的格子逐渐变成均匀的 16.7%,朴素洗牌却始终保留一条明显的斜纹:第 k 张牌特别容易出现在第 k-1 个位置附近,最大偏差超过 20%。


掉落表:加权随机

“普通 60%、稀有 10%、传说 1%“这类掉落表,标准做法是预先算好权重的前缀和,抽取时生成一个 [0, 总权重) 的随机数,再二分查找它落在哪个区间:

// 加权随机(掉落表):预先算好前缀和,抽取时二分查找,O(log n)
class WeightedTable {
public:
    explicit WeightedTable(const std::vector<double>& weights) {
        double sum = 0;
        for (double w : weights) cumulative_.push_back(sum += w);
    }

    int pick(Pcg32& rng) const {
        double r = rng.nextDouble() * cumulative_.back();
        auto it = std::upper_bound(cumulative_.begin(), cumulative_.end(), r);
        return static_cast<int>(it - cumulative_.begin());
    }

    double probability(int i) const {
        double prev = i == 0 ? 0 : cumulative_[i - 1];
        return (cumulative_[i] - prev) / cumulative_.back();
    }

    int size() const { return static_cast<int>(cumulative_.size()); }

private:
    std::vector<double> cumulative_;
};

预处理 O(n),每次抽取 O(log n)。权重表很大且抽取极其频繁时,可以改用 别名方法(alias method),抽取降到 O(1)。

演示的 loot 页同时显示期望概率(竖线)和实际频率(条形)。抽得越多,二者越接近,这就是大数定律。但在抽取次数少的时候,传说装备的实际频率可能离 1% 很远,这正是玩家抱怨的来源。


如何让随机“感觉公平”?

洗牌袋

如果希望结果“随机但均匀”,例如掉落方块的游戏希望每7个方块里7种形状各出现一次,可以把所有结果装进一个袋子,洗乱之后依次取出,取完再装。

// 洗牌袋:把一组结果装进袋子,打乱后依次取出,取完再重新装。保证每一轮里每种结果恰好出现一次
template <class T>
class ShuffleBag {
public:
    explicit ShuffleBag(std::vector<T> items) : items_(std::move(items)), next_(items_.size()) {}

    const T& next(Pcg32& rng) {
        if (next_ >= items_.size()) {
            shuffle(items_, rng);
            next_ = 0;
        }
        return items_[next_++];
    }

private:
    std::vector<T> items_;
    size_t next_;
};

为随机分布(PRD)

独立随机的 25% 暴击,连续 15 次不暴击的概率是 0.75¹⁵ ≈ 1.3%。一场战斗打几百刀,几乎每局都会遇到一次“长期脸黑”。

伪随机分布(Pseudo-Random Distribution)换了一种规则:第 N 次尝试的触发概率是 N × C,一旦触发,N 归零。刚暴击过的下一刀概率很低,越久没暴击概率越高,到 N × C ≥ 1 时必定触发。适当选取常数 C,长期平均概率仍然是 25%。

C 没有简单的解析解,但“平均概率”随 C 单调递增,可以二分查找:

// 伪随机分布(PRD):第 N 次尝试的触发概率是 N·C,触发后 N 归零。
// 平均概率仍是 p,但"连续不触发"和"连续触发"都变少了
inline double prdAverageProbability(double c) {
    double expectedAttempts = 0;  // 两次触发之间的期望尝试次数
    double notYet = 1;            // 前 n-1 次都没触发的概率
    for (int n = 1; notYet > 0; ++n) {
        double pn = std::min(1.0, n * c);
        expectedAttempts += n * notYet * pn;
        notYet *= 1 - pn;
    }
    return 1 / expectedAttempts;
}

// 由名义概率 p 反求常数 C:平均概率随 C 单调递增,用二分查找
inline double prdConstant(double p) {
    double lo = 0, hi = p;
    for (int i = 0; i < 64; ++i) {
        double mid = (lo + hi) / 2;
        (prdAverageProbability(mid) < p ? lo : hi) = mid;
    }
    return (lo + hi) / 2;
}

class PrdRoll {
public:
    explicit PrdRoll(double p) : c_(prdConstant(p)) {}

    bool roll(Pcg32& rng) {
        ++attempts_;
        if (rng.chance(attempts_ * c_)) {
            attempts_ = 0;
            return true;
        }
        return false;
    }

    double constant() const { return c_; }

private:
    double c_;
    int attempts_ = 0;
};

常用概率对应的 C 值,以及最长可能的连续不触发次数:

名义概率 P

常数 C

最长连续不触发

5%

0.00380

263

10%

0.01475

67

15%

0.03222

31

20%

0.05570

17

25%

0.08474

11

30%

0.11895

8

40%

0.20155

4

50%

0.30210

3

切到演示的 crit 页:两条时间线的暴击率都接近 25%,但独立随机的时间线上有明显的空白和扎堆,PRD 的暴击分布均匀得多。下方直方图中,独立随机的间隔有一条很长的尾巴,PRD 的间隔则集中在 3~6 之间,而且不会超过 12。

PRD 也有代价

PRD 让“连续暴击”变少了,暴击的节奏更可预测。熟练的玩家可以利用这一点,例如先打小兵“攒概率”,再去打英雄。是否使用、用在哪些机制上,是设计决策而不仅是技术决策。


常见陷阱

问题

原因

解决

每次运行结果都一样,或每次都不同

种子固定写死,或每次都用当前时间

种子作为显式参数传入,需要随机时再取时间或系统熵

骰子 1~2 点出现得稍多

next() % n 的取模偏差

用拒绝采样的 below(n)

洗牌结果有偏

和任意位置交换

使用 Fisher–Yates

回放和原局对不上

多个系统共用一个随机数生成器,调用顺序变了

每个系统使用独立的生成器(不同 stream)

nextFloat() 偶尔返回 1.0

用 next() / 4294967295.0 得到闭区间

只取高 24 位再乘以 2⁻²⁴,得到 [0, 1)


游戏中的应用

  • 程序化生成:Roguelike 的种子地图,本质上就是把种子交给 PCG 这类生成器(后续更新)。

  • 帧同步联机:所有客户端用同一个种子、同样的调用顺序,才能得到同样的随机结果。

  • 暴击、闪避、触发类被动:PRD 是 MOBA 和 ARPG 中的常见做法。

  • 抽卡保底:在加权随机之外再加一层“N 次未出必出”的计数器,原理和 PRD 相近。


延伸阅读

版权声明

本文内容版权归作者或相关权利人所有。转载、引用或其他使用请遵循相应授权条款,并保留本文链接。

XuYi,《游戏中的随机数:洗牌、加权随机与伪随机分布》,https://xuyi.dev/2026-11-09-warx1z

Comments

评论

正在加载评论…