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

一次算完，给所有人用

全课题骨架：寻路不是"找一条路"，而是"给地图上每个位置记一个数"，而记数只有一条规则 —— 从已经确定的那一圈往外推一格，给新格记下它自己的数。
前三课都是"一个人问一次"：第 1 课把整张地图算完，第 2 课让它朝终点去，第 3 课让大部分方向不必看 —— 可它们的产出都只服务一个出发位置。这一课换成一句很实际的话： 一千个人朝同一个终点走，还要逐个跑一遍搜索吗？
四段路：先把整张地图摊成一张"代价表"（27.1）→ 每格只留一个方向（27.2）→ 让一千个人读同一张表（27.3）→ 最后量一件前三课都没碰过的事：人多了会互相挡（27.4）。
★ 量出来才敢写的两件事：同一张表，任何人在任何一格里读到的方向都一样， 而"一张场 + 1000 次读"只要 1955 格次，同样的 1000 个人各跑一次 A* 要 183 000 格次 —— 少算 98.93%（判据⑦，格次是确定性读数，不受机器影响）。
★ 另一件要如实说的：积分场是四连通、流场比的是八个邻居（一手源原话如此），两者不同源 —— 斜走也算一步，所以实际走下来的步数往往小于表里那个积分值： 起点那一格积分值 43，沿场真的走一遍只要 31 步（判据⑤）。 保真度：27.1 – 27.3 为 示意 · 等价重现（都是纯图算法，页面现场跑的十条与离线定稿 q114.mjs 同口径，画面是本页自己的二维软件光栅）； 27.4 为 示意 · 结构示意 —— 一手源里 ORCA 那一步是解一个低维线性规划，本页用 "速度级各担一半 + 位置级各让一半" 的简化版画出结构与实测间距，不声称与 ORCA 逐位相同。

分段：

（脚本启动中…）

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

本帧的读数

（脚本启动中…）

27.1 一张表摊开整张地图

上一课的缺口："一个人问一次"这件事本身太贵 —— 从任意一格出发都要重新算一遍。 这一课的第一件事，是把"从终点往回看"的账一次性摊到每一格上：从终点开始，一圈一圈往外积， 每格记下"从这一格走到终点还要花多少"。这张表叫积分场（integration field）。

本段只增加一样东西：波的起点从"某一个位置"换成"目标那一格"，然后向四周积算。 积的规则与第 1 课一字不差（cand = d[n] + 1，只是方向反过来从目标出发）， 所以量出来的那条恒等式也一样：每一格的积分值 = 它最便宜的那个邻居 + 1，0 处违反（判据①）。

输入 一张格图 + 目标格 每步都花 1 波前怎么走 取 d 最小的那一格 定下来，再推四邻 推的时候写什么 d(邻) = d(这) + 1 只写更小的那个 出来的是一张表 每格一个"到终点 还要花多少" 见判据① ② ① 本页真跑的积分（逐字） function makeIntegration(map, goals) { const N = MW * MH; for (const g of goals) d[g] = 0; 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++; for (let k = 0; k < 4; k++) { const m = nbr(map, n, k); if (m < 0) continue; const cand = d[n] + 1; if (cand < d[m]) { d[m] = cand; par[m] = n; } } return true; }; return st; 右列读数 违反恒等式 0 处 / 955 格 积分值(起点) 43（= 第 3 课 C*） 波前沿途 61 层，最大 60 紧边（取等） 1806 条 见判据① ②
件一：27.1 的积分。中间是本页真跑的 makeIntegration（逐字）， 高亮那一行是它唯一的规则；左列是输入与规则；右列是两条独立核对的结果。
表① 积分场：每格的积分值 = 它最便宜的那个邻居 + 1（本页实测，2026-10-10）
量的东西实测怎么核的
违反 d(n) = 1 + min(四邻 d)0 处对全部 955 个可走格逐格算一遍
闭合顺序 d 单调非降倒退 0 次逐对比较相邻两次取出
紧边（d(邻) + 1 = d(这)）1806 条取等的那些边才是它往外推的边
积分值（起点 (5,12)）43与第 3 课的 C* 同一个数
积分值（终点 (36,12)）0波前自己那一格
波前分几层 / 最深一层61 层 / 60按 d 分层数格
第 1 / 5 / 10 / 20 层的格数4 / 16 / 25 / 16四邻波前的形状

定点观察：不动控件，直接看画面 → 看染色的深浅（越亮 = 到终点越贵）与那一条"波前" → 结论：同一张表把整张地图上"离终点多远"一次写全了，而起点那一格上的数（43）与第 3 课算出来的最优代价 是同一个数 —— 也就是说"最短路的长度"这件事，本来就只取决于终点在哪里。

27.2 每格只留一个方向

上一段留下了整张表，可表是"数"，走路的人需要的是"往哪走"。这一段的缺口在此： 光有一个数，站在格子中间的人并不知道该迈哪只脚。

本段只增加一样东西：把每个格子的八个邻居都看一遍，指向积分值最小的那一个。 于是每格只剩一个方向 —— 这张表叫流场（flow field）。★ 如实说清一处口径： 积分场是四连通的账，而流场按一手源比的是八个邻居；两处不同源，所以 斜走也算一步时，"真的沿场走一遍"的步数常常小于表里那个积分值（判据⑤）。

输入 上一段那张表 每格一个积分值 比较谁 八个邻居（含斜） 取积分值最小 一条本页约定 斜走不许切角 （横竖至少一侧可走） 为什么不会转圈 下一步的数必然更小 所以除终点外无局部极小 见判据③ ④ ⑤ ① 本页真跑的取方向（逐字） function flowDir(map, integ, n) { const x = n % MW, y = (n / MW) | 0; if (integ[n] === 0) return -1; let bi = -1, bv = Infinity; for (let k = 0; k < 8; k++) { const dx = D8[k][0], dy = D8[k][1]; if (dx !== 0 && dy !== 0) { if (!diagOK(map, x, y, dx, dy)) continue; } else if (!walk(map, x + dx, y + dy)) continue; const m = (y + dy) * MW + (x + dx); if (integ[m] < bv) { bv = integ[m]; bi = k; } } return bi; } function followField(map, flow, start) { let n = start, steps = 0, diag = 0; while (flow[n] >= 0 && steps < MW * MH + 4) { 右列读数 有方向的格 954（斜 857 / 正 97） 没有方向的格 1（就是目标格） 沿场走：卡住 0 格 / 955 格 起点真的走一遍 31 步（表里是 43） 见判据③ ④ ⑤
件一：27.2 的取方向。中间是本页真跑的 flowDir（逐字，含那条"斜走不许切角"的约定） 与 followField 的开头三行；右列是逐格跑过一遍的结果。
表② 流场：每格指向八邻居里积分值最小的那一个（本页实测，2026-10-10）
量的东西实测怎么核的
有方向的格（斜 / 正）954（857 / 97）逐格比八个邻居
没有方向的格1就是目标那一格（它自己就是终点）
沿场迭代卡住的格0对全图 955 格逐格走到头
起点沿场走的实际步数31表里那个积分值是 43（斜走算 1 步）
步数 < 积分值的格912 / 955如实报：积分场四连通、流场八邻居
平均步数 / 斜走占比19.408 / 40.4%全体格求平均

定点观察：不动控件，看画面上的箭头 → 挑任意一格顺着箭头走，一路走到终点那一格 → 结论：箭头从来不会指回自己（没有局部极小） —— 因为下一格的积分值一定比这一格小 1 以上； 而这条"一定更小"的性质只要积分场是波前积出来的就自动成立（判据④ 0 格卡住）。

27.3 一千个人读同一张表

前两段把表建好了，可真正的收益还没兑现。缺口：前三课每一次都要从某个位置重新算一遍 —— 一个人问一次。换成一千个人朝同一个终点走，逐个跑 A* 就废了。

本段只增加一样东西：把"算场"与"读场"分开。场只算一次（955 格），之后每个人做的只是 "读一眼自己脚下那一格的方向" —— 而读一眼的代价与人数无关。★ 段末还顺手收了 27.1 留的一个接口： 波前的起点可以是一列格子（多个目标各自积分值 0），这叫多目标波前。

上一段的不足 一个人问一次 一千个人就废了 本段只加一样 场算一次（955 格） 之后每人只读一眼 读一眼的代价 与人数无关 （就是取一个数组元素） 同一个终点的人 读到的方向完全一样 见判据⑥ ⑦ ⑧ ① 一次算完（本页真跑，逐字） function makeFlow(map, integ) { const N = MW * MH; const f = new Int8Array(N); f.fill(-1); for (let n = 0; n < N; n++) { f[n] = flowDir(map, integ, n); } return f; } ② 对照：一个人各跑一次（本页同一条 A*） function searchAstar(map, start, goal) { let settled = 0; g[start] = 0; f[start] = hMan(start, goal); while (true) { let n = -1, best = Infinity; for (let i = 0; i < N; i++) if (!done[i] && f[i] < best) { best = f[i]; n = i; } if (n === goal) return { cost: g[n], settled: settled, found: true }; 右列读数 一张场 955 格次 1000 次读 1000 格次 合计 1955 格次 同样 1000 人各跑 A* 183 000 格次 少算 98.93% 见判据⑥ ⑦ ⑧
件一：27.3 的复用。上框是本页真跑的 makeFlow（一次算完整张，逐字）， 下框是同一页里那条对照 A* 的收尾两行 —— 两边都以"格次"计账，因此这个比较是确定性的读数。
表③ 复用：一张场给所有人用（本页实测，2026-10-10）
量的东西实测说明
算一张流场955 格次每一格比八个邻居（一次性）
N 个人各读一眼N 格次就是取一个数组元素，与 N 无关
1000 个人合计1955 格次955 + 1000
同样 1000 人各跑一次 A*183 000 格次本页实测：单次平均已定 183.0 格
省下来的98.93%1 − 1955 / 183000
N 次读的墙钟（N = 1 / 10 / 100 / 1000 / 10000）0.07 / 0.28 / 0.31 / 1.9 / 20.8 µs本机一次实测，随机器变 —— 所以主账用格次
多目标波前（10 格一起当波前）起点积分 43 → 39"合并"就是把多个 0 一起当波前

定点观察：把"多少人"从 1 拖到 1000 → 看画面上的小点数量，同时盯"读一眼"那一列 → 结论：人数涨 1000 倍，而"读"的单价一格次都没变 —— 变的只是"要读多少眼"。 这就是"一次算完，给所有人用"的全部内容。

27.4 人多了会互相挡

上一段让一千个人各自读表走路，可它默认了一件事：人可以从别人身上穿过去。 真实的走廊里不是这样。缺口在此：流场给出的是"大方向"，它不知道前面站着谁。

本段只增加一样东西：局部避障，而且用的是与一手源同一条思路 —— "各担一半责任"：两个人快要撞上时，谁也不许把责任推给对方，各让一半。 ★ 本页是这一步的简化版（速度级"各担一半"＋位置级"各让一半"，另加一条"右侧通行"的侧让， 否则正面对穿会互相停住），如实标为结构示意：一手源里 ORCA 那一步是解一个低维线性规划，本页不做。

上一段的不足 流场只给大方向 它不知道前面站着谁 本段只加一样 快要撞上时各让一半 （谁也不把责任推给对方） 怎么算"要撞上" 两两看"接近速度" 在连线上各消掉一半 一条本页约定 侧让（右侧通行） 不然正面对穿会互停 见判据⑨ ⑩ ① 速度级：按责任份数让开（本页真跑，逐字） const app = (a.vx - b.vx) * ux + (a.vy - b.vy) * uy; if (app <= 0) continue; const both = (mode === 'half') || (a.g === b.g); const lat = app * AG_SIDE; if (both) { a.vx -= ux * app * 0.5; a.vy -= uy * app * 0.5; b.vx += ux * app * 0.5; b.vy += uy * app * 0.5; a.vx += -a.hy * lat * 0.5; a.vy += a.hx * lat * 0.5; } else if (a.g === 0) { a.vx -= ux * app; a.vy -= uy * app; } else { b.vx += ux * app; b.vy += uy * app; } ② 位置级：残余重叠按同一份责任各让一半 const both = (mode === 'half') || (a.g === b.g); if (both) { a.x -= ux * push / 2; a.y -= uy * push / 2; 三档实测 各走各的 跨组最小距 0.0001 穿过去了 ✗ 只让 A 群担责 跨组最小距 0.6400 绕行 A +15.5 / B +3.0 各担一半责任 跨组最小距 0.8778 绕行 A +6.1 / B +6.8 见判据⑨ ⑩
件一：27.4 的责任分配。上框是本页真跑的速度级避障（逐字，高亮的是"各担一半"那两支）， 下框是位置级的那几行；右列是三档的实测 —— 有意思的是绕行量的分配：责任全压在一方， 那一方就得多绕 5 倍多。
表④ 局部避障：两群对穿（各 8 人、r₁+r₂ = 0.64、1800 帧；本页实测，2026-10-10）
避障档跨组最小中心距跨组越界帧A 群路程B 群路程额外绕行（相对"各走各的"）
各走各的（不避障）0.000181 / 1800106.798.7——
只让 A 群担责0.64000122.2101.7A +15.5 / B +3.0
各担一半责任0.87780112.8105.5A +6.1 / B +6.8

★ 读这张表要看三件事：① 不避障真的会穿过去（0.0001 < 0.64）； ② 只要有人担责，跨组最小距就再没掉到 r₁+r₂ 以下（0 帧越界）； ③ 有信息量的是最后一列 —— "只让 A 群担责"时 A 多绕 5.2 倍，而"各担一半"时两边几乎一样（+6.1 / +6.8）。 这就是"各担一半责任"这五个字的可测含义：它不只是"不撞"，它还把代价也摊平了。

定点观察：在三档之间来回按，同时盯"跨组最小距"与两群路程 → 先按"各走各的"，看两群人从彼此身上穿过去； 再按"各担一半责任"，看他们各自往右让开一点 → 结论：流场负责"往哪走"，避障负责"别撞上"， 而"谁让"这件事是可以被明确定义、也可以被量出来的（本页实测：各担一半时最小距 0.8778，比"一方全担"的 0.6400 还宽）。

本页的自检

自检面板状态：（启动中…）
十条判据与离线定稿 q114.mjs 同口径；下面这块是执行日志。