14.2 随机路径的模糊测试
站内服务端的叙事分支状态架构 关心的是状态在并发与重连下的一致性，那是服务端架构层的正确性。本节是引擎层的另一件事：把随机路径本身当成模糊测试（fuzzing）的输入——不挑「精心设计」的路径，而是随机走两万条，看有没有哪一条走进死角、走出区间、或者根本不终止。它同样不涉及网络、数据库、并发，只在一份规格与一个内核里跑。
随机路径就是模糊测试的输入
模糊测试的经典形态是「拿随机字节喂解析器，看它崩不崩」。叙事引擎的输入是选择序列，所以模糊测试的形态是：从起点出发，每一步在当前状态下均匀随机挑一个可用选项，直到走进结局。一次运行 = 一条随机路径 = 一个随机输入。断言不是「输出等于某个期望值」（随机输入没有固定期望），而是三条不变量：
| # | 断言 | 违反即 |
|---|---|---|
| ① | 全部终止于 5 个结局之一 | 有卡死 / 不终止 |
| ② | 全程好感度恒 ∈ [0,100] 整数 | 有越界 |
| ③ | 每一步 goto 的目标节点都存在 | 有悬空 goto |
只要有一条被违反，模糊测试就 exit 1。它不证明规格完美，但它能在两万次随机尝试里证伪——这是模糊测试与穷举的分工：穷举（第 5 章）证明「全部可达状态」，模糊测试快速探「有没有明显坏掉」。
为什么必须自实现可播种 PRNG
全书有一条纪律：随机一律自实现可播种 PRNG，禁用语言内置 random / Math.random()。理由是跨语言对照——Python 与 TypeScript 必须能对同一批路径算出逐位相同的摘要。内置随机数发生器没有跨语言的位级契约，用它就永远对不上。
本节用 Lehmer MINSTD：rng = rng * 48271 % 2147483647，取模得到下标。Python 侧在 sim/ne_14_2_fuzz.py，TypeScript 侧复用内核 engine.ts 的 samplePaths——两处是同算法同种子，所以两万条路径逐条相同。
S 层：20000 条路径
S 层脚本从起点走 N=20000 条路径（seed 固定），统计结局分布与步数区间，并把前 500 条终局状态摘要与整批汇总摘要写进 out/ne_14_2_fuzz.json，供 P 层逐位比对：
#!/usr/bin/env python3
# file: sim/ne_14_2_fuzz.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ne_14_2_fuzz.py
"""卷二 14.2 随机路径的模糊测试（S 层）。
把随机路径当成模糊测试的输入：用自实现可播种 PRNG（Lehmer MINSTD：
rng = rng * 48271 % 2147483647，禁用语言内置 random）从起点走 N 条路径，
每一步在当前状态下**均匀随机**挑一个可用选项，直到走进结局节点。
三条断言（任何一条不成立即 exit 1）：
① 全部终止于 5 个结局之一（没有卡死、没有步数超预算）；
② 全程好感度恒 ∈ [0,100] 整数（无越界）；
③ 每步节点都存在（无悬空 goto）。
统计结局分布计数与步数区间；并把前 500 条路径的终局状态摘要（FNV-1a 32 位，
只对状态做、不对文本做）与整批的汇总摘要写进 out/ne_14_2_fuzz.json，
供 P 层同种子同批路径逐位比对。整数口径：全部 int，禁浮点。
"""
from __future__ import annotations
import json
import os
import sys
HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import na_00_spec_check as base # noqa: E402 复用 load_spec / eval_cond / apply_effects
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
N = 20000
SEED = 20261016
STEP_BUDGET = 200
DIGEST_PREFIX = 500
def init_state(spec: dict) -> dict:
aff = {v: next(c for c in spec["characters"] if c["id"] == v)["affinity"]["init"]
for v in sorted(spec["state"]["vars"])}
return {"node": spec["meta"]["start"], "aff": aff,
"flags": {f: 0 for f in sorted(spec["state"]["flags"])},
"items": {i: 0 for i in sorted(spec["state"]["items"])},
"path": [spec["meta"]["start"]]}
def canonical(s: dict) -> str:
aff = ",".join(f"{k}={s['aff'][k]}" for k in sorted(s["aff"]))
fl = ",".join(k for k in sorted(s["flags"]) if s["flags"][k])
it = ",".join(k for k in sorted(s["items"]) if s["items"][k])
return f"{s['node']}|{aff}|{fl}|{it}|{'>'.join(s['path'])}"
def digest(s: dict) -> int:
h = 2166136261
for ch in canonical(s):
h = ((h ^ ord(ch)) * 16777619) & 0xFFFFFFFF
return h
def main() -> int:
spec = base.load_spec()
by = {n["id"]: n for n in spec["dialogue"]}
name_of = {e["id"]: e["name"] for e in spec["endings"]}
start = spec["meta"]["start"]
rng = SEED
def rnd(mod: int) -> int:
nonlocal rng
rng = (rng * 48271) % 2147483647
return rng % mod
dist: dict = {e["name"]: 0 for e in spec["endings"]}
stuck = 0
over_budget = 0
oob = 0
dangling = 0
steps: list = []
digests: list = []
for _ in range(N):
s = init_state(spec)
n_step = 0
while True:
cur = by.get(s["node"])
if cur is None:
dangling += 1
break
if cur.get("ending"):
dist[cur["ending"]] += 1
steps.append(n_step)
digests.append(digest(s))
break
if n_step >= STEP_BUDGET:
over_budget += 1
break
opts = [c for c in (cur.get("choices") or []) if base.eval_cond(c.get("when"), s)]
if not opts:
stuck += 1
break
c = opts[rnd(len(opts))]
eff = c.get("effects") or {}
s = {"node": c["goto"], "aff": dict(s["aff"]), "flags": dict(s["flags"]),
"items": dict(s["items"]), "path": s["path"]}
ns = base.apply_effects(eff, {"aff": s["aff"], "flags": s["flags"], "items": s["items"]})
s["aff"], s["flags"], s["items"] = ns["aff"], ns["flags"], ns["items"]
s["path"] = [*s["path"], c["goto"]]
for v in spec["state"]["vars"]:
if not (0 <= s["aff"][v] <= 100):
oob += 1
n_step += 1
ended = sum(dist.values())
order = [e["name"] for e in spec["endings"]]
summary = 2166136261
for d in digests:
for ch in str(d):
summary = ((summary ^ ord(ch)) * 16777619) & 0xFFFFFFFF
out = {
"n": N, "seed": SEED, "step_budget": STEP_BUDGET,
"ended": ended, "stuck": stuck, "over_budget": over_budget,
"out_of_range": oob, "dangling_goto": dangling,
"ending_distribution": {k: dist[k] for k in order},
"step_min": min(steps), "step_max": max(steps),
"step_sum": sum(steps),
"summary_digest": summary,
"digest_prefix_len": DIGEST_PREFIX,
"digest_prefix": digests[:DIGEST_PREFIX],
}
os.makedirs(OUT, exist_ok=True)
with open(os.path.join(OUT, "ne_14_2_fuzz.json"), "w", encoding="utf-8") as fh:
json.dump(out, fh, ensure_ascii=False, indent=2)
fh.write("\n")
print(f"模糊测试 {N} 条路径（seed={SEED}，Lehmer MINSTD，步数预算 {STEP_BUDGET}）")
print(f"终止于结局 {ended} 条：卡死 {stuck} / 超预算 {over_budget} / 悬空 goto {dangling} / 好感度越界 {oob}")
print("结局分布：" + " · ".join(f"{k} {dist[k]}" for k in order))
rarest = min(order, key=lambda k: dist[k])
print(f"最稀有结局：{rarest} {dist[rarest]} 条（占比 {dist[rarest] * 1000 // ended}‰）")
print(f"步数区间 [{min(steps)}, {max(steps)}]，均值 {sum(steps) // len(steps)}")
print(f"前 {DIGEST_PREFIX} 条终局状态摘要前缀已写出，整批汇总摘要 {summary}")
if stuck or over_budget or oob or dangling or ended != N:
print("FAIL 模糊测试存在不终止 / 越界 / 悬空路径")
return 1
print("OK ne_14_2_fuzz：全部路径终止于 5 个结局之一，无卡死、无越界")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/ne_14_2_fuzz.py：
模糊测试 20000 条路径（seed=20261016，Lehmer MINSTD，步数预算 200）
终止于结局 20000 条：卡死 0 / 超预算 0 / 悬空 goto 0 / 好感度越界 0
结局分布：灯守 1018 · 离港 10074 · 真相 178 · 缄默 3223 · 沉没 5507
最稀有结局：真相 178 条（占比 8‰）
步数区间 [22, 31]，均值 25
前 500 条终局状态摘要前缀已写出，整批汇总摘要 2695131274
OK ne_14_2_fuzz：全部路径终止于 5 个结局之一，无卡死、无越界
20000 条全部终止于结局之一：卡死 0、超预算 0、悬空 goto 0、越界 0。
P 层：同一批路径的摘要逐位一致
P 层用 TypeScript 复用内核的 samplePaths（同算法同种子）跑同一批 20000 条路径，再读 Python 侧产物逐位比对——结局分布、摘要前缀、汇总摘要、步数区间四项全部对齐：
// file: core/test/ne_14_2_fuzz.test.ts
// tier: P
// verify: node --test 'core/test/ne_14_2_fuzz.test.ts'
// 14.2 随机路径模糊测试：20000 条同种子路径全部终止于 5 个结局之一，
// 并与 Python 侧（out/ne_14_2_fuzz.json）逐位比对终局状态摘要。
import test from "node:test";
import assert from "node:assert/strict";
import { readFileSync } from "node:fs";
import { join, dirname } from "node:path";
import { fileURLToPath } from "node:url";
import type { Spec } from "../src/inkwell/engine.ts";
import { fuzz } from "../src/inkwell/ne_14_2_fuzz.ts";
const HERE = dirname(fileURLToPath(import.meta.url));
const ROOT = join(HERE, "../..");
const spec = JSON.parse(readFileSync(join(ROOT, "config/story_spec.json"), "utf8")) as Spec;
const SEED = 20261016;
const N = 20000;
const py = JSON.parse(readFileSync(join(ROOT, "out/ne_14_2_fuzz.json"), "utf8")) as {
ending_distribution: Record<string, number>;
digest_prefix: number[];
summary_digest: number;
step_min: number;
step_max: number;
};
test("全部 20000 条路径终止于结局之一：卡死 0、超预算 0", () => {
const r = fuzz(spec, N, SEED);
assert.equal(r.ended, N);
assert.equal(r.stuck, 0);
assert.equal(r.overBudget, 0);
console.log(`路径 ${r.n}，终止 ${r.ended}，卡死 ${r.stuck}，超预算 ${r.overBudget}`);
});
test("结局分布与 Python 侧逐项相同（同种子同批路径）", () => {
const r = fuzz(spec, N, SEED);
assert.deepEqual(r.distribution, py.ending_distribution);
console.log(`结局分布 ${JSON.stringify(r.distribution)}`);
});
test("前 500 条终局状态摘要与 Python 侧逐位一致", () => {
const r = fuzz(spec, N, SEED);
assert.deepEqual(r.digests.slice(0, py.digest_prefix.length), py.digest_prefix);
console.log(`摘要前缀 ${py.digest_prefix.length} 条逐位一致，首条 ${py.digest_prefix[0]}`);
});
test("整批汇总摘要与 Python 侧相同；步数区间与 Python 侧相同", () => {
const r = fuzz(spec, N, SEED);
assert.equal(r.summaryDigest, py.summary_digest);
assert.equal(r.stepMin, py.step_min);
assert.equal(r.stepMax, py.step_max);
console.log(`汇总摘要 ${r.summaryDigest}，步数区间 [${r.stepMin}, ${r.stepMax}]`);
});
本机实跑 node --test 'core/test/ne_14_2_fuzz.test.ts'：
路径 20000，终止 20000，卡死 0，超预算 0
结局分布 {"灯守":1018,"离港":10074,"真相":178,"缄默":3223,"沉没":5507}
摘要前缀 500 条逐位一致，首条 3976226298
汇总摘要 2695131274，步数区间 [22, 31]
✔ 全部 20000 条路径终止于结局之一：卡死 0、超预算 0 (571.656875ms)
✔ 结局分布与 Python 侧逐项相同（同种子同批路径） (561.876417ms)
✔ 前 500 条终局状态摘要与 Python 侧逐位一致 (558.089458ms)
✔ 整批汇总摘要与 Python 侧相同；步数区间与 Python 侧相同 (646.970875ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 2558.799292
两侧的汇总摘要都是 2695131274，前 500 条摘要逐位一致。这就是「同算法同种子的自实现 PRNG」换来的：两万条路径、每一条的终局状态、每一个摘要，Python 与 TypeScript 完全对得上。摘要只对整数状态做，不对文本做——这一点是全书口径。
分布与步数怎么读
| 结局 | 计数 | 占比 |
|---|---|---|
| 离港 | 10074 | 504‰ |
| 沉没 | 5507 | 275‰ |
| 缄默 | 3223 | 161‰ |
| 灯守 | 1018 | 51‰ |
| 真相 | 178 | 9‰ |
均匀随机下分布是偏斜的，不是均匀的。原因在最后枢纽 d_dq_2：五个结局各由一条带条件选项门控（c_dq_2a–c_dq_2e），而 c_dq_2e（离港）无条件，永远可用；其余四条要满足各自的条件才出现。随机挑选是在当时可用的选项里等概率取一个，所以「可用的结局选项越多，每个被选中概率越低」——离港常驻，自然最高。
最稀有的 真相 178 条（9‰） 需要 bell_rung 为真，这是一条窄路径。这个数字本身不判好坏：分布是结构量，不是「平衡度」的绝对标尺。它的用途是回归基线——把这一批计数存下来，规格一改，分布一动，就能立刻看到（下一节）。
步数区间 [22, 31]、均值 25，说明每条路径都要穿过若干枢纽与场景才到结局，没有「三步速通」的短路径，也没有「走不完」的长路径。它同样是结构量：区间塌到个位数通常意味着某个枢纽塌了，区间拉长通常意味着某处出现了环。
自检表
| 检查项 | 合格标准 |
|---|---|
| 随机可复现 | 自实现 Lehmer MINSTD，同种子同序列，禁内置 random |
| 断言是命题 | 三条断言都是「对所有路径成立」的不变量，不是固定期望值 |
| 两侧逐位一致 | 同批路径的终局摘要跨语言逐位相同 |
| 摘要只对状态 | 只对整数状态做 digest，不对文本做 |
| 分布是结构量 | 不声称「平衡」「更好」，只作回归基线 |
两万条随机路径证明「怎么走都不会坏」。但它只说明当前这份规格没问题——规格一旦被改动，随机路径与分布就会变。下一节把摘要、分布与残差落成回归基线，让改动可见、可告警。
阅读导航：上一节：14.1 属性测试与不变量 · 下一节：14.3 回归与告警 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。