黑神话：索贝尔序列 - 随机敌人生成
深入探讨索贝尔序列实现游戏中低差异分布的随机敌人生成
本文内容基于Unreal Engine 5.6.0
如果我犯了错误，请在下面评论并帮助未来的读者！本文中文翻译由AI机翻，可能不够准确或产生一定的阅读困难。
在 Unreal 中，
Sobol.h中有一个FSobol类，实现了这种拟随机序列供我们直接使用，因此我们不必自己编写矩阵。它还支持格雷码顺序评估。
一切的起源
我在一位优秀开发者的敌人生成器代码中看到了这段代码：Skylake-Official Github，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//Generate the i-th Sobol number in dimension d
float AAFPEnemySpawnerActor::Sobol(uint32 d, uint32 i) {
const uint32 Matrix[8 * 32] = {
2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1,
2147483648, 3221225472, 2684354560, 4026531840, 2281701376, 3422552064, 2852126720, 4278190080, 2155872256, 3233808384, 2694840320, 4042260480, 2290614272, 3435921408, 2863267840, 4294901760, 2147516416, 3221274624, 2684395520, 4026593280, 2281736192, 3422604288, 2852170240, 4278255360, 2155905152, 3233857728, 2694881440, 4042322160, 2290649224, 3435973836, 2863311530, 4294967295,
2147483648, 3221225472, 1610612736, 2415919104, 3892314112, 1543503872, 2382364672, 3305111552, 1753219072, 2629828608, 3999268864, 1435500544, 2154299392, 3231449088, 1626210304, 2421489664, 3900735488, 1556135936, 2388680704, 3314585600, 1751705600, 2627492864, 4008611328, 1431684352, 2147543168, 3221249216, 1610649184, 2415969680, 3892340840, 1543543964, 2382425838, 3305133397,
2147483648, 3221225472, 536870912, 1342177280, 4160749568, 1946157056, 2717908992, 2466250752, 3632267264, 624951296, 1507852288, 3872391168, 2013790208, 3020685312, 2181169152, 3271884800, 546275328, 1363623936, 4226424832, 1977167872, 2693105664, 2437829632, 3689389568, 635137280, 1484783744, 3846176960, 2044723232, 3067084880, 2148008184, 3222012020, 537002146, 1342505107,
2147483648, 1073741824, 536870912, 2952790016, 4160749568, 3690987520, 2046820352, 2634022912, 1518338048, 801112064, 2707423232, 4038066176, 3666345984, 1875116032, 2170683392, 1085997056, 579305472, 3016343552, 4217741312, 3719483392, 2013407232, 2617981952, 1510979072, 755882752, 2726789248, 4090085440, 3680870432, 1840435376, 2147625208, 1074478300, 537900666, 2953698205,
2147483648, 1073741824, 1610612736, 805306368, 2818572288, 335544320, 2113929216, 3472883712, 2290089984, 3829399552, 3059744768, 1127219200, 3089629184, 4199809024, 3567124480, 1891565568, 394297344, 3988799488, 920674304, 4193267712, 2950604800, 3977188352, 3250028032, 129093376, 2231568512, 2963678272, 4281226848, 432124720, 803643432, 1633613396, 2672665246, 3170194367,
2147483648, 3221225472, 2684354560, 3489660928, 1476395008, 2483027968, 1040187392, 3808428032, 3196059648, 599785472, 505413632, 4077912064, 1182269440, 1736704000, 2017853440, 2221342720, 3329785856, 2810494976, 3628507136, 1416089600, 2658719744, 864310272, 3863387648, 3076993792, 553150080, 272922560, 4167467040, 1148698640, 1719673080, 2009075780, 2149644390, 3222291575,
2147483648, 1073741824, 2684354560, 1342177280, 2281701376, 1946157056, 436207616, 2566914048, 2625634304, 3208642560, 2720006144, 2098200576, 111673344, 2354315264, 3464626176, 4027383808, 2886631424, 3770826752, 1691164672, 3357462528, 1993345024, 3752330240, 873073152, 2870150400, 1700563072, 87021376, 1097028000, 1222351248, 1560027592, 2977959924, 23268898, 437609937
};
uint32 result = 0;
uint32 offset = d * 32;
for (uint32 j = 0; i; i >>= 1, j++)
if (i & 1)
result ^= Matrix[j + offset];
return float(result) * (1.0f / float(0xFFFFFFFFU));
}
//Generate 2D sobol coordinates
FVector2D AAFPEnemySpawnerActor::SobolVec2D(uint32 i)
{
float u = Sobol(1, i ^ (i >> 1));
float v = Sobol(2, i ^ (i >> 1));
return FVector2D(u, v);
}
提交信息说这是一个”低差异随机生成器”，可以按照”受控的加权模式”生成敌人。这些魔数来自所谓的”Sobol 序列”，还有一个奇怪的 i ^ (i >> 1) 让我很困扰：
当时我完全不知道这是什么东西。
经过深入研究数学论文、线性反馈移位寄存器（LFSR）、伽罗瓦域和本原多项式，我终于弄明白了。所以这是我尝试向未来的自己（以及任何遇到这个魔法的人）解释它的过程。
第 1 部分：核心问题 - 为什么纯随机很糟糕
假设你想在玩家周围生成 16 个敌人。你有以下选择：
选项 1：纯随机
1
2
3
4
5
for (int i = 0; i < 16; i++) {
float x = RandomFloat(0, 1);
float y = RandomFloat(0, 1);
SpawnEnemy(x, y);
}
问题： 随机数会聚集。你可能会在同一个角落生成 3 个敌人，而其他地方则有大片空白区域。玩家会注意到这一点。这让人感觉不公平，看起来也很糟糕。
选项 2：网格
1
2
3
4
5
for (int i = 0; i < 16; i++) {
float x = (i % 4) / 4.0f;
float y = (i / 4) / 4.0f;
SpawnEnemy(x, y);
}
问题： 太明显了。玩家会立即看出规律。这让人感觉很人工，可预测。
选项 3：Sobol 序列
给你的点：
- 分布均匀（无聚集）
- 看起来随机（无明显规律）
- 是确定性的（可重现，用于回放）
- 有效填充空间
这被称为拟随机或低差异采样。
第 2 部分：基础 - 范德科普特序列（1D）
在处理 2D 问题之前，让我们先了解如何在一条线上均匀分布点。
朴素方法：直接除以计数
点：0.0, 0.0625, 0.125, 0.1875, 0.25, 0.3125…
这会按顺序添加点，总是在开始处聚集。
范德科普特的洞察（1935）：反转位！
1
2
3
4
5
6
7
索引 0: 0000 → 反转 → 0000 → 0.0000 = 0.000
索引 1: 0001 → 反转 → 1000 → 0.1000 = 0.500 (一分为二！)
索引 2: 0010 → 反转 → 0100 → 0.0100 = 0.250 (填充左侧间隙！)
索引 3: 0011 → 反转 → 1100 → 0.1100 = 0.750 (填充右侧间隙！)
索引 4: 0100 → 反转 → 0010 → 0.0010 = 0.125
索引 5: 0101 → 反转 → 1010 → 0.1010 = 0.625
...
这太棒了，真是天才！顺便说一句，以防未来的我忘记了算法，计算浮点数的二进制小数就是 2^(-1)、2^(-2) 等一直到最右边的最低有效位（LSB）的总和
为什么有效：
当你正常计数（0, 1, 2, 3…）时，位从右到左（LSB 到 MSB）变化。当你反转位并将它们视为分数时：
- 最高有效位变成最低有效位（控制 0.5）
- 下一位控制 0.25
- 下一位控制 0.125
这意味着每个新点总是将最大的剩余间隙一分为二。这在 1D 中是可证明最优的！（证明材料在最后的附录中）
第 3 部分：问题 - 扩展到 2D
朴素尝试：对 X 和 Y 都使用位反转
1
2
float x = BitReverse(i);
float y = BitReverse(i); // 同样的函数！
灾难性失败： 所有点都在对角线 y=x 上！
如果 X 和 Y 使用相同的变换，它们就完全相关。你在 2D 空间中得到一条 1D 线。
稍微好一点的尝试：使用不同的位子集
1
2
float x = BitReverse(i & 0xF); // 低 4 位
float y = BitReverse((i >> 4) & 0xF); // 高 4 位
这消除了完全相关性，但仍然会创建可见的模式，因为两个维度都使用相同的简单结构。
我们需要的是： 每个维度必须使用不同的数学结构，并且可证明是独立的。
第 4 部分：Sobol 登场（1967）- 突破
苏联数学家 Ilya Sobol 有一个绝妙的想法：如果我们使用不同的数学配方生成每个维度会怎样？
魔法配方：本原多项式
将本原多项式想象成特殊的数学公式，它们生成具有完美数学结构的”最大随机外观”的位模式。
你不需要理解它们如何工作就可以使用 Sobol 序列（目前） - 只需要知道：
- 每个多项式生成唯一的位模式序列
- 不同的多项式生成不相关的（独立的）序列
- 有数千个这样的多项式可用
例如：
- 维度 1（X）： 使用配方 #1（x⁵ + x² + 1）
- 维度 2（Y）： 使用配方 #2（x⁵ + x⁴ + x³ + x² + 1）
- 维度 3（Z）： 使用配方 #3（x⁵ + x⁴ + x² + x + 1）
- 等等
每个”配方”产生不同的数字模式，当组合时，在多维空间中创建均匀分布的点。
想了解这些配方如何工作？ 请参阅第 11 部分，了解本原多项式和 LFSR 的完整技术解释。现在，只需相信它们有效！
第 5 部分：格雷码 - 缺失的拼图
再看一下代码：
1
float u = Sobol(1, i ^ (i >> 1)); // 这是什么？
这个 i ^ (i >> 1) 就是格雷码。
什么是格雷码？
一种重新排序整数的方法，使得连续的数字只相差一位：
1
2
3
4
5
6
7
8
9
常规： 格雷码：
0 → 0000 (0)
1 → 0001 (1) ← 只有第 0 位变化
2 → 0011 (3) ← 只有第 1 位变化
3 → 0010 (2) ← 只有第 0 位变化
4 → 0110 (6) ← 只有第 2 位变化
5 → 0111 (7) ← 只有第 0 位变化
6 → 0101 (5) ← 只有第 1 位变化
7 → 0100 (4) ← 只有第 0 位变化
为什么 Sobol 需要这个？
因为每次位翻转对应于添加或删除一个方向向量。这创建了一个结构化的”在空间中行走”，其中每一步都恰好改变一个预先计算的量。
没有格雷码，多个位会同时改变，导致大的不可预测的跳跃。
第 6 部分：算法 - 逐步解析
让我们追踪调用 SobolVec2D(2) 时实际发生的事情：
步骤 1：将索引转换为格雷码
1
2
i = 2
Gray = 2 ^ (2 >> 1) = 2 ^ 1 = 3（二进制：0011）
步骤 2：检查哪些位被设置
1
2
Gray = 0011
位 0 和 1 被设置
步骤 3：对相应的方向数进行异或运算（XOR）
对于维度 1：
1
2
3
4
5
6
7
Direction[0] = 2147483648 (二进制：10000000000000000000000000000000)
Direction[1] = 3221225472 (二进制：11000000000000000000000000000000)
result = Direction[0] XOR Direction[1]
= 10000000000000000000000000000000
XOR 11000000000000000000000000000000
= 01000000000000000000000000000000
步骤 4：归一化到 [0, 1]
1
u = 1073741824 / 4294967295 = 0.25
步骤 5：对维度 2 重复（使用不同的方向数）
1
v = 0.25（这个例子中恰好相同）
结果
点 (0.25, 0.25)
关键洞察： 格雷码告诉你选择哪些方向数，然后你按位对它们进行异或运算以获得坐标。
第 7 部分：为什么是 XOR？（自逆性质）
XOR 有一个神奇的性质：它是自己的逆运算
1
A XOR B XOR B = A
这意味着：
- 对某物进行 XOR 可以添加它
- 再次对它进行 XOR 可以删除它（同样的操作！）
与加法比较：
1
A + B - B = A (需要不同的操作)
为什么这对 Sobol 很重要：
当格雷码将一位从 1→0 翻转时，我们需要”删除”那个方向向量。使用 XOR，我们只需… 再次 XOR 它。添加和删除使用相同的操作！
1
2
3
步骤 1：Gray = 001 → XOR Direction[0] → result = 10000000
步骤 2：Gray = 011 → XOR Direction[1] → result = 11000000 (添加)
步骤 3：Gray = 010 → XOR Direction[0] → result = 01000000 (删除！)
这就是为什么格雷码 + XOR 是完美的配对：
- 格雷码： “一次改变一件事”
- XOR： “添加和删除使用相同的操作”
一起：增量式、可逆、结构化的导航。
第 8 部分：历史背景
这些魔法不是凭空出现的：
- 1935 - 范德科普特： 1D 的位反转
- → 可证明最优的 1D 分布
- 1960 - Halton： 使用不同的质数基扩展到多维
- → 有效，但维度之间存在相关性问题
- 1967 - Sobol： 使用本原多项式而不是质数
- → 每个维度获得数学上独立的结构
- → 这是突破
Sobol 没有发现本原多项式（自 1800 年代以来就用于纠错码）。他没有发明格雷码（自 1950 年代以来就用于轴编码器）。他以新颖的方式结合了现有的数学工具。
魔法不在于单个部分。它在于认识到：
- 本原多项式生成独立的位模式
- 格雷码实现增量更新
- XOR 实现可逆操作
- 它们一起创建了可证明的低差异序列
第 9 部分：游戏开发者的实用技巧
何时使用 Sobol 序列：
适用于：
- 敌人生成（如原始代码中）
- 粒子系统发射点
- 程序纹理采样
- 蒙特卡罗渲染
- 任何需要”随机但均匀分布”点的时候
不适用于：
- 简单的随机事件（抛硬币、掷骰子）
- 当需要聚集时
- 高频更新（计算成本很重要）
实现说明：
Matrix 值是常量： 它们几十年前就使用本原多项式预先计算了。你可以从参考实现（如顶部的代码）中复制它们。（或者直接调用Unreal的FSobol）
维度限制： 硬编码的 Matrix 通常支持 8-10 个维度。要更多，你需要生成额外的方向数。
索引很重要： 始终按顺序递增索引（0, 1, 2, 3…）。不要跳过，否则你会失去低差异特性，因为前置位的结果会成为下一个步进的输入。
重置： 如果重新开始生成，从索引 0 重新开始。序列是确定性的。
常见陷阱：
1
2
3
4
5
6
7
8
9
// 错误 - 相同的索引产生相同的点
for (int i = 0; i < count; i++) {
Spawn(SobolVec2D(0)); // 总是 (0,0)！
}
// 正确 - 递增索引
for (int i = 0; i < count; i++) {
Spawn(SobolVec2D(i));
}
1
2
3
4
5
// 错误 - 随机索引破坏序列
for (int i = 0; i < count; i++) {
int randomIndex = rand();
Spawn(SobolVec2D(randomIndex)); // 只是随机，不是拟随机！
}
深入探讨部分 - 给好奇者
下面的部分深入探讨 Sobol 序列背后的数学机制。如果你只是想有效地使用它们，可以跳到结论。
对于那些想了解为什么这有效以及如何生成魔数的人，请继续阅读！
第 11 部分：本原多项式和 LFSR - 数学机制
还记得第 4 部分中我们说每个维度使用不同的”数学配方”（本原多项式）吗？现在让我们了解这些配方到底是什么以及它们如何工作。
什么是本原多项式？
GF(2) = “2 阶伽罗瓦域” = “二进制算术中加法是 XOR (算术乘法是 AND)”的花哨术语
1
2
3
4
5
0 + 0 = 0
0 + 1 = 1
1 + 1 = 0（因为 XOR）
0 × 1 = 0（AND）
1 × 1 = 1（AND）
本原多项式 = 一个特殊的多项式，在二进制算术中生成最大长度序列。
把它想象成创建”看起来最随机”的位模式的配方，实际上具有深刻的数学结构。
例子：x³ + x + 1
这是一个本原多项式。当你在线性反馈移位寄存器（LFSR）中使用它时，它会循环遍历所有 7 个可能的 3 位状态（不包括 000）：
1
001 → 100 → 010 → 101 → 110 → 111 → 011 → (重复)
那是 2³ - 1 = 7 个状态。最大可能！
LFSR 实际如何工作？
LFSR（线性反馈移位寄存器） 是一个移位寄存器，其输入位是其先前状态的线性函数。把它想象成一排位：
- 每个时钟周期移位一个位置
- 通过对特定位置进行 XOR 来反馈计算新位
对于本原多项式 x³ + x + 1，这是 LFSR 电路：
1
2
3
4
5
6
7
8
9
┌────────────────────────────┐
│ │
│ ┌───┐ ┌───┐ ┌───┐ │
└─►│ S₂│─►│ S₁│─►│ S₀│──────►│ 输出
└───┘ └─┬─┘ └─┬─┘ │
│ │ │
└──XOR─┘ │
│ │
└────────────┘
组件：
- S₂, S₁, S₀ = 三个 1 位存储单元（”寄存器”）
- 抽头在位置 1 和 0（S₁ 和 S₀），由多项式系数 x¹ 和 x⁰ 确定
- 反馈 = S₁ ⊕ S₀
多项式 → 抽头位置：
多项式 x³ + x + 1 告诉我们：
- x³ → 阶数 3，所以我们需要 3 位
- x¹ → 在位置 1 抽头（从右边开始，从 0 计数）
- x⁰（+1） → 在位置 0 抽头
抽头规则： 对位置 1 和 0 进行 XOR，反馈到最左边的位置
逐步：生成序列
让我们从状态 001 开始追踪：
1
初始状态：[S₂ S₁ S₀] = [0 0 1]
时钟周期 1：
1
2
3
4
5
6
7
8
9
10
11
12
当前状态：[0 0 1]
反馈计算：
new_bit = S₁ ⊕ S₀ (在 x¹ 和 x⁰ 处抽头)
= 0 ⊕ 1
= 1
右移 + 插入反馈：
[0 0 1] → 移位 → [? 0 0]
→ 插入 1 → [1 0 0]
下一个状态：[1 0 0]
时钟周期 2：
1
2
3
4
5
6
当前状态：[1 0 0]
反馈：
new_bit = S₁ ⊕ S₀ = 0 ⊕ 0 = 0
下一个状态：[0 1 0]
时钟周期 3： [0 1 0] → 反馈 = 1 ⊕ 0 = 1 → [1 0 1]
时钟周期 4： [1 0 1] → 反馈 = 0 ⊕ 1 = 1 → [1 1 0]
时钟周期 5： [1 1 0] → 反馈 = 1 ⊕ 0 = 1 → [1 1 1]
时钟周期 6： [1 1 1] → 反馈 = 1 ⊕ 1 = 0 → [0 1 1]
时钟周期 7： [0 1 1] → 反馈 = 1 ⊕ 1 = 0 → [0 0 1] ← 回到开始！
完整周期
1
001 → 100 → 010 → 101 → 110 → 111 → 011 → (001) ...
那正好是 7 个状态 = 2³ - 1 = 所有可能的非零 3 位状态！
为什么排除 000？ 因为 000 ⊕ 000 = 000 永远。全零状态是一个”死状态”，永远无法逃脱。
为什么本原多项式是特殊的
关键性质： 本原多项式生成最大长度序列（m 序列）。
对于阶数 n：
- 总可能状态：2^n
- 非零状态：2^n - 1（不包括全零）
- 本原多项式在重复之前循环遍历所有 2^n - 1 个状态
为什么 x³ + x + 1 是本原的：
- 它是不可约的（不能在 GF(2) 上分解）
- 周期恰好是 2³ - 1 = 7（我们刚刚证明了这一点！）
- 它满足数学测试：它除 x^7 - 1 但不除任何更小的 x^k - 1
为什么 x⁴ + 1 不是本原的？
因为它可以分解：x⁴ + 1 = (x + 1)⁴ 在 GF(2) 中
因为它有因子，所以不能生成最大长度序列。让我们看看实际会发生什么：
x⁴ + 1 的 LFSR：
1
2
3
4
5
6
只在位置 0 抽头（因为 x⁴ + x⁰）
状态：[S₃ S₂ S₁ S₀]
反馈 = S₀（只是复制最后一位！）
从 0001 开始：
0001 → 1000 → 0100 → 0010 → 0001 (周期 = 4，不是 15！)
它只循环遍历 4 个状态，不是最大 15 = 2⁴ - 1。这就是为什么它不是本原的 - 它不能到达所有可能的状态。
左移 vs 右移：方向重要吗？
简短回答： 不重要！方向无关紧要 - 你只是以相反的顺序遍历相同的周期。
x⁴ + x + 1 的例子：
右移 LFSR：
1
2
0001 → 1000 → 0100 → 0010 → 1001 → 1100 → 0110 → 1011
→ 0101 → 1010 → 1101 → 1110 → 1111 → 0111 → 0011 → (0001)
左移 LFSR（相同的多项式，相反的方向）：
1
2
0001 → 0011 → 0111 → 1111 → 1110 → 1101 → 1010 → 0101
→ 1011 → 0110 → 1100 → 1001 → 0010 → 0100 → 1000 → (0001)
注意：相同的 15 个状态，只是顺序相反！
方向的选择纯粹是一个约定。不同的实现偏好不同的方向：
- 右移： 在数字设计教科书中更常见
- 左移： 在软件实现中经常使用（位移操作感觉更自然）
两者都到达所有 15 个状态，并且具有完全相同的周期。你只是绕着同一个循环走，只是顺时针和逆时针。
二进制空间 vs 十进制空间：秩序 vs 混沌
这就是有趣的地方！让我们看看 x⁴ + x + 1 序列的十进制值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
二进制 十进制
0001 → 1
1000 → 8
0100 → 4
0010 → 2
1001 → 9
1100 → 12
0110 → 6
1011 → 11
0101 → 5
1010 → 10
1101 → 13
1110 → 14
1111 → 15
0111 → 7
0011 → 3
在十进制中： 1, 8, 4, 2, 9, 12, 6, 11, 5, 10, 13, 14, 15, 7, 3
这看起来完全随机！没有明显的模式。
但在二进制空间中？ LFSR 正在执行非常结构化的行走：
- 每一步都翻转一个或两个特定的位（基于 XOR 反馈）
- 位模式最大程度地分散
- 序列系统地探索整个二进制状态空间
为什么这对 Sobol 序列很重要
这是 Sobol 序列背后的关键洞察：
- 在二进制空间中： LFSR 生成高度结构化、均匀分布的位模式
- 在十进制/几何空间中： 这些模式看起来随机且分布良好
- 投影到 [0,1]： 方向数（缩放的 LFSR 输出）创建低差异序列
所以当你使用 Sobol 生成敌人时：
- 数学看到： 32D 二进制超立方体中精心编排的行走
- 玩家看到： “随机”但分布良好的敌人位置
- 开发者看到： 只是有效的魔数™
十进制空间中的混沌实际上是一个特征，而不是错误 - 这就是使点看起来随机，同时在底层保持完美数学结构的原因！
第 10 部分：超立方体视角（令人费解的部分）
这就是变得奇怪的地方，但请坚持下去。
XOR 没有几何意义
当你对两个数字进行 XOR 时，你不是在添加向量。你不是在空间中移动。你是在 32 维二进制空间中操作，其中每一位都是一个单独的轴。
1
10000000 XOR 10100000 = 00100000
这不是”组合这些方向”。它是”在 32D 超立方体中翻转特定的位开/关”。
投影技巧
- 你导航一个 32D 二进制超立方体（一次沿一个轴走一步，感谢格雷码）
- 超立方体中的每个位置都是一个 32 位整数
- 你通过除以 2³² - 1 将其投影到 [0, 1]
- 这种投影，令人惊讶地，产生均匀分布的点
为什么这有效？
本原多项式确保当你在 32D 超立方体中行走时，投影的 1D 坐标系统地探索整个 [0, 1] 区间，没有聚集或模式。
这就像 3D 螺旋投影到 2D 时看起来随机，但它实际上在 3D 中是完全结构化的。同样的想法，但 32D → 1D。
“方向数”这个误称
它们不是几何方向。它们是 32D 二进制空间中的位模式。这个术语被保留下来是因为它听起来直观，但在技术上是不准确的。
第 12 部分：综合 - 所有部分如何组合在一起
现在我们已经探索了 LFSR、本原多项式和超立方体视角，这是所有东西如何连接的：
完整图景
在表面上（第 6 部分）：
- 格雷码告诉你要对哪些方向数进行 XOR
- 每个维度使用不同的方向数
- 结果归一化到 [0, 1]
在引擎盖下（第 11-10 部分）：
- 方向数来自通过 LFSR 的本原多项式
- 每个多项式在 GF(2) 中生成最大长度序列
- 不同的多项式 = 不相关的序列 = 独立的维度
- 你在 32D 二进制超立方体中行走，一次翻转一位
- 从超立方体 → [0,1] 的投影创建低差异特性
关键洞察
不要从几何上思考。 从组合的角度思考：
你不是”在空间中移动” - 你是选择和组合预先计算的位模式。[0,1] 中的均匀分布是以下因素的涌现特性：
- 最大长度序列（来自本原多项式）
- 单位转换（来自格雷码）
- 可逆组合（来自 XOR）
“魔法”在于这种数学结构，当投影到连续空间时，产生可证明最优的点分布。
为什么这对游戏开发很重要
理解这一点让你可以：
- 自信地调试： 知道为什么改变索引顺序会破坏一切
- 正确扩展： 使用 Joe & Kuo 多项式生成你自己的维度
- 智能优化： 缓存格雷码转换，预先计算 XOR
- 清晰解释： “这不是随机的，它是通过二进制空间的确定性行走”
第 13 部分：揭开魔法矩阵的神秘面纱 - 这些数字从哪里来？
你可能会想：”好的，我理解如何使用 Matrix，但这些特定的数字从哪里来？有人只是编造它们吗？”
不！它们是使用递推关系从本原多项式系统地生成的。让我展示给你看。
Bratley-Fox 算法（1988）
这是生成 Sobol 方向数的标准算法：
1
2
输入：阶数为 s 的本原多项式，系数为 a
输出：一个维度的方向数
步骤 1：初始化前 s 个方向整数
这些被称为 m[1]、m[2]、…、m[s]，必须是：
- 奇数
m[i] < 2^i
简单初始化：只使用全 1
1
2
3
4
m[1] = 1
m[2] = 1
m[3] = 1
...
（生产实现使用更复杂的值以获得更好的分布）
步骤 2：应用递推关系
对于具有二进制表示 a 的本原多项式，计算剩余值：
1
m[i] = 2*a₁*m[i-1] ⊕ 4*a₂*m[i-2] ⊕ ... ⊕ 2^s*m[i-s] ⊕ m[i-s]
其中 ⊕ 是 XOR，aⱼ 是 a 的第 j 位。
步骤 3：转换为方向数
方向数是：
1
v[i] = m[i] * 2^(32-i)
这将 m[i] 移位到占据 32 位整数的最高有效位。
具体例子：x³ + x + 1
让我们为本原多项式 x³ + x + 1 生成方向数：
设置：
- 阶数
s = 3 - 二进制表示：
a = 1011（x³、x²、x¹、x⁰ 的位） - 系数：a₂ = 0（无 x² 项），a₁ = 1（有 x¹ 项）
步骤 1：初始化
1
2
3
m[1] = 1
m[2] = 1
m[3] = 1
步骤 2：对 m[4] 应用递推关系
对于 x³ + x + 1（系数：a₂=0, a₁=1）：
1
2
3
4
m[4] = 2*1*m[3] ⊕ 4*0*m[2] ⊕ 8*m[1] ⊕ m[1]
= 2*1 ⊕ 0 ⊕ 8*1 ⊕ 1
= 2 ⊕ 8 ⊕ 1
= 11
继续（注意：a₂=0，所以 4*a₂*m[i-2] 项等于 0，可以省略）：
1
2
3
4
m[5] = 2*1*m[4] ⊕ 4*0*m[3] ⊕ 8*m[2] ⊕ m[2] = 22 ⊕ 0 ⊕ 8 ⊕ 1 = 31
m[6] = 2*1*m[5] ⊕ 4*0*m[4] ⊕ 8*m[3] ⊕ m[3] = 62 ⊕ 0 ⊕ 8 ⊕ 1 = 55
m[7] = 2*1*m[6] ⊕ 4*0*m[5] ⊕ 8*m[4] ⊕ m[4] = 110 ⊕ 0 ⊕ 88 ⊕ 11 = 61
...
步骤 3：转换为方向数
1
2
3
4
5
v[0] = m[1] << 31 = 1 << 31 = 2147483648 = 0b10000000000000000000000000000000
v[1] = m[2] << 30 = 1 << 30 = 1073741824 = 0b01000000000000000000000000000000
v[2] = m[3] << 29 = 1 << 29 = 536870912 = 0b00100000000000000000000000000000
v[3] = m[4] << 28 = 11 << 28 = 2952790016
...
这些就是你的方向数！
不同的多项式 = 不同的维度
Sobol 多维独立性的关键是对每个维度使用不同的本原多项式：
| 维度 | 多项式 | 二进制表示 |
|---|---|---|
| 0 | x² + x + 1 | 0b111 |
| 1 | x³ + x + 1 | 0b1011 |
| 2 | x⁴ + x + 1 | 0b10011 |
| 3 | x⁵ + x² + 1 | 0b100101 |
| 4 | x⁶ + x + 1 | 0b1000011 |
| … | … | … |
每个多项式通过递推关系生成自己的方向数集。这些集合在数学上是独立的，确保维度之间没有相关性。
为什么要预先计算？
方向数是：
- 确定性的 - 相同的多项式总是给出相同的数字
- 生成成本高 - 需要仔细实现
- 重复使用 - 每个 Sobol 样本都访问它们
所以它们计算一次（离线，几十年前）并硬编码为常量。你代码中的 Matrix 是为 8 个维度运行此算法的结果，每个 32 位。
生成你自己的 Matrix
如果你需要更多维度或想验证数字，这是简化的 Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def generate_sobol_direction_numbers(s, a, num_bits=32):
"""
生成 Sobol 方向数。
参数：
s: 本原多项式的阶数
a: 系数作为二进制数（例如，x^3+x+1 为 0b101）
num_bits: 生成多少个方向数
"""
m = [0] * (num_bits + 1) # 1-indexed
# 初始化前 s 个值（通常全为 1）
for i in range(1, s + 1):
m[i] = 1
# 递推关系
for i in range(s + 1, num_bits + 1):
m[i] = m[i - s]
for j in range(1, s):
if a & (1 << (s - 1 - j)):
m[i] ^= (1 << j) * m[i - j]
m[i] ^= (1 << s) * m[i - s]
# 转换为方向数
return [m[i] << (32 - i) for i in range(1, num_bits + 1)]
生产 vs 简单实现
重要警告： 上面的简化算法使用 m[i] = 1 进行初始化。生产实现（如你游戏代码中的那个）使用精心选择的初始值，提供更好的低差异特性。
Matrix 中的”魔法”不仅仅是递推关系 - 它也是由数学家优化的特定初始化值。这些值发表在论文中（Bratley & Fox 1988，Joe & Kuo 2008）并被广泛重用。
在哪里获得官方值
除非你知道自己在做什么，否则不要生成自己的！使用已发布的表：
- Joe & Kuo 数据库： 标准参考，最多 21,201 个维度
-
Numerical Recipes： 包含常见维度的表
- 开源实现：
- GSL（GNU Scientific Library）
scipy.stats.qmc.Sobol（Python）- 各种 C++ 库
结论
那些”魔数”根本不是魔法。它们是：
- 通过递推关系从本原多项式生成的
- 用精心选择的初始值优化的
- 由研究人员预先计算和发布的
- 在所有实现中用作常量
你站在几十年数学研究的肩膀上。你代码中的 Matrix 代表了 1960 年代至 2000 年代数学家数百小时的优化和验证工作。
自信地使用它 - 但也要尊重那些看似随机的数字背后的复杂性！
第 14 部分：数学基础
在本节内容中，我的数学知识已经不足以验证以下证明，整个推导由 AI 起草，因此我强烈建议对此持保留态度，并通过适当的数学来源进行验证。我仍然将其包含在这里以供参考，万一未来的我获得所需的足以验证它的数学知识呢。
如果你想要正式的数学证明，说明为什么范德科普特和 Sobol 序列如此有效，这是差异理论的基础。
1. 基数反转函数（正式定义）
范德科普特序列正式使用基数反转函数 φ_b(n) 定义：
对于具有 b 进制表示的整数 n：
1
n = Σ(i=0 to k) aᵢ · bⁱ 其中 0 ≤ aᵢ < b
基数反转是：
1
φ_b(n) = Σ(i=0 to k) aᵢ · b⁽⁻ⁱ⁻¹⁾
对于二进制（b=2），这正好是位反转：
1
2
n = aₖ·2ᵏ + aₖ₋₁·2ᵏ⁻¹ + ... + a₁·2 + a₀
φ₂(n) = a₀·2⁻¹ + a₁·2⁻² + ... + aₖ·2⁻⁽ᵏ⁺¹⁾
2. 差异 - 正式度量
星差异 D*_N 衡量 N 个点分布的均匀程度：
1
D*_N = sup_{0≤x≤1} |A([0,x), N)/N - x|
其中：
- A([0,x), N) = [0, x) 中的点数
- x = 如果完全均匀的预期比例
下界（已证明）： 对于任何序列，D*_N ≥ C·log(N)/N
这是理论最小值 - 你不能做得比 O(log N / N) 更好。
3. 范德科普特达到最优差异
定理（范德科普特，1935）：
对于基数为 b 的范德科普特序列：
1
D*_N ≤ (1/2 + (b-1)/(2b)) · log_b(N)/N + O(1/N)
对于二进制（b=2）：
1
D*_N ≤ (3/4) · log₂(N)/N + O(1/N)
这渐近地匹配下界 → 可证明最优！
4. 为什么特别是位反转？
证明依赖于分析二进制区间中的分布 [k/2^m, (k+1)/2^m)。
关键引理： 对于范德科普特序列，在任何长度为 2^(-m) 的二进制区间中：
- 预期点：N/2^m
- 实际点：最多相差 O(log N)
为什么？ 因为：
- 位位置 i 控制 2^(-i) 尺度的细分
- 当位 i 翻转时，它向分数添加/删除 2^(-i-1)
- 这对应于在该尺度上细分
- 位以分层顺序翻转
- 位 0 每步翻转 → 最细细分
- 位 k 每 2^k 步翻转 → 最粗细分
- 反转创建分层
- 反转映射：”翻转频率” → “细分尺度”
- 低频率（粗）翻转控制大跳跃（0.5）
- 高频率（细）翻转控制小跳跃（2^(-k)）
正式陈述：
对于范德科普特生成的 N 个点，二进制区间 [k·2^(-m), (k+1)·2^(-m)) 中的点数是：
1
A_{m,k} = N/2^m ± O(log N)
O(log N) 误差是不可避免的（由下界证明），但范德科普特达到了这个界。
5. 证明草图
定理： 范德科普特序列的差异 D*_N = O(log N / N)。
证明大纲：
- 将 [0,1) 划分为 2^(-m) 尺度的二进制区间：
1
I_k = [k/2^m, (k+1)/2^m) 对于 k = 0, 1, ..., 2^m - 1
- 计算每个区间中的点：
- 具有 N 个点的范德科普特：每个区间获得 N/2^m ± ε 个点
- ε 误差来自边界效应
- 关键洞察： 当你在范德科普特中生成点 n 时：
- 它在 2 进制中的位置是：n = Σ aᵢ·2ⁱ
- 反转的位置是：φ₂(n) = Σ aᵢ·2⁽⁻ⁱ⁻¹⁾
- 系数 aᵢ 确定在 2^(-i) 尺度上的哪个二进制子区间
- 计数论证：
- 点 0 到 2^m - 1 在 2^(-m) 尺度上恰好击中每个二进制区间一次
- 点 2^m 到 2^(m+1) - 1 再次击中每个区间
- 对于一般 N，”余数”点最多导致 log(N) 误差
- 界定差异：
1 2 3 4 5 6
对于任何 x ∈ [0,1)，选择二进制近似 k/2^m，使 |x - k/2^m| < 2^(-m) |A([0,x), N)/N - x| ≤ |A([0, k/2^m), N)/N - k/2^m| + 2^(-m) ≤ O(log N / N) + 1/2^m 选择 m = log₂(N) → 差异 = O(log N / N) - 最优性： 匹配下界 → 不能做得更好！
关键数学洞察
位反转有效的原因不是几何的 - 它是数论的：
b 进制数字反转在 b 进制二进制有理数中创建模 1 的等分布。
更正式地说：
序列 {φ_b(n)} 在 [0,1) 中是等分布的，差异受每个尺度上数字贡献总和的限制，按 base^(-position) 加权。
分层位翻转确保：
- 在探索细尺度（小位）之前探索粗尺度（大位）
- 每个尺度都对差异界贡献加法
- 总差异总和为 O(log N / N)
在哪里找到完整证明
完整的严格证明使用：
- Weyl 的等分布准则（傅里叶分析方法）
- Erdős-Turán 不等式（将等分布转换为差异界）
- 二进制分区论证（组合计数）
请参阅下面的参考资料部分以获取详细来源。
TL;DR： 数学证明是差异理论。范德科普特证明位反转序列达到 O(log N / N) 的理论最小差异，这被证明是无法打败的。”间隙分裂”的直觉是正确的，但正式证明使用测度论和基数 2 表示的数论性质。
结论
Sobol 序列是那些”易于使用，难以理解”的算法之一。实现只有约 10 行代码，但底层的数学机制很深。
你不需要理解伽罗瓦域或本原多项式就可以使用 Sobol 序列。但如果你像我一样，不能忍受在不理解的情况下使用”魔法”，希望这有所帮助。
关键要点：
- 拟随机 ≠ 随机 - 它是看起来随机的结构化采样
- 格雷码 + XOR 是增量更新的完美配对
- 本原多项式 在维度之间提供数学独立性
- 在超立方体中思考， 而不是几何空间
- Matrix 值是预先计算的 - 你只是查找它们并进行 XOR
现在去生成一些均匀分布的敌人吧！
参考文献和进一步阅读
主要来源
- Weyl, H. (1916). “Ueber die Gleichverteilung von Zahlen mod. Eins”（”关于模 1 的数字均匀分布”）。Mathematische Annalen，77(3)，313-352。
- 关于等分布理论的基础论文
- van der Corput, J.G. (1935). “Verteilungsfunktionen I-II。” Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen，38，813-821，1058-1066。
- 引入了基数反转函数和位反转序列
- Halton, J.H. (1960). “关于评估多维积分时某些拟随机点序列的效率。” Numerische Mathematik，2，84-90。
- 使用不同的质数基将范德科普特扩展到多维
- Sobol, I.M. (1967). “立方体中点的分布和积分的近似评估”（俄语）。Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki，7，784-802。
- 英文翻译：USSR Computational Mathematics and Mathematical Physics，7，86-112。
- 引入基于本原多项式序列的突破性论文
- Bratley, P. and Fox, B.L. (1988). “算法 659：实现 Sobol 的拟随机序列生成器。” ACM Transactions on Mathematical Software，14(1)，88-100。
- 生成最多 40 个维度的 Sobol 方向数的标准算法
- Joe, S. and Kuo, F.Y. (2008). “用更好的二维投影构造 Sobol 序列。” SIAM Journal on Scientific Computing，30，2635-2654。
- 将 Sobol 序列扩展到 21,201 个维度的综合数据库
- 可在以下地址获得：https://web.maths.unsw.edu.au/~fkuo/sobol/
教科书和综合参考
- Kuipers, L. and Niederreiter, H. (1974). 序列的均匀分布。John Wiley & Sons，纽约。
- 重印版：Dover Publications（2006）
- 关于均匀分布理论的权威参考
- 第 2 章，定理 3.1 证明了基数反转序列的差异界
- Motwani, R. and Raghavan, P. (1995). 随机化算法。Cambridge University Press，纽约。
- 第 5.5 节涵盖拟随机序列，具有可访问的证明
- 计算机科学家的优秀入门
- Dick, J. and Pillichshammer, F. (2010). 数字网络和序列：差异理论和拟蒙特卡罗积分。Cambridge University Press。
- 第 4 章提供了 Sobol 序列的现代处理
- 全面覆盖当代拟蒙特卡罗方法
技术资源
- Živković, M. “本原二进制多项式表。” Mathematics of Computation。
- 可在以下地址获得：https://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf
- 阶数 n < 5000 的本原多项式综合表
- Partow.net 本原多项式列表
- 可在以下地址获得：https://www.partow.net/programming/polynomials/
- GF(2^m) 的本原不可约多项式列表，阶数 2-32
实现参考
- Joe, S. and Kuo, F.Y. (2003). “关于算法 659 的评论：实现 Sobol 的拟随机序列生成器。” ACM Transactions on Mathematical Software，29(1)，49-57。
- 将 Bratley & Fox 扩展到 1111 个维度
- SciPy 实现：
scipy.stats.qmc.Sobol- 使用 Joe & Kuo 参数的生产质量 Python 实现
- GNU Scientific Library (GSL)： Sobol 序列生成器
- C/C++ 实现，带文档
补充阅读
- Dick, J. and Pillichshammer, F. (2014). “从范德科普特到拟蒙特卡罗规则的现代序列构造。” Indagationes Mathematicae，26(5)，760-822。
- 连接经典和现代方法的优秀历史概述
- 可在以下地址获得：https://arxiv.org/abs/1506.03764
代码来源
- Skylake-Official AFPEnemySpawner
- GitHub 存储库：AFPEnemySpawner.cpp
- 启发这次深入探讨的原始 Unreal Engine 实现
注意： 上面引用的数学证明使用以下技术：
- Weyl 的等分布准则（傅里叶分析）
- Erdős-Turán 不等式（差异界）
- 二进制分区论证（组合计数）
对于对完整严格证明感兴趣的读者，从 Kuipers & Niederreiter（1974）或更易访问的 Motwani & Raghavan（1995）开始。