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

泛洪：把「找一条路」换成「给每一格记一个数」

全课题骨架：寻路不是"找一条路"，而是"给地图上每个位置记一个数，然后从任意一点顺着这个数往下走" —— 而记数这件事只有一条规则：从已经确定的那一圈往外推一格，给新格记下它自己的数。
四段路：先把规则写成"取最小的那一格、推它的四个邻居"（24.1）→ 给每一格一个价，规则一个字不改（24.2）→ 问一句"什么时候可以停"（24.3）→ 把这同一张数表换一个看法：路就是"从终点往回走下坡"（24.4）。
★ 量出来才敢写的一件事：泛洪算出来的那张数表，与"按层一圈圈扩"这条完全独立的路线逐格相同 —— 965 个可走格，一位不差（实测 965 / 965）。 以及：把泥地标成"贵 4 倍"之后，最短路自己改道了 —— 单位权下 31 步穿 7 格泥，带权下 47 步一格泥都不穿； 老那条路线按带权算要 52，比最优的 47 贵 5。 保真度：示意 · 等价重现 —— 泛洪、参考解、连通块、梯度下坡都是纯图算法 （页面现场跑的十条与离线定稿 q241.mjs 同口径），画面是本页自己的二维软件光栅 （逐格填色 + 网格线 + 路径折线），不是任何引擎或导航库的内部实现。 ★ 本页的优先队列用"线性扫一遍取最小"实现（1000 个格，最直白也最可复算）； 不做 JPS / NavMesh / 流场（那是后面四课），也不做对角走位（只有四邻）。

分段：
推进： ｜在画面上点一下可以改一格地形（墙 ↔ 空地）

（脚本启动中…）

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

本帧的读数

（脚本启动中…）

24.1 段 · 从起点往外推一圈

本段只增加一样东西：把"路"换成一张数表（读者只动「单步 / 跑到底」，画面上一格一格地长出数来）。 保真度：示意 · 等价重现。读者默认以为寻路是"找一条线"；这里换掉这个想法： 先给每一格记一个数 d（从起点走到这儿花了多少），路只是这张表的一个副产品。 记数只有两条动作：① 从"待定"里取出 d 最小的那一格，把它定为"已定"；② 把它的四个邻居按 cand = d + w 记上数——第二条就是全课题的那条唯一规则。
★ 一手源把这两条写成一句话（Dijkstra 1959 原话）："the minimal paths from P to the other nodes are constructed in order of increasing length until Q is reached."（最短路径是按长度递增的顺序被构造出来的，直到 Q 被取到。）
★ 本段的账是两条独立路线：一条是"取最小的往外推"，另一条是"按层一圈圈扩"（BFS 层数）—— 两者不共用任何中间量，965 个可走格逐格相同（实测 965 / 965，一个不同都没有）。

输入 一张网格 40 × 25 格 一格"能走 / 不能走" 要记三样 d 到起点花了多少 par 它是从哪儿来的 done 已定，不再变 两圈 已定（闭合） 待定（有数没定） 一条约定 每轮取 d 最小的 取出来就成了"已定" 见判据① ② ③ ① 记数那一步：这是本页真跑的 step（逐字） st.step = function () { let n = -1, best = Infinity; for (let i = 0; i < N; i++) if (!done[i] && d[i] < best) { best = d[i]; n = i; } if (n < 0) return false; done[n] = 1; order.push(n); st.settled++; front--; if (opts.early && n === opts.goal) return false; for (let k = 0; k < 4; k++) { const m = nbr(map, n, k); if (m < 0) continue; const w = wOf(map, m, opts.weighted); if (w === Infinity) continue; const cand = d[n] + w; if (cand < d[m]) { if (d[m] === Infinity) front++; d[m] = cand; par[m] = n; } } /* 这一圈推完 */ if (front > peak) { peak = front; st.peak = peak; } return true; }; 右列读数 可走格 965 / 1000 墙 35 d(目标) 31 步 最大 d 46 待定峰值 36 格 与 BFS 参考解 965 / 965 见判据①
件一：24.1 的记数那一步。左列是要记的三样账与那条唯一约定， 中间是本页真跑的 st.step（逐字，含注释），右列是实测。 注意中间那两行 const cand = d[n] + w; 与 d[m] = cand; —— 全课题后面四课换的都只是这两行的"数"是什么，推邻居这个动作一个字都不改。
件三 · 表① 泛洪的账（单位权）。每一行都是可手算或可独立复核的： "与按层 BFS 参考解逐格相同"这一行用的是另一条完全独立的路线（按层扩），不是把同一份代码再跑一遍。
记的账应然实测结论怎么算类别

定点观察：① 反复按「单步」（走完再按一次会从头重来）； ② 看画面里浅色那一圈（待定）怎么长、深色那一块（已定）怎么跟着吃过去， 以及读数里"已定 / 待定"两个数怎么变； ③ 结论：被定为"已定"的顺序是按 d 从小到大排的 —— 这就是"路"能被读出来的原因， 而它其实是这张数表的一个副产品。

24.2 段 · 让每一格有自己的价

本段只增加一样东西：边权（读者只动「地形权重」那对按钮，别的一切与 24.1 相同）。 保真度：示意 · 等价重现。上一段里每一格都"值一步"，可真实地图不是这样：泥地难走、草地好走。 本段的动作只有一处：把 w 从"恒等于 1"换成"看这一格是什么地形"—— 规则本身（cand = d[n] + w）一个字符都没改。
★ 结果很直观，但它值得单独说一遍：最短路自己改道了。单位权下 31 步、要穿 7 格泥； 把泥地标成 4 倍之后，最短路变成 47 步、一格泥都不穿。 把老那条路线拿来按带权算一遍是 52，比最优的 47 贵 5 —— 也就是说泛洪不是"沿旧路径打补丁"，而是重新算了一遍，并且找到了更便宜的走法。
★ 一句话点题：这一步之后，"最短"这两个字的含义从步数最少变成了代价最小； 本页后面所有提到"最短"的地方，都是指后者。

输入 同一张网格 + 每一格自己的价 三种地形 空地 × 1 泥地 × 4 墙 ∞（不可走） 规则只换一处 cand = d[n] + w 含义变了 不是"走了几步" 而是"花了多少" ⇒ 多走几步换少花钱 见判据④ ① 价从哪来（本页真跑的 wOf，逐字） function wOf(map, i, weighted) { const t = map[i]; if (t === WALL) return Infinity; return (t === MUD && weighted) ? 4 : 1; } ② 规则本身：下面四行与 24.1 一字不差 const w = wOf(map, m, opts.weighted); if (w === Infinity) continue; const cand = d[n] + w; if (cand < d[m]) { d[m] = cand; par[m] = n; } ③ 于是路自己改道（右下是实测） 旧路：31 步，穿 7 格泥（按带权算 = 52） 新路：47 步，穿 0 格泥（ = 47） 泛洪不是打补丁，是重新算了一遍。 右列读数 单位权 d = 31 · 步 31 穿泥地 7 格 带权档 d = 47 · 步 47 穿泥地 0 格 老路线按带权算 52（贵 5） 逐格加价 = 47 与 d(目标) 相等 见判据④ ⑧
件一：24.2 只改了"价从哪来"（上半），规则那四行（下半）与 24.1 一字不差。 右下那两条路径就是本页实测的两条：旧路按带权算 52，新路 47。
件三 · 表② 边权的账。"老路线按带权算"这一行是把上一条路径拿回来重新计价—— 它证明的不是"路径变长了"，而是泛洪换了一条路。
记的账应然实测结论怎么算类别

定点观察：① 在「地形权重：关 / 开」之间来回切； ② 看画面里那条高亮的路径 —— 数一数它穿过的深色泥地格； ③ 结论：权重一开，路径自己绕开了泥地，代价从 52 掉到 47， 而这一步只改了"价从哪来"这一个地方。

24.3 段 · 什么时候可以停

本段只增加一样东西：早退（读者只动「停止条件」那对按钮）。 保真度：示意 · 等价重现。前两段一直把整张地图算完 —— 可读者要的只是到目标那一格。 本段加的那一行是：从"待定"里取出来的那一格正好是目标格时，就停。
★ 凭什么停？因为取的时候是按 d 从小到大取的：目标格的 d 已经是最小的那个数， 后面还没被取的格 d 只会更大，它们不可能再给出更小的目标值。 换句话说："取到目标 ⇒ 它的数已经定了"，这不是近似，是规则本身的性质。
★ 省下来的账是实打实的：跑满全图要定 965 格，到目标就停只定 774 格， 省下 191 格（19.8%）；而两档的 d(目标) 都是 47，一个字都没差。
★ 一手源原话（HN R 1968）把顺序也写清了："Select the open node n whose value of f is smallest."—— 取最小的那一个，这就是"能停"的全部依据。

输入 同一个泛洪 + 什么时候可以停 停的条件 取出的是目标格 为什么能停 取的是 d 最小的那些 还没取的只会更大 ⇒ 现在停就是最优 代价 少定一些格 换来少等一会儿 不是近似：数没变 见判据⑤ ① 本段只加这一行（本页真跑，逐字） st.step = function () { let n = -1, best = Infinity; for (let i = 0; i < N; i++) if (!done[i] && d[i] < best) { best = d[i]; n = i; } if (n < 0) return false; done[n] = 1; order.push(n); st.settled++; front--; if (opts.early && n === opts.goal) return false; // …（下面推四邻那几行与 24.1 一字不差） }; ② 为什么这一行是对的 取的时候是按 d 从小到大取的 ⇒ 目标格的 d 已经是最小的那个 还没取的格 d 只会更大 ⇒ 不可能更优 一手源：Select the open node n whose value of f is smallest.（HN R 1968） 右列读数 跑满全图 已定 965 格 d(目标) 47 到目标就停 已定 774 格 d(目标) 47 省下 191 格（19.8%） 两个 d(目标) 相等 ⇒ 没破坏最优 见判据⑤
件一：24.3 加的就是中间那个高亮行。下面三行是"为什么它能停"的推理链， 右列是跑满与早退两档的实测：少定 191 格，而 d(目标) 一位不差。
件三 · 表③ 早退的账。两档的 d(目标) 必须相等 —— 这是"早退"这个手法唯一的正当性来源。
记的账应然实测结论怎么算类别

定点观察：① 在「跑满全图 / 到目标就停」之间来回切，并按「单步」看过程； ② 看读数里"已定"那个数停在哪儿，以及 d(目标) 那一项； ③ 结论：早退把要定的格从 965 降到 774，而目标那一格上的数一模一样 —— 这不是"近似解"，是"同一个答案、更早拿到"。

24.4 段 · 把这张数表当地形看（第二视角）

本段只增加一样东西：看法（读者只动「看法」那对按钮，一个数都不重算）。 保真度：示意 · 等价重现。前三段把 d 当成"记在格子上的一笔账"； 现在换一个正交的看法：把 d 当成高度——起点是谷底（0），越远越高，墙是悬崖。 在这个地形上，"路"就是一件很自然的事：从终点出发，每一步都往更小的 d 走，一路下坡就回到起点。
★ 这两条读法是同一张表的两种用法：24.1–24.3 是"从起点往外记"， 本段是"从终点往里读"（par 往回回溯是另一条等价读法，两条实测步数相等：47 = 47）。
★ 实测的下降序列（每 8 格取一个）：47 → 39 → 31 → 23 → 15 → 7 → 0，全程严格递减、最后恰好落在 0。 为什么一定下得去？因为每一格的 d 都是"某个邻居的 d 加上一步"得来的 —— 所以那一格必然存在一个更小的邻居，只要一直挑最小的那个，就一定能走到起点，不会卡在半路。

输入 同一张数表 不重算，换看法 把它当高度 起点是谷底（0） 远处是坡上 路是什么 从终点往回 每一步都往更小走 为什么下得去 每格的数都来自 某个邻居 + 一步 ⇒ 一定有更小的邻居 见判据⑩ ① 本段的读法（本页真跑，逐字） function gradientPath(f, start, goal) { const out = [goal]; let n = goal, g = 0; while (n !== start && g++ < MW * MH + 4) { let best = -1, bd = f.d[n]; for (let k = 0; k < 4; k++) { const m = nbr(f.map, n, k); if (m < 0) continue; if (f.d[m] < bd - 1e-9) { bd = f.d[m]; best = m; } } if (best < 0) break; out.push(best); n = best; } return out; } ② 两条读法读的是同一张表 24.1–24.3：从起点往外「记」 24.4：从终点往里「读」 右列读数 下坡路径 47 步 = 回溯路径步数 d 序列 47 → 39 → 31 → 23 → 15 → 7 → 0 严格递减 每一格都更小 落在起点上 d = 0 见判据⑩
件一：24.4 的读法。中间那个循环里 没有堆、没有"已定"、没有任何账本 —— 它就是"每一步挑一个更小的邻居"。右列是实测：47 步、严格递减、落在 0。
件三 · 表④ 第二视角。前三段那张表的另一种用法：把"记"换成"读"， 两条读法给出的路径长度必须相等（实测 47 = 47）。
记的账应然实测结论怎么算类别

定点观察：① 在「两圈着色 / 数表热力 + 下坡」之间切换； ② 看画面 —— 热力越亮说明 d 越小（离起点越近），那条亮线就是"一路下坡"； ③ 结论：同一条路径，24.1 是"从起点往外记出来的"，24.4 是"从终点往里读出来的" —— 两种读法给出同一张表、同一条路（47 = 47）。

本课的收尾

这一课只做了一件事：把"找一条路"换成"给每一格记一个数"。 往下的缺口很直白：泛洪对整张地图一视同仁，它朝四面八方推，而终点只在一个方向 —— 所以它把很多根本不需要的格也定了数（本页 965 格里，真正与最优路径有关的只是其中很小一部分）。
下一课（24.2 → 第 2 课 · 猜一个数）加的那一样东西就是：数里再放一项"从这一格到终点还要花多少"的猜测， 取的时候按"已经花的 + 猜的还要花的"来取 —— 于是搜索会朝终点那边偏，而答案能不能保持不变， 就取决于那个猜测守不守一条规矩（不高估）。
★ 本页留了一个可以自己动手的口子：在画面上点格子可以把墙加上或去掉。 点满一列（把 x = 20 那道竖墙的三个口子封上），再按一次「跑到底」—— 你会发现 d(目标) 变成 ∞（目标压根定不上数）， 而"已定格数"恰好等于与起点连通的那一片（实测封口后 500 = 500，见判据⑥）。

自检面板

等待脚本…