6.1 死路检测
站内的独立游戏的叙事设计与分支对话 谈的是分支汇聚的经验：哪里该合、哪里该分，配的是清单与示意图，代码不可跑。本节把它换成一条能跑出计数的判据：什么样的状态叫「卡死」、怎么在 990 万个可达状态里把它找出来、以及——如果检测器什么都查不出来，怎么证明它不是一个永远返回「空」的摆设。第 5 章数过状态空间的规模与可达性，这一章从「可达」往前一步，问「走进去会不会出不来」。
死路是什么：一句话写死定义
死路指一个节点在当前状态下没有任何可用选项、且它不是结局节点。这时玩家既不能继续、也没有看到结局——游戏卡住了。这个定义里有三个词必须同时成立，缺一不可：
| 条件 | 含义 | 反例 |
|---|---|---|
| 当前状态下无可用选项 | 把 when 代进具体状态求值后，可用选项数为 0 | 节点有 3 个选项，但当前状态只满足其中 1 个——不叫死路 |
| 不是结局节点 | 节点没有 ending 字段 | 结局节点本来就没有出边，那是正常的终止 |
| 是在某个可达状态下 | 这个状态真的能从起点走到 | 一个永远走不到的状态里没有选项，无关紧要 |
把定义写成可执行的判据之后，「有没有死路」就变成一个可枚举的问题：遍历所有可达状态，逐个检查「无可用选项且非结局」。它不依赖任何主观判断，也不靠「跑着看看会不会卡」。
两种查法：静态与动态
判据一样，查法分两档，成本差很多：
- 静态死路：不看状态，只看节点有没有出边。一个节点
choices为空、又没有ending，它在任何状态下都是死路。这一档只要扫一遍节点表。 - 动态死路：把状态代进去求值
when之后才无可用选项。这一档必须枚举可达状态——同一个节点在某些状态下有选项、在另一些状态下没有。
动态这一档是真正的对象。它难在状态空间大：本规格朴素上界是 101⁴ × 2¹⁸ × 2⁹，真实可达 990 万个状态（第 5 章实测 9895423）。逐个枚举不现实吗？其实可以——只要先做一步投影：没有任何条件读到的状态量，不可能影响任何转移，可以整个投影掉。本规格 18 个 flag 里只有 7 个被对话条件读到、9 个物品里只有 8 个被读到、4 个好感度全部被读到。投影后状态数从 990 万降到 3042869，BFS 六秒跑完。投影不改变任何结论，因为它丢掉的维度在任何条件里都没出现过。
S 层：投影状态上的完整 BFS 与采样
脚本 sim/ne_06_1_dead_end.py 做三件事：① 扫静态死路；② 在投影状态上做完整 BFS，精确枚举「无可用选项且非结局」的状态；③ 再用 20000 条随机路径采样交叉验证。随机数用自实现的 Lehmer MINSTD（rng = rng * 48271 % 2147483647），与全书同一套，禁用语言内置 random。
#!/usr/bin/env python3
# file: sim/ne_06_1_dead_end.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ne_06_1_dead_end.py
"""卷二 6.1 死路检测（S 层）：静态死路与动态死路。
死路的定义写死在这里：一个节点在当前状态下**没有任何可用选项、且不是结局节点**，
玩家就卡死了。分两种查法：
1) 静态死路——不看状态，只看节点有没有出边（choices 为空且非结局）；
2) 动态死路——把状态代进去求值 `when` 之后，仍没有一条可用选项。
动态死路用「投影到条件可读变量」的完整 BFS 精确枚举（未被任何条件读到的 flag /
item 不影响任何转移，投影掉不改变结论），再用 20000 条随机路径采样交叉验证。
只读 config/story_spec.json，产出 out/ne_06_1_dead_end.json。exit 0 表示无死路。
"""
from __future__ import annotations
import json
import os
import sys
from collections import defaultdict
HERE = os.path.dirname(os.path.abspath(__file__))
AFF_LO, AFF_HI = 0, 100
def load_spec() -> dict:
with open(os.path.join(HERE, "../config/story_spec.json"), encoding="utf-8") as fh:
return json.load(fh)
def read_vars(spec: dict) -> tuple[list[str], list[str], list[str]]:
"""收集被任一条件读到的变量：投影只保留这些（未读变量不影响任何转移）。"""
rf: set = set()
ri: set = set()
ra: set = set()
def walk(c) -> None:
if not c:
return
k = c[0]
if k in ("and", "or"):
walk(c[1])
walk(c[2])
elif k == "not":
walk(c[1])
elif k == "flag":
rf.add(c[1])
elif k == "item":
ri.add(c[1])
elif k == "aff":
ra.add(c[1])
for n in spec["dialogue"]:
walk(n.get("line_when"))
for c in (n.get("choices") or []):
walk(c.get("when"))
for e in spec["endings"]:
walk(e.get("when"))
return sorted(ra), sorted(rf), sorted(ri)
def main() -> int:
spec = load_spec()
nodes = spec["dialogue"]
by = {n["id"]: n for n in nodes}
start = spec["meta"]["start"]
RA, RF, RI = read_vars(spec)
AR = {v: i for i, v in enumerate(RA)}
FR = {v: i for i, v in enumerate(RF)}
IR = {v: i for i, v in enumerate(RI)}
def cond(c, aff, fl, it) -> bool:
if c is None:
return True
k = c[0]
if k == "flag":
return ((fl >> FR[c[1]]) & 1) == c[2]
if k == "item":
return ((it >> IR[c[1]]) & 1) == c[2]
if k == "aff":
v, op, n = aff[AR[c[1]]], c[2], c[3]
return {">=": v >= n, "<": v < n, "==": v == n, "!=": v != n}[op]
if k == "and":
return cond(c[1], aff, fl, it) and cond(c[2], aff, fl, it)
if k == "or":
return cond(c[1], aff, fl, it) or cond(c[2], aff, fl, it)
return not cond(c[1], aff, fl, it)
def step(eff, aff, fl, it):
aff = list(aff)
for k, v in (eff.get("set") or {}).items():
if k in FR:
fl = (fl | (1 << FR[k])) if v else (fl & ~(1 << FR[k]))
for k, v in (eff.get("add") or {}).items():
if k in AR:
nv = aff[AR[k]] + v
aff[AR[k]] = AFF_LO if nv < AFF_LO else AFF_HI if nv > AFF_HI else nv
for k, v in (eff.get("grant") or {}).items():
if k in IR:
it = (it | (1 << IR[k])) if v else (it & ~(1 << IR[k]))
for k in (eff.get("revoke") or {}):
if k in IR:
it &= ~(1 << IR[k])
return tuple(aff), fl, it
# ---- 1) 静态死路：无出边且非结局 ----
static_dead = [n["id"] for n in nodes if not (n.get("choices") or []) and not n.get("ending")]
# ---- 2) 动态死路：投影状态上的完整 BFS ----
aff0 = tuple(next(c["affinity"]["init"] for c in spec["characters"] if c["id"] == v) for v in RA)
seen = {(start, aff0, 0, 0)}
frontier = [(start, aff0, 0, 0)]
dyn_nodes: set = set()
dyn_states = 0
min_opts = 99
while frontier:
nxt = []
for node, aff, fl, it in frontier:
cur = by[node]
if cur.get("ending"):
continue
avail = [c for c in cur["choices"] if cond(c.get("when"), aff, fl, it)]
min_opts = min(min_opts, len(avail))
if not avail:
dyn_states += 1
dyn_nodes.add(node)
continue
for c in avail:
a2, f2, i2 = step(c.get("effects") or {}, aff, fl, it)
k = (c["goto"], a2, f2, i2)
if k not in seen:
seen.add(k)
nxt.append(k)
frontier = nxt
n_states = len(seen)
# ---- 3) 采样 20000 条路径（Lehmer MINSTD，seed 20261016）交叉验证 ----
rng = 20261016
def rnd(mod: int) -> int:
nonlocal rng
rng = (rng * 48271) % 2147483647
return rng % mod
stuck = 0
stuck_nodes: dict = defaultdict(int)
for _ in range(20000):
node, aff, fl, it = start, aff0, 0, 0
for _step in range(200):
cur = by[node]
if cur.get("ending"):
break
opts = [c for c in cur["choices"] if cond(c.get("when"), aff, fl, it)]
if not opts:
stuck += 1
stuck_nodes[node] += 1
break
c = opts[rnd(len(opts))]
aff, fl, it = step(c.get("effects") or {}, aff, fl, it)
node = c["goto"]
else:
stuck += 1
stuck_nodes[node] += 1
out = {
"static_dead_ends": static_dead,
"dynamic_dead_end_states": dyn_states,
"dynamic_dead_end_nodes": sorted(dyn_nodes),
"reachable_projected_states": n_states,
"min_available_options": min_opts,
"sampled_paths": 20000,
"sampled_stuck_paths": stuck,
"sampled_stuck_nodes": dict(stuck_nodes),
}
os.makedirs(os.path.join(HERE, "../out"), exist_ok=True)
with open(os.path.join(HERE, "../out/ne_06_1_dead_end.json"), "w", encoding="utf-8") as fh:
json.dump(out, fh, ensure_ascii=False, indent=2)
fh.write("\n")
print(f"静态死路（无出边且非结局）{len(static_dead)} 个：{static_dead}")
print(f"动态死路状态 {dyn_states} 个 / 节点 {len(dyn_nodes)} 个：{sorted(dyn_nodes)}")
print(f"投影可达状态 {n_states}（条件可读变量 {len(RA)} 好感 + {len(RF)} flag + {len(RI)} item）")
print(f"每状态最少可用选项 {min_opts}")
print(f"采样 20000 条路径：卡死 {stuck} 条 {dict(stuck_nodes)}")
if static_dead or dyn_states or stuck:
print("FAIL 存在死路")
return 1
print("OK ne_06_1_dead_end：静态与动态死路均为 0")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/ne_06_1_dead_end.py：
静态死路（无出边且非结局）0 个：[]
动态死路状态 0 个 / 节点 0 个：[]
投影可达状态 3042869（条件可读变量 4 好感 + 7 flag + 8 item）
每状态最少可用选项 1
采样 20000 条路径：卡死 0 条 {}
OK ne_06_1_dead_end：静态与动态死路均为 0
三个读数都是 0：静态死路 0、动态死路状态 0、采样卡死 0。第四行「每状态最少可用选项 1」是关键——它说明在 3042869 个可达状态里，没有任何一个状态让它所在节点变成 0 选项；最小值恰好是 1，不是 0。
P 层：负例——让检测器开火
「检测器返回 0」这句话有两种可能：真的没有死路，或者检测器坏了、永远返回 0。只有负例能区分这两者。P 层把检测器用 TypeScript 重写（复用 engine.ts 的 condOk / applyEffects / initState），先用真实规格断言 0 死路，再人为把某节点全部选项的 when 改成恒假，断言检测器报出该节点：
// file: core/test/ne_06_1_dead_end.test.ts
// tier: P
// verify: node --test 'core/test/ne_06_1_dead_end.test.ts'
// 卷二 6.1：死路检测器 —— 真实规格 0 死路；再用三组注入负例证明检测器会开火。
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 { detectDeadEnds, staticDeadEnds, muteNode } from "../src/inkwell/ne_06_1_dead_end.ts";
const HERE = dirname(fileURLToPath(import.meta.url));
const spec = JSON.parse(readFileSync(join(HERE, "../../config/story_spec.json"), "utf8")) as Spec;
test("真实规格：静态死路 0 个、动态死路 0 个状态", () => {
const r = detectDeadEnds(spec);
assert.deepEqual(r.staticDeadEnds, []);
assert.equal(r.dynamicDeadEndStates, 0);
assert.deepEqual(r.dynamicDeadEndNodes, []);
assert.ok(r.minAvailableOptions >= 1, "每个可达状态至少要有一个可用选项");
console.log(`可达投影状态 ${r.reachableStates}，最少可用选项 ${r.minAvailableOptions}`);
});
test("负例一 · 起点全部选项恒假：检测器报出 d_pier_1", () => {
const r = detectDeadEnds(muteNode(spec, "d_pier_1"));
assert.deepEqual(r.dynamicDeadEndNodes, ["d_pier_1"]);
assert.ok(r.dynamicDeadEndStates >= 1);
});
test("负例二 · 终局前节点 d_dq_2 全部选项恒假：卡在结局之前", () => {
const r = detectDeadEnds(muteNode(spec, "d_dq_2"));
assert.ok(r.dynamicDeadEndNodes.includes("d_dq_2"));
});
test("负例三 · 抽掉某节点的全部出边：静态检测器报出 d_pier_2", () => {
const clone: Spec = JSON.parse(JSON.stringify(spec));
clone.dialogue.find((n) => n.id === "d_pier_2")!.choices = [];
assert.deepEqual(staticDeadEnds(clone), ["d_pier_2"]);
});
本机实跑 node --test 'core/test/ne_06_1_dead_end.test.ts'：
可达投影状态 3042869，最少可用选项 1
✔ 真实规格：静态死路 0 个、动态死路 0 个状态 (4526.724584ms)
✔ 负例一 · 起点全部选项恒假：检测器报出 d_pier_1 (0.555417ms)
✔ 负例二 · 终局前节点 d_dq_2 全部选项恒假：卡在结局之前 (2860.334292ms)
✔ 负例三 · 抽掉某节点的全部出边：静态检测器报出 d_pier_2 (0.418666ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 7626.416167
三组负例覆盖了三条不同的失败路径：负例一（起点全假）证明「所有路径从一开始就卡死」能被抓到；负例二（终局前的 d_dq_2 全假）证明「走到最后一格才卡死」也能被抓到——注意 d_dq_2 不是起点，它要靠 BFS 从可达状态里走到才发现；负例三（抽掉出边）证明静态检测器独立工作。三组一起，「返回 0」才从「可能坏了」变成「确实没有」。
这个 0 有多硬。 静态与动态用的是两套独立判据，都返回 0 比单查一种可信；更重要的是动态这一档是精确的——3042869 个状态是全部可达状态（投影后），不是采样子集，所以「没有死路」在整个可达空间上成立。20000 条采样只是交叉验证，不是主证据。最小值恒为 1 还说明设计留了余量：只要某节点的选项在某些状态下会塌到 0，最小值就会是 0、死路计数也会非零。
这套判据放过什么。 它只问「有没有可用选项」，不问「可用选项好不好」。一个节点如果只剩一条明显是惩罚项的路，判据照样算它「不是死路」——因为「好不好」不是可判定的结构量。这是刻意的取舍：能被脚本判的必须离散、确定。
自检表
| 检查项 | 合格标准 |
|---|---|
| 定义写死 | 死路 = 无可用选项 ∧ 非结局 ∧ 该状态可达 |
| 动态精确 | 在全部可达状态上枚举，不拿采样冒充穷举 |
| 负例必给 | 至少一组注入负例证明检测器会报出，不只报计数 |
| 余量可读 | 报告「每状态最少可用选项」，让 0 死路可被交叉核对 |
死路是「走进去出不来」的静态缺陷；下一节换一个方向：汇聚点没问题，但汇聚之后如果状态不可区分，信息就被丢了——那是一种更隐蔽的缺陷。
阅读导航：上一节：5.3 不可达节点与孤儿结局 · 下一节：6.2 汇流的合法性 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。