7.3 顺序约束与解锁

#!/usr/bin/env python3
# file: sim/na_07_3_order_unlock.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/na_07_3_order_unlock.py
"""卷一 7.3 顺序约束与解锁（S 层）。

带条件的边表达的是**顺序约束**：`lighthouse_base -> tide_cave` 的 when 是
`knows_tide_rule`，读作「先拿到潮汐规则，才进得了洞窟」。本节把 5 条带条件边折成
一张**约束表**，并做两项判定：

  1. **环检测**：场景图是不是 DAG。有环则「解锁顺序」不可定义——A 要等 B 的状态、
     B 又要等 A 的状态，两个门互相锁死。DFS 三色法找后向边；Kahn 算法顺带给出一个
     拓扑序（无环时它与幕序一致）。
  2. **不可达的解锁条件**：某条边的条件引用了 flag / item，而它只在**目标场景或
     其后**才可能被产生——「要进去得先有钥匙，钥匙却在门后面」。判定法：该引用的
     生产者场景里，是否至少有一个能在「进入目标场景之前」被走到（生产者从起点可达，
     且从生产者能走到目标场景）。

生产者映射来自 `dialogue`：`effects.set` 写 flag、`effects.grant` 写 item；把每个对话
节点按 scene 归到场景，就得到「哪个场景会产出哪个 flag / item」。

产出 out/narr07_constraints.csv；有环或有不可达解锁条件即非零退出。
"""
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")


def cond_label(c) -> str:
    if c is None:
        return ""
    k = c[0]
    if k in ("flag", "item"):
        return f"{k}:{c[1]}=={c[2]}"
    if k == "aff":
        return f"aff:{c[1]}{c[2]}{c[3]}"
    if k in ("and", "or"):
        return f"({cond_label(c[1])} {'&' if k == 'and' else '|'} {cond_label(c[2])})"
    if k == "not":
        return f"!{cond_label(c[1])}"
    return k


def cond_refs(c, acc) -> None:
    """收集条件里引用的 (kind, id)：flag / item 是场景级锁，aff 不是。"""
    if c is None:
        return
    if c[0] in ("flag", "item"):
        acc.append((c[0], c[1]))
    elif c[0] in ("and", "or"):
        cond_refs(c[1], acc)
        cond_refs(c[2], acc)
    elif c[0] == "not":
        cond_refs(c[1], acc)


def succ_map(graph):
    succ = {n["id"]: [] for n in graph["nodes"]}
    for e in graph["edges"]:
        succ[e["from"]].append(e["to"])
    return succ


def reach(succ, src):
    seen, stack = {src}, [src]
    while stack:
        for v in succ[stack.pop()]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return seen


def find_cycle(succ):
    """DFS 三色法：返回一条后向边构成的环，无环返回空列表。"""
    color = {k: 0 for k in succ}
    stack = []

    def dfs(u):
        color[u] = 1
        stack.append(u)
        for v in succ[u]:
            if color[v] == 1:
                return stack[stack.index(v):] + [v]
            if color[v] == 0:
                got = dfs(v)
                if got:
                    return got
        color[u] = 2
        stack.pop()
        return []

    for u in succ:
        if color[u] == 0:
            got = dfs(u)
            if got:
                return got
    return []


def topo_order(graph):
    """Kahn 算法：入度归零者按字典序入队，返回一个拓扑序。"""
    succ = succ_map(graph)
    indeg = {k: 0 for k in succ}
    for u in succ:
        for v in succ[u]:
            indeg[v] += 1
    order, ready = [], sorted(k for k, d in indeg.items() if d == 0)
    while ready:
        u = ready.pop(0)
        order.append(u)
        for v in succ[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
        ready.sort()
    return order


def producers(spec):
    """(kind, id) -> 会产出它的场景集合。set 写 flag，grant 写 item。"""
    scene_of = {n["id"]: n["scene"] for n in spec["dialogue"]}
    prod = {}
    for n in spec["dialogue"]:
        for c in (n.get("choices") or []):
            eff = c.get("effects") or {}
            for f in (eff.get("set") or {}):
                prod.setdefault(("flag", f), set()).add(scene_of[n["id"]])
            for it in (eff.get("grant") or {}):
                prod.setdefault(("item", it), set()).add(scene_of[n["id"]])
    return {k: sorted(v) for k, v in prod.items()}


def main():
    with open(SPEC, encoding="utf-8") as fh:
        spec = json.load(fh)
    graph = spec["scene_graph"]
    succ = succ_map(graph)
    start = next(n["scene"] for n in spec["dialogue"] if n["id"] == spec["meta"]["start"])

    cycle = find_cycle(succ)
    order = topo_order(graph)
    print(f"环检测：{'有环 ' + str(cycle) if cycle else '无环（DAG）'}  节点={len(graph['nodes'])}")
    print(f"拓扑序（Kahn）：{' -> '.join(order)}")

    prod = producers(spec)
    from_start = reach(succ, start)
    rows, bad = [], 0
    for e in graph["edges"]:
        if not e.get("when"):
            continue
        refs = []
        cond_refs(e["when"], refs)
        for kind, rid in refs:
            ps = prod.get((kind, rid), [])
            ok_scenes = [p for p in ps if p in from_start and p != e["to"] and e["to"] in reach(succ, p)]
            ok = bool(ok_scenes)
            bad += 0 if ok else 1
            rows.append({"edge": f"{e['from']}->{e['to']}", "cond": cond_label(e["when"]),
                         "ref_kind": kind, "ref_id": rid, "producer_scenes": "|".join(ps),
                         "unlock_before_entry": "|".join(ok_scenes), "ok": ok})

    print(f"带条件边={sum(1 for e in graph['edges'] if e.get('when'))}  约束条目={len(rows)}  不可达解锁条件={bad}")
    for r in rows:
        print(f"  [{'OK' if r['ok'] else 'FAIL'}] {r['edge']:<32} 需 {r['ref_kind']}:{r['ref_id']:<16} "
              f"生产于 {r['producer_scenes']:<28} 入口前可满足于 {r['unlock_before_entry'] or '(无)'}")

    os.makedirs(OUT, exist_ok=True)
    with open(os.path.join(OUT, "narr07_constraints.csv"), "w", encoding="utf-8", newline="") as fh:
        w = csv.DictWriter(fh, fieldnames=["edge", "cond", "ref_kind", "ref_id",
                                           "producer_scenes", "unlock_before_entry", "ok"])
        w.writeheader()
        for r in rows:
            w.writerow(r)
    print(f"wrote out/narr07_constraints.csv rows={len(rows)}")

    if cycle:
        print(f"FAIL 场景图有环：{cycle}")
        return 1
    if bad:
        print(f"FAIL 有 {bad} 个解锁条件在进入目标场景前无法满足")
        return 1
    print("OK na_07_3_order_unlock：场景图无环，5 条顺序约束的解锁条件都在入口前可满足")
    return 0


if __name__ == "__main__":
    sys.exit(main())

环检测：无环（DAG）  节点=14
拓扑序（Kahn）：pier -> chapel -> tavern -> counting_house -> watch_post -> lighthouse_base -> market_row -> drowned_bell -> tide_cave -> harbor_office -> lighthouse_top -> breakwater -> fog_gate -> dawn_quay
带条件边=5  约束条目=5  不可达解锁条件=0
  [OK] tavern->counting_house           需 flag:met_hui          生产于 tavern                       入口前可满足于 tavern
  [OK] chapel->watch_post               需 flag:met_shen         生产于 chapel                       入口前可满足于 chapel
  [OK] lighthouse_base->tide_cave       需 flag:knows_tide_rule  生产于 harbor_office|lighthouse_base|pier 入口前可满足于 lighthouse_base|pier
  [OK] tide_cave->harbor_office         需 item:ledger_page      生产于 counting_house               入口前可满足于 counting_house
  [OK] market_row->drowned_bell         需 flag:knows_bell_legend 生产于 chapel|market_row|pier       入口前可满足于 chapel|market_row|pier
wrote out/narr07_constraints.csv rows=5
OK na_07_3_order_unlock：场景图无环，5 条顺序约束的解锁条件都在入口前可满足

edge,cond,ref_kind,ref_id,producer_scenes,unlock_before_entry,ok
tavern->counting_house,flag:met_hui==1,flag,met_hui,tavern,tavern,True
chapel->watch_post,flag:met_shen==1,flag,met_shen,chapel,chapel,True
lighthouse_base->tide_cave,flag:knows_tide_rule==1,flag,knows_tide_rule,harbor_office|lighthouse_base|pier,lighthouse_base|pier,True
tide_cave->harbor_office,item:ledger_page==1,item,ledger_page,counting_house,counting_house,True
market_row->drowned_bell,flag:knows_bell_legend==1,flag,knows_bell_legend,chapel|market_row|pier,chapel|market_row|pier,True