5.1 状态空间的规模
Phaser 分支叙事 讲的是分支叙事在引擎里怎么落地——对话怎么挂、分支怎么切、场景怎么跳，那是实现。本节不做任何实现，只回答一个更基础的问题：把这份规格的所有可能状态摆出来，它到底有多大？答案不是「14 个场景 × 5 个结局」，而是节点、好感度、flag、物品四者的笛卡尔积。
一个状态由什么构成
引擎里的状态是一个四元组：当前节点、4 个好感度变量的值、18 个 flag 的置位情况、9 个线索物品的持有情况（第 1 章给过它的完整定义）。把它当成可枚举的对象，每一维都取自一个有限域：
| 维 | 域 | 大小 |
|---|---|---|
| 节点 | 48 个对话节点 | 48 |
| 好感度 | 4 个变量，各 0–100 整数 | 101⁴ |
| flag | 18 个布尔 | 2¹⁸ |
| 物品 | 9 个布尔 | 2⁹ |
四维相乘得到朴素上界——「如果每一维都能自由取值、彼此独立」时状态的总数：48 × 101⁴ × 2¹⁸ × 2⁹ = 670404028655468544，约 6.70×10¹⁷。这个数大得没有直觉：即便每秒枚举十亿个状态，也要二十多年。如果状态空间真有这么大，任何穷举都是幻想——这正是「分支会爆炸」这句话的字面含义。
S 层：把上界与真实可达并列
但真实可达的状态远远小于这个上界。下面这段 S 层脚本 sim/ne_05_1_scale.py 做两件事：先由声明域直接算出朴素上界 B0，再对规格做一次按条件剪枝的 BFS 完整枚举，跑出真实可达状态数 R；中间另算两个逐步收紧、但仍是上界的中间量 B1 / B2，用来定位差距从哪来。状态在 frontier 里打包成整数（好感度 7 位一段、flag / item 各一位图），只在去重时展开成规范串。
#!/usr/bin/env python3
# file: sim/ne_05_1_scale.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ne_05_1_scale.py
"""卷二 5.1 状态空间的规模（S 层）：朴素上界 vs 真实可达。
一个「状态」= 节点 × 4 个好感度 × 18 个 flag × 9 个物品。本节把两条路并列：
朴素上界 B0 = 48 × 101⁴ × 2¹⁸ × 2⁹
（48 个节点、好感度 0–100 共 101 个取值、flag 布尔、物品有无）
真实可达 R = 从起点出发、按条件剪枝的 BFS 完整枚举
再给出两个**逐步收紧、但仍是上界**的中间量，用来定位差距从哪来：
B1 = 48 × ∏(好感度实际取到的值数) × 2¹⁸ × 2⁹ # 只收紧好感度值域
B2 = 48 × ∏(好感度实际取到的值数) × |flag 位图| × |item 位图| # 再收紧 flag/item
B0 与 R 的比值给出「差了几个数量级」；B2 仍大于 R，说明真正的收缩来自
**变量之间的相关性**与**节点-状态耦合**（路径约束），而非单变量的取值多少。
"""
from __future__ import annotations
import json
import math
import os
import sys
import time
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
JSON_PATH = os.path.join(OUT, "ne_05_1_scale.json")
AFF_LO, AFF_HI = 0, 100
STATE_BUDGET = 12000000
def load_spec() -> dict:
with open(os.path.join(ROOT, "config/story_spec.json"), encoding="utf-8") as fh:
return json.load(fh)
def clamp(v: int, lo: int = AFF_LO, hi: int = AFF_HI) -> int:
return lo if v < lo else hi if v > hi else v
def eval_cond(c, st: dict) -> bool:
if c is None:
return True
k = c[0]
if k == "flag":
return st["flags"].get(c[1], 0) == c[2]
if k == "aff":
v, op, n = st["aff"].get(c[1], 0), c[2], c[3]
if op == ">=":
return v >= n
if op == "<":
return v < n
if op == "==":
return v == n
return v != n
if k == "item":
return st["items"].get(c[1], 0) == c[2]
if k == "and":
return eval_cond(c[1], st) and eval_cond(c[2], st)
if k == "or":
return eval_cond(c[1], st) or eval_cond(c[2], st)
return not eval_cond(c[1], st) # not
def apply_effects(eff: dict, st: dict) -> dict:
aff, flags, items = dict(st["aff"]), dict(st["flags"]), dict(st["items"])
for k, v in (eff.get("set") or {}).items():
flags[k] = v
for k, v in (eff.get("add") or {}).items():
aff[k] = clamp(aff.get(k, 0) + v)
for k, v in (eff.get("grant") or {}).items():
items[k] = v
for k in (eff.get("revoke") or {}):
items[k] = 0
return {"aff": aff, "flags": flags, "items": items}
def enumerate_reachable(spec: dict) -> dict:
"""完整 BFS：返回可达状态数、好感度值域、flag/item 位图数。"""
by_id = {n["id"]: n for n in spec["dialogue"]}
VARS = sorted(spec["state"]["vars"])
FLAGS = sorted(spec["state"]["flags"])
ITEMS = sorted(spec["state"]["items"])
NV = len(VARS)
def canon(node, aff, flags, items):
a = ",".join(f"{k}={aff[k]}" for k in VARS)
f = ",".join(k for k in FLAGS if flags[k])
it = ",".join(k for k in ITEMS if items[k])
return f"{node}|{a}|{f}|{it}"
def pack(aff, flags, items):
code = 0
for v in VARS:
code = (code << 7) | aff[v]
fb = 0
for i, k in enumerate(FLAGS):
if flags[k]:
fb |= 1 << i
ib = 0
for i, k in enumerate(ITEMS):
if items[k]:
ib |= 1 << i
return code, fb, ib
def unpack(code, fb, ib):
aff = {VARS[i]: (code >> (7 * (NV - 1 - i))) & 127 for i in range(NV)}
flags = {FLAGS[i]: (fb >> i) & 1 for i in range(len(FLAGS))}
items = {ITEMS[i]: (ib >> i) & 1 for i in range(len(ITEMS))}
return aff, flags, items
start = spec["meta"]["start"]
aff0 = {v: next(c["affinity"]["init"] for c in spec["characters"] if c["id"] == v) for v in VARS}
flags0 = {f: 0 for f in FLAGS}
items0 = {i: 0 for i in ITEMS}
c0, b0, g0 = pack(aff0, flags0, items0)
frontier = [(start, c0, b0, g0)]
seen = {canon(start, aff0, flags0, items0)}
aff_vals = {v: set() for v in VARS}
flag_bm: set = set()
item_bm: set = set()
states = 0
budget_hit = False
while frontier:
nxt = []
for node, code, fb, ib in frontier:
states += 1
aff, flags, items = unpack(code, fb, ib)
for v in VARS:
aff_vals[v].add(aff[v])
flag_bm.add(fb)
item_bm.add(ib)
cur = by_id[node]
if cur.get("ending"):
continue
st = {"aff": aff, "flags": flags, "items": items}
for c in (cur.get("choices") or []):
if not eval_cond(c.get("when"), st):
continue
st2 = apply_effects(c.get("effects") or {}, st)
k = canon(c["goto"], st2["aff"], st2["flags"], st2["items"])
if k not in seen:
seen.add(k)
c2, b2, g2 = pack(st2["aff"], st2["flags"], st2["items"])
nxt.append((c["goto"], c2, b2, g2))
frontier = nxt
if states > STATE_BUDGET:
budget_hit = True
break
return {
"states": states,
"budget_hit": budget_hit,
"vars": VARS,
"aff_distinct": {v: len(aff_vals[v]) for v in VARS},
"flag_bitmaps": len(flag_bm),
"item_bitmaps": len(item_bm),
}
def main() -> int:
t0 = time.time()
spec = load_spec()
n_nodes = len(spec["dialogue"])
n_vars = len(spec["state"]["vars"])
n_flags = len(spec["state"]["flags"])
n_items = len(spec["state"]["items"])
b0 = n_nodes * (101 ** n_vars) * (2 ** n_flags) * (2 ** n_items)
print(f"状态 = 节点 × {n_vars} 个好感度 × {n_flags} 个 flag × {n_items} 个物品")
print(f"朴素上界 B0 = {n_nodes} × 101^{n_vars} × 2^{n_flags} × 2^{n_items} = {b0}")
res = enumerate_reachable(spec)
states = res["states"]
aff_prod = math.prod(res["aff_distinct"].values())
b1 = n_nodes * aff_prod * (2 ** n_flags) * (2 ** n_items)
b2 = n_nodes * aff_prod * res["flag_bitmaps"] * res["item_bitmaps"]
print(f"好感度实际取到的值数：{res['aff_distinct']}（声明域 101）")
print(f"flag 位图 {res['flag_bitmaps']} 种（上界 2^{n_flags}={2 ** n_flags}），"
f"item 位图 {res['item_bitmaps']} 种（上界 2^{n_items}={2 ** n_items}）")
print(f"B1（只收紧好感度值域）= {b1}")
print(f"B2（再收紧 flag/item）= {b2}")
print(f"真实可达 R（BFS 完整枚举，预算 {STATE_BUDGET}，超限={res['budget_hit']}）= {states}")
print(f"B0 / R = {b0 / states:.3e} ≈ 10^{math.log10(b0 / states):.1f}")
print(f"B1 / R = {b1 / states:.3e} B2 / R = {b2 / states:.3e}")
print(f"耗时 {round(time.time() - t0, 1)}s")
assert not res["budget_hit"], "BFS 超预算"
assert 0 < states < b0, "真实可达应严格小于朴素上界"
os.makedirs(OUT, exist_ok=True)
report = {
"nodes": n_nodes,
"naive_bound_b0": b0,
"bound_b1_aff_tightened": b1,
"bound_b2_flag_item_tightened": b2,
"reachable": states,
"ratio_b0_over_r": b0 / states,
"ratio_b1_over_r": b1 / states,
"ratio_b2_over_r": b2 / states,
"aff_distinct": res["aff_distinct"],
"flag_bitmaps": res["flag_bitmaps"],
"item_bitmaps": res["item_bitmaps"],
"state_budget": STATE_BUDGET,
}
with open(JSON_PATH, "w", encoding="utf-8") as fh:
json.dump(report, fh, ensure_ascii=False, indent=2)
fh.write("\n")
print(f"wrote out/ne_05_1_scale.json")
print(f"OK ne_05_1_scale：朴素上界 {b0}，真实可达 {states}，差约 {math.log10(b0 / states):.0f} 个数量级")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/ne_05_1_scale.py：
状态 = 节点 × 4 个好感度 × 18 个 flag × 9 个物品
朴素上界 B0 = 48 × 101^4 × 2^18 × 2^9 = 670404028655468544
好感度实际取到的值数：{'hui': 35, 'mu': 16, 'shen': 12, 'yan': 21}（声明域 101）
flag 位图 711 种（上界 2^18=262144），item 位图 36 种（上界 2^9=512）
B1（只收紧好感度值域）= 909158677217280
B2（再收紧 flag/item）= 173381160960
真实可达 R（BFS 完整枚举，预算 12000000，超限=False）= 9895423
B0 / R = 6.775e+10 ≈ 10^10.8
B1 / R = 9.188e+07 B2 / R = 1.752e+04
耗时 90.6s
wrote out/ne_05_1_scale.json
OK ne_05_1_scale：朴素上界 670404028655468544，真实可达 9895423，差约 11 个数量级
判读：真实可达比朴素上界小约 11 个数量级
第一，真实可达是 9895423，约 9.90×10⁶。 它落在 10⁶–10⁷ 量级，这正是本案例的设计目标——可穷举但非平凡：小到一次 BFS 能跑完，大到不是「数一数就完」。
第二，B0 / R = 6.78×10¹⁰，即小了约 11 个数量级。 差距不是一两倍，而是十个数量级往上。
第三，差距可以逐层拆开。
| 量 | 表达式 | 值 | 与 R 之比 |
|---|---|---|---|
| B0 朴素上界 | 48 × 101⁴ × 2¹⁸ × 2⁹ | 670404028655468544 | 6.78×10¹⁰ |
| B1 收紧好感度值域 | 48 × 141120 × 2¹⁸ × 2⁹ | 909158677217280 | 9.19×10⁷ |
| B2 再收紧 flag / 物品 | 48 × 141120 × 711 × 36 | 173381160960 | 1.75×10⁴ |
| R 真实可达 | BFS 完整枚举 | 9895423 | 1 |
第一层，好感度只能取到有限个可达值：4 个变量声明域各是 101 个整数，但实际跑下来 yan 只取到 21 个值、hui 35 个、shen 12 个、mu 16 个，乘起来 141120，远小于 101⁴ = 104060401。只收紧这一维，B1 就从 6.70×10¹⁷ 掉到 9.09×10¹⁴（逐变量的值域表见第 5.2 节
）。
第二层，flag 与物品的位图也远小于全空间：18 个 flag 理论上有 2¹⁸ = 262144 种置位组合，实测只出现 711 种；9 个物品理论上有 2⁹ = 512 种持有组合，实测只出现 36 种。再收紧这一层，B2 降到 1.73×10¹¹。
第三层，也是最后也最关键的：B2 仍然比 R 大 1.75×10⁴ 倍。剩下的差距不再是「某一维取值少」，而是变量之间的相关性与路径约束——好感度与 flag 不是独立可取的，它们被同一条路径一起推进；而 48 个节点也不是每一个都能配上任意状态，只有沿真实选项序列演化出来的组合才落在可达集里。条件剪枝（每一步只走 when 成立的边）与路径约束（状态必须来自一条真实路径）共同把 B2 又砍掉了四个数量级，才落到 9895423。
一句话：「分支会爆炸」是朴素上界说的；「穷举跑得完」是条件剪枝与路径约束说的。 两者都是真的，差别在于前者假设每一维自由独立，后者只承认真正走得出来的组合。
自检表
| 检查项 | 合格标准 |
|---|---|
| 上界可复算 | B0 由声明域直接算出，与脚本输出一致 |
| 真实可达真跑 | R 来自 BFS 完整枚举，非估计 |
| 中间量仍为上界 | B1 / B2 都严格 ≥ R，逐层收紧 |
| 整数不变量 | 好感度 ∈ [0,100]，枚举未超预算 |
| 差距可归因 | 每一层的收缩都指向具体的一维或一类约束 |
知道了总量，下一步是把它真的列出来——不是数一个总数，而是逐层展开、看清每一层新增多少、每个好感度变量到底取了哪些值。这是下一节的事。
阅读导航：上一节：4.3 回放的逐位一致 · 下一节：5.2 可达状态的枚举 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。