随机算法在游戏中的应用

概述

游戏无处不随机：发牌、掉落、暴击、抽卡、随机事件。随机用得好，玩法有深度；随机用不好，玩家骂"假随机"或"欧皇游戏"。本文讲解游戏随机三大核心：伪随机 vs 真随机、Fisher-Yates 洗牌算法、概率控制（保底、概率递增、Pseudo Random Distribution）。

---

一、伪随机与真随机

1.1 两种随机

真随机：
  物理熵源产生，不可预测（如硬件噪声）
  代价高、不可复现

伪随机（PRNG）：
  确定性算法 + 种子
  种子相同 → 序列相同
  游戏几乎全部用伪随机

游戏为什么用伪随机：
  可复现（对局回放、测试）
  可控制（种子同步，见帧同步篇）
  速度快、资源友好

1.2 种子与可复现性

种子决定序列：
  Random(seed) → 固定序列
  同种子同序列 → 可回放、可复现测试

游戏应用：
  发牌种子 → 服务器生成，可回溯
  帧同步随机 → 种子同步（已讲）
  Bug 复现 → 记录种子重跑

注意：
  默认 Random 用系统时间播种 → 不可复现
  需要复现时必须显式指定种子

1.3 安全随机

安全场景（不可预测）：
  抽奖防预测、Token、防作弊随机

用 SecureRandom：
  加密级随机，不可预测
  代价高，仅关键场景使用
  普通玩法用 Random 即可

---

二、Fisher-Yates 洗牌

2.1 为什么需要洗牌

发牌/刷出道具需要"随机排列"：
  54 张牌随机发给玩家
  奖池随机排序

朴素做法的问题：
  每次随机取一张，重复标记 → 效率低、易出 bug

Fisher-Yates：
  O(N) 原地洗牌，完美均匀分布

2.2 算法实现

public class Shuffle {

    // 原地洗牌：从后往前，i 与 [0, i] 随机位置交换
    public static <T> void shuffle(List<T> list, Random rand) {
        for (int i = list.size() - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            T tmp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, tmp);
        }
    }
}

算法正确性：
  每个元素等概率出现在任意位置
  遍历 N 次，每次 O(1) → 总 O(N)
  rand.nextInt(i+1) 保证 i 位置与前面任意位交换

使用注意：
  发牌前 shuffle 一次牌组
  洗牌用带种子的 Random（可复现发牌）

2.3 洗牌应用

牌局：发牌 = shuffle + 顺序发牌
奖池：掉落池 shuffle 后按序发放（保底）
随机事件：事件列表 shuffle 后触发
地图生成：预置块 shuffle 排列

---

三、概率控制

3.1 为什么需要控制

纯随机的体验问题：
  暴击率 30% 但可能连续 10 次不爆 → 玩家崩溃
  抽卡概率 1% 可能 1000 抽不出 → 玩家流失
  理论概率 ≠ 玩家体感概率

解法：让"运气"可控
  保底：N 次必出
  概率递增：失败提高下次概率
  PRD：事件分布更均匀

3.2 保底机制

抽卡保底：
  90 抽内必出 SSR（第 90 抽强制）
  实现：记录连续未出次数，达上限强制

掉落保底：
  击杀 N 只必掉稀有
  刷副本 N 次必出装备

实现：
  counter = 连续未出次数
  if (counter >= max) 必定出货 + counter 清零
  else 按概率判定，未出则 counter++

public class PitySystem {

    private final int pityMax;        // 保底次数
    private int counter;              // 连续未出次数

    public boolean roll(double baseRate) {
        counter++;
        if (counter >= pityMax) {
            counter = 0;
            return true; // 保底必出
        }
        if (random() < baseRate) {
            counter = 0;
            return true;
        }
        return false;
    }
}

3.3 概率递增

递增概率（失败增加成功概率）：
  P(n) = base + n × step
  第 n 次成功率随失败次数上升

对比保底：
  保底：硬性保证（体验确定）
  递增：平滑上升（体感温和）

实现：记录失败次数，每失败 step 递增加权

3.4 Pseudo Random Distribution（PRD）

PRD（暴雪公司用于 Dota 等）：
  用修正概率 C 代替名义概率 P
  每次未触发 → 成功率按系数递增
  名义概率 P 与修正概率 C 关系：
    P = C × (1 + ... )（有公式换算）

特点：
  实际期望 = P（统计一致）
  分布更均匀（不会长时间不出/连续爆）
  前期稍低、后期补偿 → 体感"不黑"

简单实现（近似）：
  C 初始 = P / 某系数（经验值）
  第 N 次概率 = C × N
  触发后 N 重置
  名义概率通过试验标定 C

public class Prd {

    private final double c;      // 修正概率（标定值）
    private int attempts = 1;    // 当前尝试次数

    // 判定：第 N 次成功率 = c * N
    public boolean roll() {
        double p = c * attempts;
        boolean hit = random() < p;
        if (hit) {
            attempts = 1; // 触发重置
        } else {
            attempts++;   // 失败累积
        }
        return hit;
    }
}

选型对比：
  保底：最确定，适合重氪抽卡（合规友好）
  递增：温和，适合掉落
  PRD：最"均匀"，适合战斗触发（暴击/眩晕）
  组合：保底 + PRD（抽卡常用）

---

四、随机在游戏中的场景落地

场景	技术	关键点
发牌	Fisher-Yates	种子可复现
抽卡	保底 + 递增	概率表配置
暴击/控制	PRD	均匀分布
掉落	递增 + 保底	期望可控
随机事件	加权随机	权重表
帧同步随机	种子同步	确定性

加权随机（随机事件）：
  事件带权重，按权重占比取
  例：普通 70、稀有 25、传说 5
  实现：累加权重 → rand % 总重 → 定位区间

---

五、随机与合规

抽卡合规（国内）：
  概率公示（公布各档位概率）
  保底说明（规则透明）
  随机日志留存（可审计）
  服务端权威（客户端不能算概率）

工程要求：
  概率表集中配置（策划可调）
  抽卡流水全记录（对账/客服）
  随机结果可追溯（种子 + 记录）

---

六、常见问题

问题	处理
连黑被骂	PRD/递增/保底
概率被破解	安全随机 + 服务端权威
发牌重现难	种子记录
保底重置时机	出货/时间窗口/版本定义清楚
概率表混乱	集中配置 + 版本管理

---

七、小结

随机算法的本质是"可控的运气"：伪随机 + 种子提供可复现性与确定性，是帧同步与测试的基础，安全场景才用 SecureRandom；Fisher-Yates 洗牌以 O(N) 均匀洗牌支撑发牌与奖池；概率控制把纯随机的极端体验拉回可接受范围——保底保证"一定出"，概率递增让"越失败越接近"，PRD 让暴击、控制这类战斗触发分布均匀。配合概率表集中配置、流水留痕与服务端权威，随机既能带来惊喜，又不会透支信任。