← 图形原理 · 交互课 课题十一 · 寻路 · 第 3 课

剪枝：大部分方向不必看

全课题骨架：寻路不是"找一条路"，而是"给地图上每个位置记一个数"，而记数只有一条规则 —— 从已经确定的那一圈往外推一格，给新格记下它自己的数。
上一课让搜索朝终点偏；可它仍然在每一格上把四邻一个个看过去。这一课问的是更狠的一句： 站在一格上，那四个方向里有没有根本不值得看的？
四段路：先数清"同一个答案背后有多少条路"（26.1）→ 给出"哪个方向被支配"的规矩，并把它与定义逐对核对（26.2）→ 看清"遇到墙角时被迫要补回来的那一步"（26.3）→ 然后量一个不太好听的结果（26.4）。
★ 量出来才敢写的一件事：同一对起终点、代价恰好等于最优的路径，本页这张图上有 2 103 273 000 条 （21 亿条，可手算的小图上与组合数逐一相符）。而这条"被支配的方向"的规矩， 逐对核 3 612 对、一处不一致都没有（判据③）—— 它把全图 13 842 个可选方向剪掉 75.2%。
★ 另一件更要如实说的：把这条规矩直接用在搜索上，会找不到路 —— 只按"继续往前"走，目标上的数是 ∞（判据⑥）；把被迫方向也补回来，仍然是 ∞（判据⑦）。 也就是说这条剪枝局部每一处都能证，整体上却把图剪断了。 本页因此只交付"剪枝是什么、被迫方向是什么"这两件可逐位验证的事， 不做完整的 JPS 搜索 —— 一手源的完整规则是八连通那一套（对角那一步正是"滑过去"的替代路）， 本页与前两课一样只走四邻，如实标注。 保真度：示意 · 等价重现 —— 都是纯图算法，页面现场跑的十条与离线定稿 q113.mjs 同口径， 画面是本页自己的二维软件光栅。 ★ 本页的图与前两课不是同一张（前两课那张图的最优路是一条直线，等代价路径只有 1 条，没有对称性可讲）， 且每步价一律 1（剪枝要求每格代价相同，前两课那张图的泥地价差在这里不成立）。

分段：

（脚本启动中…）

定点观察：（脚本启动中…）

本帧的读数

（脚本启动中…）

26.1 段 · 同一个答案背后有多少条路

本段只增加一样东西：一个"数"的读数（把代价等于最优的路径数出来，画面没有新控件）。 保真度：示意・等价重现。上一课的解是 47 这一个数；可这一个数背后， 可能有很多条不同的路都走到它 —— 本段先把这件事数清楚，因为"对称性"这三个字说的就是它。
★ 数法只用一条递推：一条走到某一格的最优路，其前驱必须满足 d(前驱) + 1 = d(这一格)； 把每一格的最优路径条数设成"它的全部前驱的条数之和"，顺着"闭合顺序"（d 非降）推一遍就得到答案。
★ 实测：本页这张图上，从起点到终点、代价等于最优 43 的路径有 2 103 273 000 条（21 亿条）。 为了能"拿笔算"，本段还在一张空地小图上对照了组合数：3×3 是 C(4,2) = 6、4×3 是 C(5,3) = 10、 5×4 是 C(7,4) = 35，三张都对上了。
★ 一手源把这件事的严重性说得很直白（Harabor & Grastien 2011 引言原话）： "Symmetry in this case manifests itself as paths (or path segments) which share the same start and end point, have the same length and are otherwise identical save for the order in which moves occur. Unless handled properly, symmetry can force search algorithms to evaluate many equivalent states and prevents real progress toward the goal."

输入 一张网格 每步一律 1 四连通，不做对角 要数的东西 代价 = 最优 的那 些路径有多少条 只有一条递推 前驱满足 d(前) + 1 = d(这) 为什么能推一遍 闭合顺序里 d 非降 ⇒ 轮到它时已定稿 见判据① ② ① 数路径条数（本页真跑，逐字） function countShortest(map, start, goal) { const f = makeFlood(map, start).run(); const cnt = new Float64Array(N); cnt[start] = 1; for (const n of f.order) { if (cnt[n] === 0) continue; for (let k = 0; k < 4; k++) { const m = nbr(map, n, k); if (m < 0) continue; if (Math.abs(f.d[n] + 1 - f.d[m]) < 1e-9) cnt[m] += cnt[n]; } } return cnt[goal]; } 高亮那一行就是全部：只有"紧边"才往下传 右列读数 最优代价 C* 43 等代价路径条数 2.103273e+9 （21 亿条） 小图手算对照 3×3 → 6 = C(4,2) 4×3 → 10 = C(5,3) 5×4 → 35 = C(7,4) 画面上那一块 是"走廊"不是线 见判据① ②
件一：26.1 的数法。中间是本页真跑的 countShortest（逐字）， 高亮那一行是它唯一的内容 —— 只有"d(前驱) + 1 = d(这一格)"的边才把条数往下传。 右列是本页这张图的实测：同一个 43，背后有 21 亿条路。
件三 · 表① 数出来的账。"小图手算"那三行是**拿笔能算的**：空地上从一角到对角， 条数就是"横竖怎么排"的组合数。
记的账应然实测结论怎么算类别

定点观察：① 看画面（不用动任何控件）； ② 看高亮的那一片 —— 它是一片走廊，不是一条线；读数里那个条数大得离谱； ③ 结论："最优解"是一个数，可走到它的路有 21 亿条 —— 一个算法如果在这些路上都要看一眼， 那它看的绝大部分是白看的。

26.2 段 · 哪个方向被支配

本段只增加一样东西：一条剪枝规矩（画面换成"每一格被剪掉几个方向"，没有新控件）。 保真度：示意・等价重现。站在 x 上、来路是 p：往旁边那一步， 如果有一条不经过 x、长度一样的替代路，那这一步就是被支配的 —— 不值得看。
★ 规矩写成两句话：① 继续往前那一个方向永远留着； ② 旁边那一个方向只在这一格"退半步"的位置是墙的时候才留（那时替代路不存在）。 代码就是 expandDirs 里那几行。
★ 本段的账是两条独立路线：一条按上面的规矩给，另一条按定义给 —— 把"有没有一条 ≤2 步、绕开 x 的路"逐个数出来（dist2No）。 全图 3 612 对 (p, x) 逐对核，一处不一致都没有。
★ 剪掉的量：全图可走方向合计 13 842 个，被剪掉 10 412 个（75.2%）—— 四分之三的方向不看。一手源把它写成一句（Harabor & Grastien 2011）： "there is little point to evaluating any neighbour highlighted grey as the path induced by such a move is always dominated by (i.e. no better than) an alternative path which mentions p(x) but not x."

输入 站在 x 上 来路是 p 判断一句话 有没有一条不经过 x 的替代路，一样长？ 写成两句话 ① 往前那一个永远留 ② 旁边那个只在 "退半步"是墙时留 怎么知道规矩对 再写一个"按定义"版 两边逐对核 见判据③ ④ ① 本页真跑的剪枝（逐字） function expandDirs(map, p, x) { const out = []; const x0 = x % MW, y0 = (x / MW) | 0; if (p < 0) return [[1, 0], [-1, 0], [0, 1], [0, -1]]; const dx = Math.sign(x % MW - p % MW); const dy = Math.sign(((x / MW) | 0) - ((p / MW) | 0)); if (walk(map, x0 + dx, y0 + dy)) out.push([dx, dy]); if (dx !== 0) { const up = y0 + 1, dn = y0 - 1; if (walk(map, x0, up) && !walk(map, x0 - dx, up)) out.push([0, 1]); if (walk(map, x0, dn) && !walk(map, x0 - dx, dn)) out.push([0, -1]); } else { const rt = x0 + 1, lf = x0 - 1; if (walk(map, rt, y0) && !walk(map, rt, y0 - dy)) out.push([1, 0]); if (walk(map, lf, y0) && !walk(map, lf, y0 - dy)) out.push([-1, 0]); } return out; } 右列读数 逐对核过 3612 对 不一致 0 方向合计 13842 个 被剪掉 10412 个 75.2% 留下 3430 个 见判据③ ④
件一：26.2 的规矩。高亮那一行是"继续往前永远留着"， 下面四行是"旁边那一个什么时候才留下"。右列是两条独立路线的核对结果与剪掉的量。
件三 · 表② 剪枝的账。"两条独立路线"这一行是本段的地基： 规矩版与定义版逐对核，一处不一致都不能有。
记的账应然实测结论怎么算类别

定点观察：① 看画面（不用动控件）；② 看那些被剪掉方向最多的格（最亮的一片）在哪儿； ③ 结论：全图 75.2% 的方向是不必看的，而这条规矩能逐对核对到"零不一致"—— 它每一步都站得住。下一段要看的就是"它有没有什么地方必须例外"。

26.3 段 · 被迫的那一步

本段只增加一样东西：一个三档开关（搜索怎么走：四邻都看 / 只按自然方向 / 补上被迫方向）。 保真度：示意・等价重现。上一段的规矩有一处例外：遇到墙角的时候，旁边那一步不能剪 —— 因为那时"退半步"的位置是墙，替代路根本不存在。本段把那处巷角放大看，并量一件事： 这一处如果不补回来，会怎样。
★ 巷角长这样：从 (19,7) 往上走到 (19,6)（父方向向上），右边 (20,7) 是墙、 (20,6) 正是墙上那个口子。这时要看的方向是 [[0,-1],[1,0]] —— 两个：继续向上，加上被"逼"出来的向右。只按自然方向则只有 [[0,-1]]， 于是永远拐不进口子。
★ 三档的实测（读数就在画面下）：四邻都看 → 已定 323 格、目标上 43（对）； 只按自然方向 → 已定 44 格、目标 ∞（找不到路）； 补上被迫方向 → 已定 44 格、目标 仍然 ∞。最后这一档是本课最该记住的数， 下一段就讲它。

输入 上一段的规矩 + 一处例外 巷角长什么样 (19,7) → (19,6) 右边是墙的尽头 (20,7) 墙 (20,6) 口 这时要看几个方向 两个：上 + 右（被迫） 只按自然方向 ⇒ 一个 不补会怎样 拐不进口子 ⇒ 到不了 目标上的数是 ∞ 见判据⑥ ⑦ ① 本页真跑的对照（逐字）：只按自然方向那一版 function naturalOnly(map, p, x) { const x0 = x % MW, y0 = (x / MW) | 0; if (p < 0) return [[1, 0], [-1, 0], [0, 1], [0, -1]]; const dx = Math.sign(x % MW - p % MW); const dy = Math.sign(((x / MW) | 0) - ((p / MW) | 0)); if (!walk(map, x0 + dx, y0 + dy)) return []; return [[dx, dy]]; } ② 两版共用同一个搜索（只看 dirsFn 给的方向） function prunedSearch(map, start, goal, dirsFn) { // …取 f 最小的那一圈与第 2 课一字不差 const keep = dirsFn(map, par[n], n); /* ② 只往这几个方向推 */ // …其余同第 2 课 } 三档实测 四邻都看 已定 323 目标 43 ✓ 只按自然方向 已定 44 目标 ∞ ✗ 补上被迫方向 已定 44 目标 ∞ ✗ 巷角要看的方向 2 个 （自然只有 1 个） 见判据⑥ ⑦
件一：26.3 的例外与对照。中间上半是"只按自然方向"那一版（逐字）， 下半是两版共用的搜索骨架。右列第三行是本课的关键数：把被迫方向补回来，目标上的数还是 ∞。
件三 · 表③ 三档的账。注意最后两行 —— 它们的"已定"一样、目标上的数也一样是 ∞， 补了被迫方向也没有救回来，这就是下一段的入口。
记的账应然实测结论怎么算类别

定点观察：① 在「搜索怎么走」那三个按钮之间切； ② 看读数里"已定"与"目标上的数"两项 —— 第一档 323 格 / 43，后两档都停在 44 格 / ∞； ③ 结论：只按自然方向会断在巷角；补上被迫方向也还是断的 —— 这条规矩"每一步都对"，可它把整张图剪断了。

26.4 段 · 把它用在搜索上会怎样

本段只增加一样东西：一个两档开关（看哪个：43 步的路径 / 压缩后 4 段）。 保真度：示意・等价重现。上一段那个结果值得单独说清楚：这条剪枝规则局部每一处都能证， 整体上却不安全 —— 把整张图按它剪完，起点到终点就不通了。
★ 为什么？因为"被支配"这句话是局部说的：它只保证"这一步有等长的替代路"， 却没保证那条替代路在剪完之后的图里还在。四连通里没有对角，"滑过去"的那一步不存在， 替代路就会一环一环地被剪掉。一手源的完整规则是八连通那一套（对角那一步正是这条替代路）， 本页与前两课一样只走四邻，所以不做完整的 JPS 搜索。
★ 那这一段的交付是什么？是同一件事的安全版本：既然"直接在搜索上剪"不行， 那就在已经拿到的最优路径上剪 —— 把同一段直线上的一串格压成一个点，只留转角。 实测：这条 43 步的最优路径，压完只剩 5 个点、4 段： (5,12) → (19,12) → (19,6) → (36,6) → (36,12)； 而各段长度之和仍然恰好是 43 —— 代价一位没变。
★ 一手源里那句 JPS 的招牌台词说的正是这件事（Harabor & Grastien 2011 摘要）： "Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded." —— 本页把"中间那些格不必记"这件事在路径上坐实了（43 步只剩 5 个点）， 但在搜索上如实做了边界说明。

输入 一条最优路径 43 步、代价 = C* 要留下哪些 方向变了的那一格 也就是"转角" 为什么代价不变 同一段直线上每步都是 1 压完段长之和 = 原步数 边界（如实） 在搜索上直接剪不安全 完整规则是八连通那套 本页不做完整 JPS 见判据⑧ ⑩ ① 本页真跑的压缩（逐字） function compressPath(map, path) { if (path.length <= 2) return path.slice(); const out = [path[0]]; for (let k = 1; k + 1 < path.length; k++) { const a = path[k - 1], b = path[k], c = path[k + 1]; const d1x = Math.sign(b % MW - a % MW); const d1y = Math.sign(((b / MW) | 0) - ((a / MW) | 0)); const d2x = Math.sign(c % MW - b % MW); const d2y = Math.sign(((c / MW) | 0) - ((b / MW) | 0)); if (d1x !== d2x || d1y !== d2y) out.push(b); } out.push(path[path.length - 1]); return out; } 压缩后的点（本页实测）： (5,12) → (19,12) → (19,6) → (36,6) → (36,12) 段长和 14+6+17+6 = 43 = 原步数 ✓ 右列读数 原路径 43 步 压缩后 5 个点 / 4 段 压缩比 10.75 段长之和 43 = 原步数 代价一位没变 搜索上直接剪 不安全（26.3） 见判据⑧ ⑩
件一：26.4 的压缩。中间是本页真跑的 compressPath（逐字）， 高亮那一行就是全部 —— 方向变了就留下。右列是实测：43 步压成 4 段，代价一位没变。
件三 · 表④ 压缩的账。最后一行"段长之和"是这条压缩唯一的正当性来源： 它必须恰好等于原来的步数。
记的账应然实测结论怎么算类别

定点观察：① 在「看哪个：43 步的路径 / 压缩后 4 段」之间切； ② 看高亮的那条线怎么从"一格一格的 43 步"变成"四段折线"，同时盯住读数里"段长之和"那一项； ③ 结论：43 步里真正"必须记下"的只有 4 个转角 —— 但这件事只在路径上成立；把它搬到搜索上就直接把图剪断了（26.3 实测）。

本课的收尾

这一课问的是"站在一格上，四个方向里有没有不值得看的"。答案分两半，都要记：
① 有 —— 那条"被支配"的规矩把全图 75.2% 的方向剪掉，而且逐对核对零不一致； 在路径上，43 步只剩 4 个转角。
② 但不能直接照搬到搜索上 —— 局部每一处都对，整体却把图剪断（补上被迫方向也不行）； 一手源的完整规则是八连通那一套。
往下的缺口：上面三课全都建在方格上，而且是"一个人问一次"。下一课（第 4 课 · 流场） 换的是问题的规模：一千个人朝同一个终点走，逐个跑搜索就废了 —— 得让整张地图一次算完，之后每个人只读一格的方向。

自检面板

等待脚本…