从格到面
全课题骨架：寻路不是"找一条路"，而是"给地图上每个位置记一个数"，而记数只有一条规则 ——
从已经确定的那一圈往外推一格，给新格记下它自己的数。
方格 上：数记在格上、方向记在格上、人也在格与格之间走。可真实关卡的可走面是任意形状 ——
方格要么太粗（走廊只有一格宽时没法表达"贴着墙走"），要么太贵（要精细就得把格子切得很小）。
这一课把"数的载体"从格换成面 ：
先把三角网格体素化、把走不了的地方滤掉，再把可走面切成一组凸多边形，最后在多边形图上找路并拉直。
为什么必须是凸的 （28.1）→ 从体素到"能走的面" （28.2）→
切成多边形 （28.3）→ 在面上找路 （28.4）。
1264 个可走格，
按 agent 半径 0.75 过滤后剩 1132 （删掉 132）；划分出 11 个凸多边形 （面积合计 283.00，
与可走格数×格面积逐位相等 ）；多边形图上找出 7 个多边形的序列之后，
拉直把 8 个点的折线（代价 28.3095）压成 4 个点（27.5727） —— 而拉直之后再也拉不动一点 （判据⑦）。
"面内任取两点的连线不出面" 这条判据，在正方形上1000 对全过 ，
在 L 形（凹）上1000 对里有 232 对出界 —— 这就是"为什么必须是凸的"（判据①）。
保真度：示意 · 等价重现 —— 体素化 / 过滤 / 划分 / A* / 拉直都是手写 toy ，
页面现场跑的读数与离线定稿 q115.mjs 同口径（核心块逐字相同，由 sync115.mjs 复核）；
画面是本页自己的二维软件光栅。
★ 如实标注三处与 Recast 的差别：① 障碍取轴对齐矩形 （为了让"点到障碍的距离"与"点在不在障碍里"都能精确判定）；
② 过滤按格心到障碍的连续距离 判（Recast 是在体素上按邻居膨胀）；
③ 拉直用逐点试删 （Detour 用的是 funnel）—— 一手源里 Recast 的四步与"共享同一条边"的说法都逐字引在下面，
本页不引入 Recast 本体 （它是 C++，与本站"单文件自包含"冲突）。
这台设备拿不到 canvas 2D 上下文，活例跑不了。本页的原理与四张数值表照常可读 （画面只是把同一份账画出来）。
分段：
28.1 为什么必须是凸的
28.2 从体素到"能走的面"
28.3 切成多边形
28.4 在面上找路
复位
拿哪个多边形试：
正方形（凸）
L 形（凹）
agent 半径：0.75
看哪条：
穿中点的折线
拉直后
（脚本启动中…）
定点观察：（脚本启动中…）
本帧的读数
（脚本启动中…）
28.1 为什么必须是凸的
上一课的缺口：流场把方向记在格子上，可人不是走在格子中心上的 —— 贴着墙走、斜穿走廊，
这些都是"面"上的事，格子表达不了。要换成面，第一件事是决定用什么形状的面 。
本段只增加一样东西：凸多边形 （面内任意两点的连线都不出面）。
理由可以从两个方向各量一遍：叉积判据 （按序取相邻边的叉积同号）与
采样判据 （面内任取两点的连线，密集采样看有没有出界）。两者在正方形上都过，
在 L 形上叉积判据直接报"不同号"、采样判据报 232 / 1000 对出界 。
要决定的
可走面用什么形状
凸 = 什么
面内任两点连线
都不出面
怎么判
① 相邻边叉积同号
② 任取两点连线采样
为什么非要凸
同一面里两点
直线可达
见判据① ②
① 本页真跑的凸性判据（逐字）
function isConvex(pts) {
const n = pts.length;
let sgn = 0;
for (let i = 0; i < n; i++) {
const c = cross3(pts[i], pts[(i + 1) % n], pts[(i + 2) % n]);
if (Math.abs(c) < 1e-12) continue;
const s = c > 0 ? 1 : -1;
if (sgn === 0) sgn = s; else if (s !== sgn) return false;
}
return true;
}
② 同一页里那条采样判据（逐字）
function segPairs(pts, n) {
let bad = 0;
for (let i = 0; i < n; i++) {
const a = randInPoly(pts), b = randInPoly(pts);
if (!segInside(pts, a, b, 256)) bad++;
右列读数
正方形（凸）
叉积 true
出界 0 / 1000
L 形（凹）
叉积 false
出界 232 / 1000
划分出的多边形
11 个全部凸
见判据① ②
件一：28.1 的两条凸性判据。上框是本页真跑的 isConvex（逐字，
高亮那一行是"取到第一个非零叉积的符号"）；下框是同一页里那条采样判据。右列是两种形状上的实测 ——
凹形状是这一段唯一有分辨力的对照 ，缺了它就只是一句口号。
表① 凸性：两种判据在两种形状上的实测（本页，2026-10-10）
形状 叉积判据（同号？） 采样判据（1000 对里出界的） 说明 正方形（凸） true 0 两条判据一致通过 L 形（凹） false 232 两条判据一致报错 划分出的 11 个多边形 全部 true —— 它们都是矩形，凸性由构造保证
定点观察：在「正方形 / L 形」之间切 → 看画面上那 60 条采样连线里有没有一条"跑出多边形" →
结论：凸性不是审美要求，它是"同一块面里两点直线可达"这句话的充要条件 ；
而这条性质正是后面能在面上直接连直线、把路径拉直的前提。
28.2 从体素到"能走的面"
上一段决定了形状，可形状还没拿到手：真实数据是三角网格 ，不是"一组多边形"。缺口在此：
得先把空间变成一张能判"这里能不能站人"的网格。
本段只增加一样东西：把 0.5 的体素格按"格心在不在障碍里"标出来，再按 agent 半径过滤一遍
（格心到最近障碍的距离 < 半径的格删掉）。第一遍叫体素化 ，第二遍就是把 agent 的"体格"烘焙进可走面。
一手源里 Recast 的四步，前两步说的就是这一件事。
上一段的缺口
形状还没有
真实数据是三角网格
第 1 步：体素化
格心在障碍里
⇒ 这一格走不了
第 2 步：过滤
格心到障碍 < 半径
⇒ 删掉（agent 挤不进）
本页的差别（如实）
按连续距离判
Recast 按邻居膨胀
见判据③
① 体素化（本页真跑，逐字）
function makeGrid() {
const g = new Uint8Array(GW * GH);
for (let j = 0; j < GH; j++) for (let i = 0; i < GW; i++) {
g[j * GW + i] = inObst((i + 0.5) * CELL, (j + 0.5) * CELL) ? 0 : 1;
}
return g;
}
② 按半径过滤（本页真跑，逐字）
function erodeGrid(g, R) {
const out = new Uint8Array(GW * GH);
for (let j = 0; j < GH; j++) for (let i = 0; i < GW; i++) {
if (!g[j * GW + i]) continue;
const x = (i + 0.5) * CELL, y = (j + 0.5) * CELL;
out[j * GW + i] = distToObst(x, y) >= R ? 1 : 0;
}
return out;
}
右列读数
格 0.5 ⇒ 48×32
共 1536 格
体素化后可走
1264
过滤后
1132（删 132）
最小距障碍
0.7500 = 半径
见判据③
件一：28.2 的两步。上框体素化 、下框按半径过滤 （都是本页真跑，逐字）；
右列是三步的实测。★ 这两步正是一手源里 Recast 四步中的第 1、2 步
（"rasterizes the input triangle meshes into voxels" / "Voxels in areas where agents would not be able to
move are filtered and removed."）。
表② 滤波：把 agent 的体格烘焙进可走面（本页，2026-10-10；半径 0.75）
量的东西 实测 说明 体素格总数（0.5 的格） 1536（48×32） 24×16 的世界 体素化后可走格 1264 格心不在障碍里 按半径过滤后 1132 删掉 132 格 （对照）过滤前格心到障碍 < 半径的格 132 与删掉的数量逐位相等 过滤后格心到最近障碍的最小距离 0.7500 ≥ 半径 0.75 ⇒ 贴着过道走也挤不到墙
定点观察：拖「agent 半径」从 0.25 到 1.50 → 看被删掉的格数（读数里）与画面上可走面带怎么瘦下去 →
结论："agent 能不能走"不是一个格上的布尔量，而是一条带宽 ——
半径越大，可走面越小；而 28.3 的划分、28.4 的路径全都建在这张已经瘦过的面上 （半径是烘焙进去的，不是事后判的）。
28.3 切成多边形
上一段给了"一片能走的格"，可格子太多、也太碎：1132 个格子当图上的节点，比直接用方格还糟。
缺口在此：得把这片格压成若干个"面"。
本段只增加一样东西：把可走格划成一批极大的矩形（每个矩形就是一个凸多边形），
每个矩形的四条边都能与邻居对上 。划分器是手写 toy：逐格"先向右伸到头、再整块向下伸"；
一手源里 Recast 的第三步说的是同一件事（"divided into sets of polygonal regions"），
但它用的是分水岭 + 单调分区，本页不做。
上一段的缺口
1132 个格太碎
当图的节点比方格还糟
划分的三条要求
① 盖满、不重叠
② 每个面都是凸的
③ 相邻面共享一段
（不是只共一个点）
本页怎么分（toy）
逐格向右伸到头
再整块向下伸
Recast 用的是什么
分水岭 + 单调分区
本页不做
见判据② ④ ⑤
① 划分（本页真跑，逐字）
function regionRects(g) {
const used = new Uint8Array(GW * GH), out = [];
for (let j = 0; j < GH; j++) for (let i = 0; i < GW; i++) {
if (!g[j * GW + i] || used[j * GW + i]) continue;
let i1 = i;
while (i1 + 1 < GW && freeAt(g, used, i1 + 1, j)) i1++;
let j1 = j;
while (j1 + 1 < GH) {
let row = true;
for (let x = i; x <= i1; x++) {
if (!freeAt(g, used, x, j1 + 1)) { row = false; break; }
}
② 相邻面共享的是"一段"（本页真跑，逐字）
function sharedSeg(a, b) {
const ox = Math.min(a.x1, b.x1) - Math.max(a.x0, b.x0);
const oy = Math.min(a.y1, b.y1) - Math.max(a.y0, b.y0);
if (ox < -1e-9 || oy < -1e-9) return null;
右列读数
多边形数
11 个
面积合计
283.00 = 格数×格面积
相邻（共享一段）
14 对
长度 1.00 ~ 13.50
只共一个点
0 对
见判据② ④ ⑤
件一：28.3 的划分。上框是本页真跑的极大矩形划分（逐字），下框是"两个面共享的是什么"那个判定；
右列三条读数分别对应"盖满不重叠（面积守恒）""都是凸的""相邻共享的是一段而不是一个点"。
★ 三条里最有分辨力的是最后一条 —— 它必须为 0，否则面上根本走不过去 。
表③ 划分与邻接（本页，2026-10-10）
量的东西 实测 说明 多边形数（极大矩形） 11 由 1132 个可走格压成 多边形面积合计 283.00 = 可走格数 × 格面积（1132 × 0.25）⇒ 盖满且不重叠 每个多边形是否凸 11 / 11 矩形 ⇒ 凸性由构造保证（判据②） 相邻（共享正长度线段）的对数 14 线段长度 1.00 ~ 13.50 ★ 只在一个点相接的相邻对 0 必须为 0：只共一个点的话，agent 过不去 节点数对比 11 vs 1132 压掉 99.0% 的节点
定点观察：不动控件，看画面上那 11 块颜色的边界 → 找两个颜色交界的地方，看交界是"一条线"还是"一个点" →
结论：交界必须是一段有长度的线段 —— 它既是"两面相通"的证据，也是 28.4 里 A* 的边（portal）；
而"每个面都是凸的"这条保证的是"面内两点连线不出面"，于是路径在面内可以自由拉直。
28.4 在面上找路
上一段把面切好了，可面本身还不是路。缺口：面与面之间靠什么相连、连起来之后怎么走？
本段只增加一样东西：把多边形当成图的节点、把"共享的那一段"当成图的边，在图上跑 A* 得出一串多边形，
再把这串多边形"拉直"成一条折线 。拉直的做法是逐点试删 ：只要两个相邻点的连线整段落在可走面里，
就把中间那个点删掉 —— 删到再也删不动为止。★ 如实说：Detour 用的是 funnel
（一手源里的名字："Funnel algorithm is simple algorithm to find straight path along portals."），本页没有 逐行实现它。
上一段的缺口
面不是路
得知道面与面怎么连
节点与边
节点 = 一个多边形
边 = 共享的那一段
拿到什么
一串多边形（序列）
不是一个点一个点
然后拉直
能拉直就删中间点
（Detour 用 funnel）
见判据⑥ ⑦
① 多边形图上的 A*（本页真跑，逐字）
function astarPolys(regs, adj, s, g2) {
const C = regs.map(polyCenter), G = polyCenter(regs[g2]);
gsc[s] = 0; fsc[s] = h(s);
while (true) {
let u = -1, best = Infinity;
for (let i = 0; i < n; i++)
if (!done[i] && fsc[i] < best) { best = fsc[i]; u = i; }
if (u < 0) return { found: false, path: [], settled: settled };
done[u] = 1; settled++;
if (u === g2) break;
② 拉直：能拉直就删掉中间那个点（本页真跑，逐字）
function straighten(pts, regs, n) {
const out = pts.slice();
let changed = true;
while (changed) {
changed = false;
for (let i = 1; i + 1 < out.length; i++) {
右列读数
多边形序列
7 个
（已定 9 个）
穿中点折线
8 点 / 28.3095
拉直后
4 点 / 27.5727
短 2.60%
还能再拉吗
不能（0 个）
见判据⑥ ⑦
件一：28.4 的两步。上框是本页真跑的多边形图 A*（逐字），下框是拉直的开头（逐字）；
右列是三步读数。★ 最后一栏"还能再拉吗 = 0"是这一段的自检：拉直跑完必须处于"局部不可再拉"的状态 ，
否则那只是拉了一半。
表④ 在面上找路：A* + 拉直（本页，2026-10-10）
量的东西 实测 说明 起点 / 终点落在哪个多边形 3 / 2 由 findRegion 判定 多边形序列长度 7 3 → 6 → 10 → 9 → 7 → 8 → 2（A* 已定 9 个多边形） 穿中点的折线 8 点 / 代价 28.3095 每个 portal 的中点连起来 拉直后 4 点 / 代价 27.5727 短 0.7368（2.60%） ★ 拉直后再拉不动（可删的点数） 0 否则说明只拉了一半 拉直后的每个采样点都落在可走面里 真 它只删"已经验证过能直连"的点
定点观察：在「穿中点的折线 / 拉直后」之间切 → 看那条折线在拐角处"贴着墙角擦过去"还是"从多边形中心绕" →
结论：A* 给的是"经过哪几个面"，拉直才给出"具体怎么走" ——
而拉直之所以是安全的，正是因为面是凸的（面内任意两点直线可达，所以只要"每个采样点都还在面里"就够了）。
本页的自检
自检面板状态：（启动中…）
q115.mjs 同口径；下面这块是执行日志。