7.2 场景的可达性
独立游戏关卡设计与环境叙事 谈「玩家会不会走到那个地方」，靠的是动线、地标、视觉引导——那是空间与环境叙事的设计经验，它给的是「大概会走进去」。本节换一个问法：把场景图当成一张有向图，从起始场景出发，哪些场景真的可达？答案不靠直觉，靠一次 BFS。
可达性要问两个问题
「可达」这个词在这个案例里要拆成两个不同的问题：
| 问题 | 口径 | 回答它的工具 |
|---|---|---|
| 图连不连通 | 带条件的边当作「可能通」 | 场景图 BFS（本节） |
| 某一局走不走得到 | 条件在具体状态下是否成立 | 状态空间穷举（卷二第 5 章） |
本节只回答第一个。它的价值是便宜的：14 个节点、16 条边，一次 BFS 就完了，不需要展开状态。它的局限也是明确的：结构可达不等于一局可达——一个场景可能在图上通，却因为它的入口条件在每一局里都凑不齐而永远进不去。
口径：把带条件的边当作「可能通」
BFS 要能走，就得先定「什么算能走」。本节的口径是：一条带条件的边，只要它的条件在某个可达状态下能满足，就当作可通行。于是 5 条带条件的边在 BFS 里全都被当成普通边。
这个口径有一个直接后果：BFS 走出来的可达集，是「可能被走到」的上界。真实的可达集是它的子集。所以如果连这个上界里都有场景进不去，那才是真问题；反过来，上界里全通，不代表每一局都通。
S 层：场景图上的 BFS
下面这段是 S 层脚本 sim/na_07_2_reachability.py。它从起始场景出发做 BFS，每个场景统计四列：入度 / 出度（按边计，不看条件）、最少跳数（hops，边数）、最早出现幕（earliest_act，所有路径上「途经场景的最大幕号」的最小值）。earliest_act 用松弛法算——earliest[v] = max(act(v), min over preds earliest[pred])——不依赖「图恰好按幕分层」这个先验，万一哪天加一条跨幕回绕的边，它照样算得出。
#!/usr/bin/env python3
# file: sim/na_07_2_reachability.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/na_07_2_reachability.py
"""卷一 7.2 场景的可达性（S 层）。
关键问题：**14 个场景里，哪些真的可达？**
本节在**场景图层面**做 BFS，把带条件的边当作「可能通」——条件只要在某个状态
下能满足，就视为这条边可走。于是 BFS 给出的是一张**结构可达性**表，它回答的是
「这张图连不连通」，不是「某一局一定走得到」。
每个场景统计四列：
in / out 入度、出度（按边计，不看条件）
hops 从起始场景出发的最少跳数（边数）
earliest_act 最早出现幕：所有路径上「途经场景的最大幕号」的最小值
entry_cond_all 入口边是否**全部**带条件（是则它的可达性完全取决于状态）
`earliest_act` 用松弛法算（`earliest[v] = max(act(v), min over preds earliest[pred])`），
不依赖「图恰好按幕分层」这个先验——如果哪天有人加一条跨幕回绕的边，它照样算得出。
产出 out/narr07_reachability.csv；不可达场景数 > 0 即非零退出。
"""
from __future__ import annotations
import csv
import json
import os
import sys
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
SPEC = os.path.join(ROOT, "config/story_spec.json")
CSV_PATH = os.path.join(OUT, "narr07_reachability.csv")
def load_spec() -> dict:
with open(SPEC, encoding="utf-8") as fh:
return json.load(fh)
def start_scene(spec: dict) -> str:
"""起始场景 = meta.start 指向的对话节点所属的 scene。"""
sid = spec["meta"]["start"]
node = next(n for n in spec["dialogue"] if n["id"] == sid)
return node["scene"]
def analyse(graph: dict, start: str) -> dict:
nodes = {n["id"]: n for n in graph["nodes"]}
succ: dict[str, list[str]] = {k: [] for k in nodes}
preds: dict[str, list[str]] = {k: [] for k in nodes}
entry_cond: dict[str, list[bool]] = {k: [] for k in nodes}
for e in graph["edges"]:
succ[e["from"]].append(e["to"])
preds[e["to"]].append(e["from"])
entry_cond[e["to"]].append(bool(e.get("when")))
# BFS：最短跳数 + 可达集
hops: dict[str, int] = {start: 0}
queue = [start]
while queue:
u = queue.pop(0)
for v in succ[u]:
if v not in hops:
hops[v] = hops[u] + 1
queue.append(v)
# 松弛：earliest_act[v] = max(act(v), min over preds earliest_act[pred])
INF = 1 << 30
earliest: dict[str, int] = {k: INF for k in nodes}
earliest[start] = nodes[start]["act"]
changed = True
while changed:
changed = False
for u in nodes:
if earliest[u] == INF:
continue
for v in succ[u]:
cand = max(nodes[v]["act"], earliest[u])
if cand < earliest[v]:
earliest[v] = cand
changed = True
rows = []
for nid, n in nodes.items():
reachable = nid in hops
ec = entry_cond[nid]
rows.append({
"scene": nid,
"act": n["act"],
"in_degree": len(preds[nid]),
"out_degree": len(succ[nid]),
"hops": hops.get(nid, -1),
"earliest_act": earliest[nid] if reachable else -1,
"entry_edges": len(ec),
"entry_cond_all": bool(ec) and all(ec),
"reachable": reachable,
})
return {"rows": rows, "hops": hops, "earliest": earliest, "preds": preds}
def main() -> int:
spec = load_spec()
graph = spec["scene_graph"]
start = start_scene(spec)
res = analyse(graph, start)
rows = res["rows"]
reachable = [r for r in rows if r["reachable"]]
unreachable = [r for r in rows if not r["reachable"]]
cond_only = [r for r in rows if r["entry_cond_all"]]
print(f"起始场景={start} 节点={len(rows)} 可达={len(reachable)} 不可达={len(unreachable)}")
print(f"{'scene':<16}{'act':>4}{'in':>4}{'out':>4}{'hops':>6}{'earliest':>10}{'entry':>7} entry_cond_all")
for r in sorted(rows, key=lambda r: (r["act"], r["hops"] if r["hops"] >= 0 else 99, r["scene"])):
print(f"{r['scene']:<16}{r['act']:>4}{r['in_degree']:>4}{r['out_degree']:>4}"
f"{r['hops']:>6}{r['earliest_act']:>10}{r['entry_edges']:>7} {r['entry_cond_all']}")
print(f"入口边全部带条件的场景（可达性完全取决于状态）：{[r['scene'] for r in cond_only]}")
if unreachable:
print(f"不可达场景：{[r['scene'] for r in unreachable]}")
# 结构不变量：可达 + 不可达 = 全部；起始场景入度 0
assert len(reachable) + len(unreachable) == len(rows), "可达 + 不可达应等于全部节点"
assert res["preds"][start] == [], f"起始场景 {start} 不应有入边"
os.makedirs(OUT, exist_ok=True)
with open(CSV_PATH, "w", encoding="utf-8", newline="") as fh:
w = csv.DictWriter(fh, fieldnames=["scene", "act", "in_degree", "out_degree", "hops",
"earliest_act", "entry_edges", "entry_cond_all", "reachable"])
w.writeheader()
for r in sorted(rows, key=lambda r: (r["act"], r["hops"] if r["hops"] >= 0 else 99, r["scene"])):
w.writerow(r)
print(f"wrote out/narr07_reachability.csv rows={len(rows)}")
if unreachable:
print(f"FAIL 有 {len(unreachable)} 个场景不可达")
return 1
print("OK na_07_2_reachability：14 个场景在「条件视为可满足」的口径下全部可达")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/na_07_2_reachability.py：
起始场景=pier 节点=14 可达=14 不可达=0
scene act in out hops earliest entry entry_cond_all
pier 1 0 2 0 1 0 False
chapel 1 1 1 1 1 1 False
tavern 1 1 1 1 1 1 False
counting_house 1 1 1 2 1 1 True
watch_post 1 1 1 2 1 1 True
lighthouse_base 2 2 2 3 2 2 False
market_row 2 1 1 4 2 1 False
tide_cave 2 1 1 4 2 1 True
drowned_bell 2 1 1 5 2 1 True
harbor_office 2 1 1 5 2 1 True
lighthouse_top 3 2 2 6 3 2 False
breakwater 3 1 1 7 3 1 False
fog_gate 3 1 1 7 3 1 False
dawn_quay 3 2 0 8 3 2 False
入口边全部带条件的场景（可达性完全取决于状态）：['counting_house', 'watch_post', 'tide_cave', 'harbor_office', 'drowned_bell']
wrote out/narr07_reachability.csv rows=14
OK na_07_2_reachability：14 个场景在「条件视为可满足」的口径下全部可达
同一趟写出的 out/narr07_reachability.csv（每场景一行）：
scene,act,in_degree,out_degree,hops,earliest_act,entry_edges,entry_cond_all,reachable
pier,1,0,2,0,1,0,False,True
chapel,1,1,1,1,1,1,False,True
tavern,1,1,1,1,1,1,False,True
counting_house,1,1,1,2,1,1,True,True
watch_post,1,1,1,2,1,1,True,True
lighthouse_base,2,2,2,3,2,2,False,True
market_row,2,1,1,4,2,1,False,True
tide_cave,2,1,1,4,2,1,True,True
drowned_bell,2,1,1,5,2,1,True,True
harbor_office,2,1,1,5,2,1,True,True
lighthouse_top,3,2,2,6,3,2,False,True
breakwater,3,1,1,7,3,1,False,True
fog_gate,3,1,1,7,3,1,False,True
dawn_quay,3,2,0,8,3,2,False,True
判读：14 个场景全部可达，但有 5 个要过门
表里最有信息量的不是「全通」，而是 entry_cond_all 这一列：
| 观察 | 表里的证据 | 含义 |
|---|---|---|
| 14 / 14 可达 | 不可达=0 | 场景图在结构上连通，没有孤岛 |
| 5 个场景入口全带条件 | entry_cond_all=True 共 5 行 | 它们的可达性完全取决于状态 |
| 最早出现幕 = 声明幕 | earliest_act 与 act 逐行相等 | 图没有跨幕回绕，幕分层是紧的 |
| 跳数单调 | hops 0→8 逐层展开 | 从码头到黎明码头最少 8 跳 |
第二行是本节的关键发现：counting_house、watch_post、tide_cave、harbor_office、drowned_bell 这 5 个场景，入边全部带条件——它们没有一条「无条件入口」兜底。也就是说，只要对应的 flag / item 在某一局里凑不齐，这个场景在那一局里就进不去。BFS 把它们的可达性算成「可能可达」，但真正的可达与否，要回到状态层去问。
对比之下，lighthouse_base、lighthouse_top、dawn_quay 的入口边里有无条件的（前者是 counting_house / watch_post 两条无条件入边，后两者同理），所以它们在任何一局里都进得去。
第三行是另一种确认：earliest_act 与节点自己声明的 act 逐行相等。这说明所有边都从低幕指向高幕（或同幕），没有「第一夜的场景要等第三夜的状态」这种回绕。这条事实会在 7.3 变成「无环」的判定依据。
最后要写清口径的局限：这里的「可达」是结构可达，是一个上界。它用一次 BFS 换来了便宜，代价是它不看条件——所以它既不能说「某个场景每局都能进」，也不能说「某个场景某局一定进不去」。要判后者，得把条件代进去跑状态空间，那是卷二第 5 章的对象。本节给出的是「有没有孤岛」这个更粗但更便宜的问题的答案，而答案是没有。
自检表
| 检查项 | 合格标准 |
|---|---|
| 起始场景有据 | 由 meta.start 指向的对话节点的 scene 决定，不硬编码 |
| 口径写死 | 明确声明「带条件边当作可能通」，并说明结果是上界 |
| 上界与实达分开 | 显式区分结构可达与一局可达，后者指向状态层 |
| 不变量成对 | 断言「可达 + 不可达 = 全部」与「起始场景入度 0」 |
| 跳数可核 | hops 从 0 起、逐层递增，可在邻接表上手算复核 |
可达性回答了「能不能到」，但没回答「按什么顺序到」。5 条带条件的边其实在说「先有钥匙、再进门」，而钥匙会不会被锁在门后，是下一节的事。
阅读导航：上一节：7.1 场景图：节点、边与入口条件 · 下一节：7.3 顺序约束与解锁 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。