narrative

1.2 路径的表示与编码

同一条路径可以写成三种编码：人可读的规范串、机器可比的紧凑整数元组、以及只对状态算的 FNV-1a 摘要。本节给出三种编码的构造规则，并用 Python 与 TypeScript 两侧对同一条路径算出逐位一致的结果，说明摘要绑定的是编码串而不是文本。

Leeting Yan 9 分钟阅读 4218 字

站内那篇独立游戏的叙事设计与分支对话 （约 1076 行）讲的是玩家选择体验：怎么让一个选择读起来有意义、怎么让分支不显得敷衍，配的是散文与清单，代码不可跑。本章把同一批问题编码成可算对象——上一节把一次通关拆成了三种表示，这一节给每一种表示一个固定的编码，让「两条路径是不是同一条」变成一个 32 位整数能不能相等的问题。

路径要被存储、被比较、被跨语言对照，就必须先规范化：键怎么排、空值怎么写、路径怎么连、摘要对什么做。这一节把这三件事定死。

三种编码，三个用途

规范串是 node|aff|flag|item|path 形态，人可读、可 diff、可落日志，样例 388 字符；整数元组是 [node_idx, a0..a3, flag_bits, item_bits, path_len]，机器可比、可当数组下标，样例 8 个整数；摘要是一个 32 位整数，用于判等、建索引、跨语言对照。三者不是替代关系：规范串最贵但最透明，元组最紧凑但不可读，摘要最省但会碰撞。判两条路径相等用摘要，解释它们为什么不同用规范串，做批量统计用元组。

规范串：把状态排成一个固定顺序

规范串把状态的五个字段按固定顺序拼起来，中间用 | 分隔：节点名、四个好感度（键名排序，k=v 逗号连接）、置位 flag（只列亮的，排序）、持有物品（只列有的，排序）、路径（> 连接）。排序是关键——对象的键序在不同语言、不同运行里不保证一致，若按插入顺序拼，同一个状态在 Python 与 TS 下会拼出两个不同的串，所以两侧都强制「键名排序 + k=v 逗号连接」。空值也要约定：flag 只列置位的、物品只列持有的，没置位的键根本不出现——这样「18 个 flag 全 0」和「9 个物品全 0」都收敛成空段。

整数元组：把状态压成 8 个整数

规范串是给人看的，机器比它更想要一组定长整数。整数元组把同一状态压成 8 个整数，位置固定：

位置含义
0节点下标（在 spec.dialogue 里的序号）
1–4四个好感度（yan / hui / shen / mu，键名排序）
5flag 位图：18 个 flag 按排序压进一个整数
6item 位图：9 个物品按排序压进一个整数
7路径长度

位图是这里的压缩点：18 个布尔 flag 本来要 18 个字段，压进一个整数只需 18 个二进制位；9 个物品同理。元组定长 8，不随规格里的 flag 数变化——这是它比规范串更适合当数组下标的原因。代价是可读性：71562 这个数单看没有意义，要把它拆回位图才知道亮了哪几个 flag。

摘要：只对状态做，不对文本做

摘要是 FNV-1a 32 位，输入是编码串（规范串或元组串），输出是一个 32 位整数。这里有一条本套贯穿始终的口径：摘要只对状态做，不对文本做。原因是文本涉及编码与换行：同一句话在不同编码、不同换行约定下字节不同，把「文本逐字相等」当判据是不可靠的（这是卷一 1.3 节定下的口径）。状态全是整数，序列化没有歧义，所以摘要稳定。注意一个细节：摘要绑定的是编码串，不是状态本体——同一个状态用规范串算和用元组算，会得到两个不同的整数（样例里是 4162796975 与 3738584881）。用摘要判等时，必须同时声明用的是哪种编码。

S 层：Python 侧算出三种编码

sim/nm_01_2_encode.py 给「1 条确定性路径 + 20 条采样路径」各算出规范串、整数元组与两个摘要，落 out/nm_01_2_encode.json。推进与规范串复用卷一 sim/na_02_digest.py（只读 import）。

#!/usr/bin/env python3
# file: sim/nm_01_2_encode.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/nm_01_2_encode.py
"""卷三 1.2 路径的表示与编码（S 层，Python 侧）：给同一个状态算出三种编码。

  规范串     canonical = "node|yan=..,hui=..,|flag,..|item,..|n1>n2>.."   人可读
  整数元组   tuple     = [node_idx, yan,hui,shen,mu, flag_bits, item_bits, path_len]
  FNV-1a 摘要 digest   = 32 位整数，只对**状态**做，不对文本做

落 out/nm_01_2_encode.json；TS 侧 core/test/nm_01_2_encode.test.ts 读同一份产物，
用 engine.ts 重算 canonical 与 digest、用 nm_01_2_encode.ts 重算整数元组，逐条逐位比对。
推进与规范串复用卷一 sim/na_02_digest.py（只读 import）。全部整数，不出现浮点。
"""
from __future__ import annotations

import json
import os
import sys

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
from na_02_digest import cond_ok, init_state, node_by_id, apply_choice, canonical, sample_paths  # noqa: E402

ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
JSON_PATH = os.path.join(OUT, "nm_01_2_encode.json")
SEED, SAMPLE_N, MASK32 = 20261016, 20, 0xFFFFFFFF


def load_spec() -> dict:
    with open(os.path.join(ROOT, "config/story_spec.json"), encoding="utf-8") as fh:
        return json.load(fh)


def fnv1a(text: str) -> int:
    h = 2166136261
    for ch in text:
        h = (h ^ ord(ch)) & MASK32
        h = (h * 16777619) & MASK32
    return h


def encode_tuple(spec: dict, s: dict) -> list[int]:
    """紧凑整数元组：节点下标 + 四个好感度 + flag 位图 + item 位图 + 路径长度。"""
    node_idx = next(i for i, n in enumerate(spec["dialogue"]) if n["id"] == s["node"])
    aff = [s["aff"][v] for v in sorted(s["aff"])]
    flag_bits = sum((1 << i) for i, f in enumerate(sorted(s["flags"])) if s["flags"][f])
    item_bits = sum((1 << i) for i, it in enumerate(sorted(s["items"])) if s["items"][it])
    return [node_idx, *aff, flag_bits, item_bits, len(s["path"])]


def walk(spec: dict) -> list[str]:
    """确定性策略：每步选第一个条件成立的选项，返回选择序列。"""
    s, trail = init_state(spec), []
    for _ in range(64):
        cur = node_by_id(spec, s["node"])
        if cur.get("ending"):
            break
        opts = [c for c in (cur.get("choices") or []) if cond_ok(c.get("when"), s)]
        if not opts:
            break
        trail.append(opts[0]["id"])
        s = apply_choice(spec, s, opts[0]["id"])
    return trail


def main() -> int:
    spec = load_spec()
    seqs = [walk(spec), *sample_paths(spec, SAMPLE_N, SEED)]

    rows = []
    for i, p in enumerate(seqs):
        s = init_state(spec)
        for cid in p:
            s = apply_choice(spec, s, cid)
        t = encode_tuple(spec, s)
        ts = ",".join(str(x) for x in t)
        rows.append({"i": i, "choices": p, "canonical": canonical(s), "canonical_len": len(canonical(s)),
                     "tuple": t, "tuple_str": ts, "digest": fnv1a(canonical(s)),
                     "digest_tuple": fnv1a(ts), "node": s["node"],
                     "ending": node_by_id(spec, s["node"]).get("ending", "")})

    known = {n["id"] for n in spec["dialogue"]}
    for r in rows:
        for part in r["canonical"].split("|")[1].split(","):
            assert 0 <= int(part.split("=")[1]) <= 100, "好感度越界"
        assert r["node"] in known, f"未知节点 {r['node']}"

    r0 = rows[0]
    print(f"spec={spec['meta']['title']}  路径数 {len(rows)}（1 确定性 + {SAMPLE_N} 采样）")
    print(f"样例（确定性路径）：node={r0['node']} ending={r0['ending']}")
    print(f"  规范串   {r0['canonical']}")
    print(f"  规范串长 {r0['canonical_len']} 字符")
    print(f"  整数元组 {r0['tuple_str']}")
    print(f"  元组含义 [node_idx, yan,hui,shen,mu, flag_bits, item_bits, path_len]")
    print(f"  digest(规范串)   {r0['digest']:>10}")
    print(f"  digest(整数元组) {r0['digest_tuple']:>10}")
    print(f"元组长度恒为 {len(r0['tuple'])}（18 flag -> 1 个位图整数，9 item -> 1 个位图整数）")
    print(f"摘要去重：{len({r['digest'] for r in rows})} / {len(rows)} 条（规范串口径）")
    print(f"两条摘要是否相同（同状态不同编码）：{r0['digest'] == r0['digest_tuple']}")

    os.makedirs(OUT, exist_ok=True)
    with open(JSON_PATH, "w", encoding="utf-8") as fh:
        json.dump(rows, fh, ensure_ascii=False, indent=1)
        fh.write("\n")
    print(f"wrote out/nm_01_2_encode.json rows={len(rows)}")
    print("OK nm_01_2_encode：三种编码已落盘，待 TS 侧逐位比对")
    return 0


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

本机实跑 /opt/homebrew/bin/python3 sim/nm_01_2_encode.py：

spec=雾港夜航  路径数 21（1 确定性 + 20 采样）
样例（确定性路径）：node=e_lit ending=灯守
  规范串   e_lit|hui=60,mu=65,shen=50,yan=65|cave_explored,found_yan_journal,knows_tide_rule,knows_yan_missing,met_hai,met_hui,met_mu,saw_lighthouse_light|journal,ledger_page,rope_knot,salt_letter|d_pier_1>d_pier_2>d_tavern_1>d_tavern_2>d_tavern_3>d_hub_a1>d_ch_1>d_ch_2>d_ch_3>d_hub_a2>d_lb_1>d_lb_2>d_lb_3>d_tc_1>d_tc_2>d_tc_3>d_ho_1>d_ho_2>d_ho_3>d_hub_b2>d_lt_1>d_lt_2>d_lt_3>d_dq_1>d_dq_2>e_lit
  规范串长 388 字符
  整数元组 43,60,65,50,65,71562,212,26
  元组含义 [node_idx, yan,hui,shen,mu, flag_bits, item_bits, path_len]
  digest(规范串)   4162796975
  digest(整数元组) 3738584881
元组长度恒为 8（18 flag -> 1 个位图整数，9 item -> 1 个位图整数）
摘要去重：21 / 21 条（规范串口径）
两条摘要是否相同（同状态不同编码）：False
wrote out/nm_01_2_encode.json rows=21
OK nm_01_2_encode：三种编码已落盘，待 TS 侧逐位比对

P 层：同一条路径跨语言逐位一致

TypeScript 侧的整数元组编码写在 core/src/inkwell/nm_01_2_encode.ts（只 import 既有内核 engine.ts，不改动它）：

// file: core/src/inkwell/nm_01_2_encode.ts
// tier: P
// verify: node --test 'core/test/nm_01_2_encode.test.ts'
// 卷三 1.2（P 层）：紧凑整数元组编码 + 通用 FNV-1a。只 import 既有内核 ./engine.ts。

import { canonical, digest } from "./engine.ts";
import type { Spec, State } from "./engine.ts";

export { canonical, digest };

/** FNV-1a 32 位，对任意字符串（此处只喂状态编码串，不喂文本）。 */
export function fnv1a(text: string): number {
  let h = 2166136261;
  for (let i = 0; i < text.length; i += 1) {
    h = (h ^ text.charCodeAt(i)) >>> 0;
    h = Math.imul(h, 16777619) >>> 0;
  }
  return h >>> 0;
}

/** 紧凑整数元组：[node_idx, yan,hui,shen,mu, flag_bits, item_bits, path_len]。 */
export function encodeTuple(spec: Spec, s: State): number[] {
  const nodeIdx = spec.dialogue.findIndex((n) => n.id === s.node);
  const aff = Object.keys(s.aff).sort().map((k) => s.aff[k]);
  let flagBits = 0;
  Object.keys(s.flags).sort().forEach((f, i) => {
    if (s.flags[f]) flagBits |= 1 << i;
  });
  let itemBits = 0;
  Object.keys(s.items).sort().forEach((it, i) => {
    if (s.items[it]) itemBits |= 1 << i;
  });
  return [nodeIdx, ...aff, flagBits, itemBits, s.path.length];
}

export function tupleStr(t: number[]): string {
  return t.join(",");
}

export function digestTuple(t: number[]): number {
  return fnv1a(tupleStr(t));
}

门禁测试读 Python 落盘的同一份 out/nm_01_2_encode.json，逐条重算并断言逐位一致：

// file: core/test/nm_01_2_encode.test.ts
// tier: P
// verify: node --test 'core/test/nm_01_2_encode.test.ts'
// 卷三 1.2（P 层门禁）：Python 落盘的三种编码与 TS 侧逐位一致。

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 { replay, canonical, digest } from "../src/inkwell/engine.ts";
import type { Spec } from "../src/inkwell/engine.ts";
import { encodeTuple, tupleStr, digestTuple, fnv1a } from "../src/inkwell/nm_01_2_encode.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 rows = JSON.parse(readFileSync(join(ROOT, "out/nm_01_2_encode.json"), "utf8")) as {
  i: number;
  choices: string[];
  canonical: string;
  canonical_len: number;
  tuple: number[];
  tuple_str: string;
  digest: number;
  digest_tuple: number;
  node: string;
  ending: string;
}[];

test("21 条路径的规范串、摘要、整数元组与 Python 逐位一致", () => {
  assert.equal(rows.length, 21);
  for (const r of rows) {
    const s = replay(spec, r.choices);
    assert.equal(s.node, r.node, `#${r.i} 终点节点不一致`);
    assert.equal(canonical(s), r.canonical, `#${r.i} 规范串不一致`);
    assert.equal(canonical(s).length, r.canonical_len, `#${r.i} 规范串长度不一致`);
    assert.equal(digest(s), r.digest, `#${r.i} 规范串摘要不一致`);
    const t = encodeTuple(spec, s);
    assert.deepEqual(t, r.tuple, `#${r.i} 整数元组不一致`);
    assert.equal(tupleStr(t), r.tuple_str, `#${r.i} 元组串不一致`);
    assert.equal(digestTuple(t), r.digest_tuple, `#${r.i} 元组摘要不一致`);
  }
});

test("整数元组长度恒为 8，节点下标与好感度都在范围内", () => {
  for (const r of rows) {
    assert.equal(r.tuple.length, 8);
    assert.ok(r.tuple[0] >= 0 && r.tuple[0] < spec.dialogue.length, `#${r.i} 节点下标越界`);
    for (let k = 1; k <= 4; k += 1) {
      assert.ok(r.tuple[k] >= 0 && r.tuple[k] <= 100, `#${r.i} 好感度越界`);
    }
  }
});

test("摘要绑定的是编码串而非状态本体：两种编码得到两个不同的整数", () => {
  const r0 = rows[0];
  const s = replay(spec, r0.choices);
  assert.equal(digest(s), r0.digest, "engine.ts 的 digest 应等于规范串摘要");
  assert.equal(fnv1a(canonical(s)), r0.digest);
  assert.notEqual(r0.digest, r0.digest_tuple, "两种编码串不同，摘要本不应相等");
});

本机实跑 node --test 'core/test/nm_01_2_encode.test.ts'：

✔ 21 条路径的规范串、摘要、整数元组与 Python 逐位一致 (3.21175ms)
✔ 整数元组长度恒为 8，节点下标与好感度都在范围内 (0.169458ms)
✔ 摘要绑定的是编码串而非状态本体：两种编码得到两个不同的整数 (0.159209ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 154.181042

判读：编码定死之后，路径才可比

21 条路径三种编码全部跨语言一致。 这说明编码规则被两侧同构地实现了：键名排序、位图顺序、路径连接符、溢出语义（Python & 0xFFFFFFFF 对应 TS Math.imul）逐条对齐。任何一处不一致，测试都会在具体那条路径上报出差异。

元组长度恒为 8，与规格里的 flag / item 数量无关。 位图把 18 个 flag、9 个物品各压成一个整数，所以元组是定长的。这带来一个直接的工程好处：元组可以直接当数组下标或哈希键，而规范串不行。

两个摘要不相等是设计而非缺陷。 4162796975（规范串）与 3738584881（元组）来自同一个状态的两种编码串，输入不同，输出自然不同。摘要绑定的是编码串，不是状态本体——用摘要判等时必须声明编码口径，否则「两个摘要不等」会被误读成「两个状态不等」。

这里的每一个数都是 proxy 口径下的结构量——规范串长度、元组长度、摘要，只用于判等与相对比较，不声称任何体验结论。

自检表

检查项合格标准本节实测
三种编码齐全规范串 / 整数元组 / 摘要各有定义三张表
规范串可复现键名排序、空段约定固定388 字符
元组定长不随 flag 数变化恒 8
摘要口径只对状态做，不对文本做声明并用两个摘要对照
跨语言一致Python 与 TS 逐位相同21 / 21
说法诚实摘要绑定编码串，不绑定状态本体两个摘要不等

编码定死之后，「两条路径是不是同一条」就变成了一个整数能不能相等的问题。但还差最后一块地基：同一条路径，重复走两遍，状态是不是逐位一样——也就是回放。下一节把「复现」这件事钉死。

阅读导航：上一节：1.1 一次通关的轨迹 · 下一节：1.3 路径的回放与复现 。

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「narrative」更多文章

  1. 15.3 规模告警
  2. 15.2 求值与遍历的开销
  3. 15.1 规格规模的增长