WARNING

NavMesh 规划器仍处在快速迭代中，各类边界情况的处理还在陆续补齐。本文只能作为大致参考，常数、判据分支和数据包字段很可能很快过时；主体结构一般不变。文中代码行为以 MaaEnd v2 分支 84de1e1（2026-10-05）为准；实测数字各自注明测量时的代码版本。

NavMesh 规划器是 MapNavigator 的路径规划部分：给定区、起点和终点，在随包预烘的体素格图上求一条带净空信息的折线，交给导航展开成 RUN 路点。MapNavigator 一文只讲了它在导航里的用法。本文先讲规划器在包体积、运行时内存和耗时之间的取舍，再按执行顺序展开内部实现：数据包、网格清洗、预烘场、垂直可达判据、前置检查与选类、窗口分档、建窗、两段搜索、视线判据、后处理和诊断，最后是实测数字。

代码在 agent/cpp-algo/source/Navmesh/，共约 1.33 万行：

约定

水平单位是底图像素，下文简称像素。体素是边长 0.25 像素的方格，下文称「格」。一格里可以叠几层路面，每层是一条格图记录，叫 span，这个叫法来自 Recast 的高度场⁠^[1]。上下左右相邻的两格里，高差不超过 3 m 的两条 span 算作连通；连通的一片 span 叫一个「类」（代码里叫 region），全区统一编号，编号叫类号。宽 $n_x$ 格、原点在 $x_0$ 的窗口里，格 $(x,y)$ 的编号是 $y\cdot n_x+x$，格心的横坐标是 $x_0+(x+0.5)\times 0.25$。竖直单位是米：按滑索数据里的仿射推算，武陵 1 像素约 1.33 m，四号谷地约 1.42 m，一格约 0.33 到 0.36 m。竖直常数都按米用。

规划器交出的路线是一条折线。两个端点都在路线上的线段叫弦，和数学里弦的意思一样；两点之间能不能直接走一条弦，要看这条线段会不会碰墙、会不会跨到别的层上，判断方法见视线。拉直（string pulling）是把折线上能直接用一条弦连起来的两点之间的中间点删掉，像把一根松弛的绳子拉紧，见拉直。

几个常数贯穿全文：

栅格算子文件开头有一行 #pragma clang fp contract(off)，禁止编译器把相邻的乘法和加法合并成一条融合乘加指令（FMA）。合不合并会改变舍入，关掉以后同一份输入在不同构建下算出逐位相同的格图。

输入与输出

规划请求由导航的路线展开器构造：

goal_deck_y 决定终点停在哪张面，也参与起点吸附：先找出终点声明面所在的类，起点只考虑吸附点所在格里有这一类 span 的三角，填洞格不算；一个都吸不上，再照常吸附。给了 start_deck_y 时，起点按它吸附，窗内的起点 span 也取离它最近的一张；没给时，起点站在哪张面由吸附得到的起点高度定，见起点所在的面。no_go_discs 只收同区的禁区：展开器按禁区生成时所在的定位区记录它，只有同区规划把它当作墙；已经判定封住唯一通路、标了 push_through 的禁区不再计入。

输出：

展开器把 points 和 clearance 原样转成 RUN 路点，用 waypoints 决定哪些点交给路线跟随。heights 写进每个路点的面高。drops 标出的落点改成严判点，带上下层面高和起跳点。

整体流程

flowchart LR
    subgraph P1 [planLocked：前置检查与分档]
        direction TB
        IN(["区 · 起点 · 终点<br/>楼层 · 声明面 · 运行期虚拟禁区"]) --> G1["引擎、区、旁包<br/>三项检查"]
        G1 --> SN["三角网吸附<br/>半径 8，退到 16"]
        SN --> NG{"端点在<br/>作者禁区？"}
        NG -->|是| F1(["判失败，置 no_go"])
        NG -->|否| CA{"端点到核心可走区<br/>的距离 > 8 像素？"}
        CA -->|是| F2(["判失败：端点离<br/>核心可走区太远"])
        CA -->|否| RG["选类<br/>起点附近的 span"]
        RG --> WN["椭圆窗口<br/>解码瓦片、建窗"]
        WN --> RW(["进入窗内求路"])
    end
    subgraph P2 [routeWindow：窗内求路]
        direction TB
        M["walk 掩膜<br/>端点所在格"] --> AC["端点接入"]
        AC --> BS["基线<br/>纯长度最短路"]
        BS --> TP["拓扑层<br/>通道掩膜 + 净空单价"]
        TP --> GM["几何层<br/>走廊内 Lazy Theta*"]
        GM --> PP["拉直、组装、拐点抬升<br/>净空、高度、落点、路点"]
        PP --> OK(["输出折线"])
        BS -.->|小窗无解或<br/>碰到可信区边界| UP(["放大窗口<br/>重新建窗"]):::bg
    end
    P1 --> P2
    classDef bg stroke-dasharray: 4 3

左边是每次规划只做一遍的前置检查，右边是每一档窗口都要重跑的求路。小窗里任何一步无解或越出可信区，都回到建窗口那一步：允许的路长与直线距离之比翻倍，按新的比值建一档更大的窗口重来。

体积、内存与速度

规划器的很多设计是在三样资源之间取平衡：数据包的体积、运行时的内存、每次规划的耗时。三样都有硬约束。数据包随资源发布，每个用户都要下载；规划器和游戏跑在同一台电脑上，内存峰值高了会挤占游戏；导航途中随时可能重新规划，一次规划要在几百毫秒内出结果。三样又互相牵制，压低其中一样，往往要多付另一样。这是整个规划器最难的部分，后面各节的数据结构和分档策略大多由它决定。

一份数据有三种放法：

• 离线算好放进包：运行时直接读，省掉计算，包变大。
• 运行时现场算：包里不存，计算时间和临时内存都记在每次规划上。
• 压缩存放，用到时解码：常驻内存小，每次用到都多花一段解码时间。

选哪种看两件事：这份数据的计算量随什么增长，以及每次规划用到它的多少。计算量随整类面积增长、每条腿都要用的场，离线算好；只与本次窗口有关的搜索，留在运行时；体积大、每次只用一小块的格图，压缩常驻，按需解码。

格图的两种内存形态差一个数量级。以 map01base 和 map02base 两张大地图为例，合计 2733 万条记录，解码后每条记录 16 字节（GridSpanRec：格号、类号、高度各 4 字节，净空 2 字节，flags 和禁步位各 1 字节）：

压缩后的流共 25.7 MB，约为它的 $1/17$。规划只解码窗口覆盖的那几块瓦，常驻的始终是压缩字节。

窗口的内存由面积上限封顶。按每格约 15 字节估算，小窗的面积上限 kLocalMaxCells 是 300 万格，整类窗口的上限 kMaxCells 是 4 亿格：

两者差两个多数量级，所以窗口分档要尽量让结果在小窗里定下来，整类窗口只在小窗证明不了的时候才开。

运行时还有几处只为压内存峰值：三角按每批 $2^{20}$ 条分批解码，避免全部原始记录和结构体表同时在内存里；建窗时各张中间表用完立刻释放；同一份主包的几次载入共用一份格图段字节，旁包也按文件身份共用一份；每次规划结束把空闲页还给系统。并行解码的工人数上限是 4，这几个循环受内存带宽限制，线程再多也不会更快。

演进

规划器从 2026 年 5 月到 10 月换了七代：

第 3 代和第 5 代之间有一串修补：

• #4632「立面纳入跨越约束」：路线跨过立面（高差大于水平距离、陡过 45° 的面）时告警。
• #4682「移除不知道谁丢的二向箔」：搜索改到 span 级，引入高度连续检查（LayerOracle），同列 span 的合并容差从 1.0 收到 0.25。
• #4809：高度连续检查加上 1.0 的取样高差容差。
• #4836「NAVMESH 航点支持声明所在重叠面」：终点声明面。
• #5045：工具侧的查询改用同一份 C++ 后端，删掉约 3700 行 Python 镜像实现。
• #5137「网格边界边只用来算余量，不再拿它禁步」。禁步是相邻两格之间不许跨过的那条格边。
• #5290 把抽点（从折线的密集点里挑出保留的点）改为动态规划，#5373「优化寻路速度」改成窗口为 4 的 Slim DP。按 PR 里给的对比，同一段路的规划从约 40 s 降到十几秒，代价是不够空旷的地方出来的路线不再最优。

#5405 合入 38 分钟后被 #5433 回滚，9 小时后由 #5434 原样合回。它删掉了 Slim DP 和「精确优化路径」选项，诊断改成从建窗到拐点抬升的六段输出。#5566 加入作者禁区表，#5576 加入运行期虚拟禁区，两者都在建窗时把禁区标成不可走，见 MapNavigator 一文的虚拟禁区。

第 7 代之后的修补：

• #6147「台沿下落落点留余量」：落点往外多留一段余量，并保留为路点，见落点留余量。
• 9839304「叠层处重规划起点层与下落判定」：搜索面高随路线交出；声明了终点面时，起点先按终点那一类筛三角；判台沿时顺着上层跨过多段折线找断开处。
• ff3a956「下落落点面高与抬升拐点面高」：拐点抬升挪过的拐点和留出余量后的落点重新取面高。
• #6205「滑索落地重规划起点层与同步规划停步计时」：起点声明面，见起点所在的面。
• #6214「规划松弛跳过已关闭的 span」：几何层松弛跳过已关闭的 span。
• #6219「规划提速并共用旁包与格图段」：小窗里基线和拓扑层碰到可信区边界时提前放弃；下落判定在各档窗口间共用；格图段和旁包在各区载入间共用。
• #6227「同类走不通时经台沿跳下换类续规划」：类内走不通时试从台沿跳进终点那一类，见台沿下落换类。

数据包

规划器读三份随资源发布的数据包，放在 <repo>/assets/resource/model/map/navmesh/，按文件名配对：

主包和旁包缺一不可，OccluderPack 可以没有。旁包与主包按同目录同名配对，缺了或者核对不上，整个引擎就不可用，运行期也不现场重算这些场。作者禁区表的处理一样严：没有这个文件就当没有禁区，文件在却读不通，引擎同样不可用。禁区读错比没有禁区更糟，作者以为封住的地方其实还通着。

OccluderPack 读不到时，台沿下落一律放行，滑索的每条线都当作没挡。

公共编码

三份包共用一套底层编码：

• 字节序全部小端。
• 变长整数是 LEB128⁠^[6]：每字节低 7 位有效，最高位为 1 表示后面还有字节；移位超过 63 位就判为损坏。
• 有符号数先做 zigzag⁠^[7]：unzig(u) = (u >> 1) ^ -(u & 1)，小的正负数都落成小的无符号数。
• 「流」是 varint 压缩长度 + zlib 数据。每条流解完必须正好用完字节，有剩余也判为损坏。
• 指纹是 FNV-1a 64⁠^[8]。
• 外层 gzip 整份解压后再按偏移取段，段偏移都指向解压后的字节。

主包头与段目录

BNAV 头 80 字节：

段目录每项 24 字节：tag[4], u32 flags, u64 offset, u64 size，偏移从文件头算起。已知四个段：BGEO 几何、BOML 离网连接、BSRF 面属性、BGRD 格图。v4 引入段目录，v5 把顶点、三角、连接和区表搬进 BGEO，头里那四个偏移从此作废。读包时只有 BGRD 的字节留在内存里，规划时才按瓦片解码；其余段读完就地解析，段条目保留在目录里但不再带数据，下游用 section(tag) != nullptr 判断包是哪一代。同一份主包按区载入几次时（展开器按「路径#区」各载一份），BGRD 字节按整个文件的 FNV 共用一份：缓存只持弱引用，最后一个持有者释放时字节随之释放；命中时还要逐字节比对，才算同一份（#6219「规划提速并共用旁包与格图段」）。

版本检查按字段单独记：区表的 floor_y 从 v3 起有，段目录从 v4 起有，BGEO 从 v5 起有。每个字段记的是自己出现的版本号（kZoneFloorYSince 等）。要是统一写成 >= kBaseNavRevision，下一次升版时老包里本来就有的字段会被静默跳过。

几何段

BGEO 段头 72 字节，偏移都相对段首：

三张表都切成定长块，块目录每项 16 字节：u64 offset, u32 size, u32 aux。块长记作 $c$、记录总数记作 $N$，第 $i$ 块覆盖记录 $[ic,\min ((i+1)c,N))$，块内的差分在块首从 0 重新开始，所以每块可以独立解码，按区加载时只解用得着的块。

区表不压缩，每区一条，前缀 44 字节，v3 起再加 4 字节 floor_y，后接区名：

u16 zone_id, u16 flags, u32 name_len, u32 first_tri, u32 tri_count,
u32 component_count, f32 width, f32 height, f32 sx, tx, sy, ty,
f32 floor_y, u8 name[name_len]

每区占一段连续三角 [first_tri, first_tri + tri_count)。flags 第 0 位标出 tier 区：tier 区没有自己的三角，component_count 存父区的编号，sx、tx、sy、ty 是 tier 模板像素到父区像素的仿射 $x_{\text{父区}}=s_x\cdot x_{\text{tier}}+t_x$，y 方向同理。

三张表的块编码各不相同：

三角的规范记录是 36 字节：三个顶点号、三个邻居号、分量号、重心 u、v。读进内存只留前 24 字节。分量号由规划器从邻居关系重算，重心不存盘，读取时按 ((a+b)+c)/3.0f 补回。补重心这一步不能省，因为 build_hash 按 36 字节的规范记录算；运算顺序也得照抄，换成乘 1/3 算出来的值就不再逐位相同。

连接表按 source 非降排列。连接块目录的 aux 存每块首条的 source，按区加载时先用它跳过整块，再在块内二分。表按 source 非降，下一块的首条 source 还小于要找的值，本块就整块落在前面，不用解。

面属性与离网连接

BSRF 段头 16 字节，之后每三角 8 字节：u8 area, u8 poly_type, u16 保留, u32 flags，条数必须等于三角数。每个三角带一组 32 位面属性标志，与可走白名单 0x00020CDD 相与为 0 的三角标为不可走。包里没有 BSRF 时全部可走。

BOML 是预烘的离网连接表，段头 16 字节：tag, u16 版本, u16 记录长, u32 条数, u32 保留。v1 每条 80 字节，含区号、种类、扩展标志、单双向、区域、类型、方向、半径、代价倍率和四个点的坐标；#5844 升到 v2，每条 88 字节，加了一个方向位字节（第 0 位：起端到终端可走；第 1 位：终端到起端可走）和两端所在的三角号。两端三角号存整包下标，按区加载时与连接表同一套平移，落在区外的端点退回哨兵值。

格图段

BGRD 是第 4 代起随包预烘的体素格图，也是规划器读得最多的一段。段头 40 字节：

段头后是逐区的瓦目录：区名（补齐到 4 字节的倍数）、区原点、全区类数、瓦数，然后每块瓦 48 字节：

i32 gx0, gy0, nx, ny          # 瓦窗口在全局格上的原点和尺寸
i32 px0, px1, py0, py1        # 本瓦负责的矩形，瓦内格号闭区间
u64 offset; u32 len; u32 records

左：四号谷地主区按瓦着色，颜色越深每格平均记录越多，灰色是没有记录的空瓦；蓝框是记录最多的一块瓦，实线为本瓦负责的矩形，虚线为连同外圈的整块窗口。右：一块瓦的尺寸。

每块瓦负责 512 × 512 格（128 像素）的矩形，四周各带 64 格（16 像素）的外圈，整块窗口 641 × 641 格，多出的 1 格来自格心比格边多一格。各瓦负责的矩形互不重叠，拼起来正好覆盖全区。外圈里的记录与邻瓦负责的记录重复，拼窗时丢掉。格号是全局的：窗口原点 $o_x$ 换成全局格号是 $\mathrm{round}(o_x/0.25)$，窗口原点对齐全局格线，所以窗口格和烘焙格一一对上。

一条格图记录在内存里 16 字节：

flags 五位的来历见预烘场。steps 记的是禁步：从本格迈到某个方向的相邻格，这一步是否禁止。4 个方向是 (1, 0)、(0, 1)、(1, 1)、(1, −1)，每个方向一位禁正向、一位禁反向，另外 4 个方向由邻格的反向位表示。净空存成整数平方格距，还原式

与 Clearance 算子最后一步的写法相同，读回的净空与当场算出的逐位相同。

v3 瓦载荷：

varint n                      # 记录数，0 表示空瓦
f32    hmin                   # 瓦内最低高度
varint regions, ncell, kmax   # 类号字典长、有记录的格数、最大层数
u8     select[5 · kmax]       # 每个字段每一层选 Up 或 Down
8 × 流

同一格的各层按高度升序排，第 L 层是该格的第 L 条记录。高度量化到 1/64 米，瓦内最低高度记作 $h_{\min }$，量化值记作 $q$：

Fill 记录的高度记 0。类号存成瓦内字典的下标。

五个字段的残差按「字段 → 层 → 格」三重循环排列，每个 (字段, 层) 单独选一种预测：

• Up：同一列（x 相同）、格号更小的最近一个有这一层的格，中间可以隔行。每个 (字段, 层) 开始时清空列状态。
• Down：同一格的下一层。第 0 层没有下一层，只能用 Up。

左：俯视一块小瓦，数字为该格的层数，箭头是 Up 预测取值的来源；插图是一格的侧视，Down 取同格下一层。右：map01base 和 map02base 两张大地图合计，各字段每条记录平均占的压缩后字节。

两种预测对应两种相关性：同一层面在水平方向上连续，Up 抓住地面的坡度；楼板上下层的净空和禁步位往往相同，Down 抓住层间的重复。select 由烘焙端写入，运行期照着读。以 map01base 和 map02base 两张大地图为例，合计 2733 万条记录，五个字段和三条辅助流压缩后共 25.7 MB，每条平均 0.94 字节：

高度占了一半多；量化到 1.6 cm 的高度在坡上每格都在变，残差难以归零。

主包解压后的布局。上两行展开 80 字节的 BNAV 头，中间展开 BGEO 段，下面展开 BGRD 的逐区目录和一块瓦的载荷：定长字段之后是 8 条压缩流，流 3 到 7 是五个字段的残差。块宽不按字节比例，各段的先后以段目录里的偏移为准。

旁包

BNVF 是第 6 代加入的旁包，#5450 把原来每次规划都要在整类上重算的六种场挪到离线。主包的每条 span 记录在旁包里对应六列：类内强连通分量号、重判禁步位、立面段位、台阶税边位、计入边界边的净空（把保留下来的区网格边界边也当作障碍求出的净空，不大于主包里的净空）、中轴位；另有每类一张分量间的有向无环图，以及边界边保留表：每条边界边记一张类号表，列出哪些类保留这条边。运行期因此省掉可达域、禁步重判、边界边取舍、台阶税、计入边界边的净空、中轴六样计算，没有禁区的腿只剩解码瓦片和 A*。

头 48 字节：

段：

FSPN 每瓦先存记录数 n（必须等于 BGRD 同瓦的记录数），然后 6 条流，按记录下标与 BGRD 对位：

净空的合并只许变小：边界边只会让净空变小，clr2d 大于主包净空说明旁包本身有错，这时直接判失败。禁步位的合并以主包为前提：主包在某个方向上的两位都是 0，这个方向就跳过；不全为 0 时，这个方向改用旁包重判后的两位，立面段位也从旁包读，两个正交方向上带立面段位的格边还会作为障碍线段挡住视线。

FSCC 每类存类号、分量数、边数和一条边流，边 (Δsrc, dst) 按 (src, dst) 升序，装成 CSR（compressed sparse row，压缩稀疏行）后由 reachFrom 做深度优先求可达分量集，用法见可达域。FWAL 的键是 $3t+k$（$t$ 为区内三角号，$k$ 为边序），升序差分存储，每个键挂一张升序差分的类号表，查询先二分找键、再在类号表里二分；建窗时窗口里每条边界边都要查。表里查不到某条边，说明旁包与区网格对不上，直接报错。

FLNK 由 BOML 换算到格图上而来，每条 80 字节，两端各 24 字节：格坐标、落脚高、数据里标注的落脚高、类号、净空、flags 和一个原因码。原因码 0 到 4 依次是可落脚、出界、无面、高度带内无面、带内只有非核心面。FOPN 每条 16 字节 i32 gx, i32 gy, f32 h, u16 clr, u8 flags, u8 src，区内按 (gy, gx, h 的位模式) 升序，加载时校验顺序，查找用二分。

旁包解压后的布局。48 字节头之后是段目录，FLNK、FOPN 两段可选。FCON 是 15 个 f64 加 6 个 i32 的判据常数，与运行期常数逐字节比对；FSPN 每块瓦先写 n（须等于瓦表里的记录数），再写 6 条流。

旁包校验

旁包载入时依次核对：

1. 魔数 “BNVF”，版本 2。
2. build_hash 等于主包头里的值，FNV 等于主包整份解压字节的指纹。
3. 判据版本等于 2。
4. FCON、FZON、FSPN、FSCC、FWAL 五段齐全。
5. FCON 与运行期常数逐字节相等。
6. 区表逐区对照 BGRD：同名区存在，类数、瓦数、每瓦记录数都一致。

FCON 是 15 个 f64 加 6 个 i32：

改了这些常数中的任何一个，旧旁包就整份作废，引擎不可用。这里没有降级路径，任一项不符就失败：判据不一致的场比没有场更糟。

主包的 FNV 按整份解压字节算，按区加载也照算一遍，两种加载方式得到同一个指纹，旁包都认得。

OccluderPack

OccluderPack 是第 7 代加入的，#5972 先用在滑索遮挡上，#6121 再用到台沿下落。外层容器 OCLS 头 12 字节：魔数、版本 1、场景数。之后每个区一条记录 u16 名长, 区名, u32 字节数, 本体，读取时只解目标区，其余记录跳过；同名记录取最后一条。

每个区的本体 OCLZ 头 80 字节：

之后 12 条流，每条 u32 字节数 + 数据，首尾相接，必须正好用完本体的字节：

三类数据各有一套压法：

• 模板：量化步长取 2 的整数次幂 $2^e$（$-60\le e\le 60$），顶点坐标是整数乘以步长，这个乘法没有舍入。三角角点存回指距离 $\mathrm{back}$：0 表示新顶点，否则指回下标为 $\mathrm{next}-\mathrm{back}$ 的已出现顶点，$\mathrm{next}$ 是到此为止出现过的顶点数。顶点在流里按首次被引用的顺序排。
• 实例：摆放是 $p_{\text{world}}=A{p}_{\text{local}}+t$。旋转用 smallest-three 压缩⁠^[9]：四元数四个分量里略去绝对值最大的一个，旋转码 0–3 记它的位置，其余三个分量落在 $[-1/\sqrt{2},1/\sqrt{2}]$，按分母量化；最大分量由单位长度反推。缩放三元组进调色板，每个实例存下标。分量可以为负，表示镜像摆放。旋转码 4 表示原样存 9 个 f32 的矩阵，留给写不成「旋转 × 缩放」的摆放。矩阵可逆时存它的逆，线段换进模板局部系求交；行列式恰为 0 或非有限（压扁成面或线）时，三角先摆进世界系再求交。
• 地形块：每块 $n\times n$ 个高度格点，按平面预测 $\hat{k}=k_{\text{左}}+k_{\text{上}}-k_{\text{左上}}$ 存残差，首行只看左、首列只看上，每块第一个采样接着上一块的第一个。有洞的块另存 $(n-1{)}^2$ 位的洞位图，每格切成两个三角，洞所在的格不出三角。

解完建两级包围盒树：实例树装全部实例，模板树只给三角超过 8 个的模板建，叶子最多 4 项。节点盒向外取整到 float，三角盒再外扩 $10^{-3}$（模板局部单位），盖住近乎贴面的线段求交时的舍入误差。树只用来少算，不能漏算；外扩量只要盖得住舍入，取大一点只是多算几个三角，结果不变。

OccluderPack.cpp 开头同样关掉了乘加合并，clang 和 GCC 各写了一份，求交结果与烘焙端逐位相同。地形块不进树，按块线性扫。

OccluderPack 的布局。OCLS 容器里每个区一条记录，本体 OCLZ 是 80 字节头加 12 条流，每条流是 u32 长度加数据。

读取路径

三份包都走同一个读函数：.gz 后缀的先读 gzip 尾部 4 字节的 ISIZE 预留容量，再按 4 MB 一块读进堆上的缓冲。预留来自 #3110，避免倍增扩容时新旧两份缓冲同时存在；缓冲放到堆上来自 #3095，原来放在栈上的 4 MB 数组会超出线程栈的容量。

主包有整包和按区两条加载路径。MapNavigator 的路线展开器按区加载，工具侧的查询整包加载：

flowchart LR
    subgraph W [整包]
        direction TB
        W1["读头、段目录<br/>区表"] --> W2["顶点块"]
        W2 --> W3["三角块分批<br/>补重心"]
        W3 --> W4["连接块<br/>原地剔除"]
        W4 --> W5["流式哈希<br/>核对 build_hash"]
    end
    subgraph Z [按区]
        direction TB
        Z1["读头、段目录<br/>区表，带上 tier 子区"] --> Z2["区内三角块<br/>记顶点范围"]
        Z2 --> Z3["范围内顶点块"]
        Z3 --> Z4["连接块窗口<br/>二分 source"]
        Z4 --> Z5(["靠 gzip CRC<br/>不算 build_hash"])
    end
    W ~~~ Z

两条路径解码顺序相反。整包时重心要靠顶点补，顶点先解；按区时要先扫三角才知道顶点范围，顶点后解。整包的 build_hash 按区表、顶点、三角逐批、连接的解码顺序流式更新；按区加载跳过这一步，完整性交给 gzip 自带的 CRC。两条路径都对全部解压字节算一遍 FNV，留给旁包核对。

三角按每批 $2^{20}$ 条解码，每批至少含工作线程数个块；一批转成结构体以后，暂存区留给下一批复用。整包有 553 万条原始记录，约 200 MB，一次全解出来会和结构体表叠在一起，抬高加载峰值；分批以后每批内部仍然并行。

块是定长的，每块的输出区间事先算得出，各块写各自那段，所以块解码可以并行。并行工具 NavParallel 很小：

• 工作线程数上限 4，这几个循环受内存带宽限制，线程再多也快不了；元素少于 65536 时单线程，这时起线程的开销比计算本身还大。
• 按下标静态切块，调用线程自己做第 0 块，其余每块另起一个 jthread，最多 3 个。用 jthread 是为了异常路径：调用线程那块抛出异常时，jthread 析构会等工作线程结束；普通 std::thread 在这种情况下析构会直接调用 std::terminate。
• 过滤类的循环每块往自己的桶里推，全部完成后按块序拼接，1 个线程和 N 个线程的输出逐位相同。

OccluderPack 的读取另有一套缓存：按 (路径, 区) 缓存解好的场景，失败结果也缓存，没有淘汰，解码全程持锁。

包的内存

#5450 前后的一串改动把常驻和瞬时内存都压了下来：

释放连接表容量用的是 swap：

std::vector<BaseNavLink>().swap(links_);

写成 links_ = {} 会选中 initializer_list 赋值，只把 size 清零，容量还占着。

每次规划结束都把空闲页还给系统：macOS 上调 malloc_zone_pressure_relief，Windows 上调 _heapmin（#6219）。

网格清洗

第 3 代以后，三角网退到辅助位置：搜索在格图上做，三角网只负责三件事。

• 端点吸附：起终点先吸到最近的可走三角上，取三角高度作为起点高度。
• 边界边：可走三角没有邻居的边就是墙，建窗时先按边界边保留表筛过，再标进格图（标墙，StampWalls）。
• 下落取高：判断台沿下落时，从三角网上读落点高度。

三角网在用之前要按区清洗一遍，产物是 ZoneClean。每个 ZoneClean 常驻几十到两百 MB，引擎只缓存最近用过的两个区（通常是一层 base 加一层 tier），换区时先淘汰旧区再建新区。建的过程本身还要一份临时内存，先淘汰后建，新旧两个大区就不会同时占着内存。

flowchart LR
    subgraph A [逐三角]
        direction TB
        M["按面属性<br/>就地加可走标记"] --> WD{"新一代包？"}
        WD -->|是| V1["直接借用包里的顶点"]
        WD -->|否| V2["取整到 0.05<br/>同一 (x, y) 按高度焊接"]:::bg
        V1 --> CCW["统一成逆时针"]
        V2 --> CCW
        CCW --> NB["槽位分桶<br/>找反向边、标重边"]
        NB --> J(["进入断开邻接"])
    end
    subgraph B [断开邻接与分量]
        direction TB
        C1["规则 1：重边两侧断开"] --> C2["规则 2：单向邻接断开"]
        C2 --> C3["规则 3：不可走或<br/>无对应连接，断开"]
        C3 --> UF["并查集求分量"]
        UF --> ISL["孤岛位"]
        UF --> FB["邻接压成边界位<br/>12 字节换 1 字节"]
    end
    A ~~~ B
    classDef bg stroke-dasharray: 4 3

可走标记与顶点

每个三角按面属性标志就地加一个可走标记，三角留在原位。RecastNavRoute 用 全局三角号 - lo 直接索引区网格，三角的下标必须与包里一致，所以不可走的三角也原样留在表里，只靠标记区分。标为不可走的三角在下游六处各自跳过：邻接、分量、离网连接、吸附、墙判据、体素化。全区都不可走时报错。

新一代包的顶点已经去重，ZoneClean 直接指向包里的 float 数组，不复制也不焊接。包里有 BGEO 段，或者带一份完整的 BSRF，就按新一代处理。只看 BSRF 不够：纯可走的包可以不带 BSRF，只拿它当判据会把这种新包误判成老包。老包先把坐标取整到 0.05 像素，再把同一 (x, y) 上的顶点按高度排序，相邻两点高差不超过 3 m 就并到当前代表点。这是链式合并：高度 0、2.5、5 三个点会全部并到 0。焊出退化三角时整区报错。

槽位与邻接

三角 $i$ 的第 $k$ 条有向边 T[i][k] → T[i][(k+1)%3] 编为槽号 $3i+k$。所有槽按起点顶点分桶，桶里只存槽号，终点从三角表现算，省掉一张三倍三角数的 int32 表，最大的区上是 47 MB。

对槽 $a\to b$，在 $b$ 的桶里找第一个终点是 $a$ 的槽，就是反向边，邻居是那个槽所属的三角。同一趟顺带标重边：$a$ 的桶里还有别的槽也是 $a\to b$，本槽就是重边。每个顶点平均只挂六条边，找反向边扫一个桶就够了。

桶内按槽号递增填，首个命中就是槽号最小的那一槽，和把全部有向边整体排序后取首个的结果相同。所以找邻居和标重边可以并行做，结果与线程数无关。另有一张 24 像素方格的三角分桶，供吸附查近邻三角。

断开邻接

按三条规则依次断开邻接：

1. 重边：同一条有向边出现不止一次，说明这里有非流形的接缝，重边两侧互相断开。
2. 单向邻接：$i$ 指向 $j$、$j$ 的三个槽都不指回 $i$ 的，清掉 $i$ 这一侧的邻居。
3. 可走标记与连接表：两侧有一侧不可走就断开；两侧都可走时，查包的连接表里有没有从小号三角指向大号三角的连接，没有对应连接也断开。

第三条规则让不可走的三角跟谁都不相连，各自落成孤立分量。三条规则都在并查集之前执行，求出的分量因此直接把水面这类不可走的面与可走面分开。

连接表查的是规划器构造时建好的链接表 hasLink(小号, 大号)。建表时每条连接先过一遍通行判据；通过的连接里，目标是源三角自带邻居的（约 97%）在那个邻居槽上记 1 位，其余连接按 source<<32 | target 排成一张有序小表。查询时目标若是源三角自带的邻居，就看那一槽的位；否则在小表里二分。

通行判据 isTraversableLink：

1. 两端不同区或区号为 0：不通。
2. 是三角自带的邻居：通。
3. 两端所在原始分量中较小的一个超过 512 个三角：通。
4. 否则两个三角的边两两配对（$3\times 3$ 对），求最近点对，距离 $\le 4$ 像素才通。

原始分量只用包自带的邻居关系、只连同区三角求出，连接表和可走标记都不参与。第 3、4 条只拦下至少一端在小碎片上、两端又隔得远的连接。

分量与孤岛

三条规则执行完，在剩下的邻接上做并查集（union-find）⁠^[10]⁠^[11]，根取组内最小下标。

包里的分量号在读取时就丢掉了，原始分量由规划器自己重算。孤岛按原始分量的大小判：清洗后的一个分量里，所在原始分量不超过 512 个三角的三角严格过半，整个分量标为孤岛。孤岛位只在吸附排序里用，排在距离和高度之后：这两项都相同时，非孤岛三角优先，见吸附。

最后把邻接压成每三角 1 字节的边界位，第 $k$ 位为 1 表示第 $k$ 条边没有邻居，然后释放邻接表。邻接只在 ZoneClean 构造期间存在；运行期唯一读边界位的是 BakeWalls，它只问一条边是不是边界，1 位就够，每个三角从 12 字节降到 1 字节。

预烘场

格图里的每个字段都由一串栅格算子算出来。这串算子的输入只有区几何和墙，起点、终点、禁区都不参与，所以同一块矩形任何时候算出来都一样，可以离线算好存进包里。运行期代码保留了同名的算子：BakeWalls 和 PackSpans 在运行期仍有调用方，其余算子运行期不再调用，下文按它们的代码讲烘焙的算法。三角的可走标记随网格一起送进栅格化，可走标记为 0 的三角既不出样本，也不出边界边；离线和运行期用的是同一份标记，两边的可走面一致。

第 4 代之前，这串算子在每次规划时现场运行。把当时的运行期流程和现在包里的字段对照起来，每个标志位的来历就清楚了：

Walk 位表示这一格既在层里又在核心里。Ghost 是补出来的格，高度由邻格传播；Fill 也是补出来的格，没有高度可传播。上表左列的顺序来自第 3 代的代码，右列按各标志位的定义对照。

栅格化

栅格化把三角形变成格上的高度样本。Rasterize 用的是保守栅格化（conservative rasterization）⁠^[12]：三角与格方块只要有接触，这一格就出一个样本。判断接触用二维分离轴测试⁠^[13]⁠^[14]：两个凸多边形相交，当且仅当它们在每条候选轴上的投影都重叠。格是半宽 0.125 像素的方块，对每个可走三角，在它包围盒内的每一格测 5 条轴：

• x、y 两条坐标轴：三角顶点相对格心的坐标范围与 $[-0.125,0.125]$ 有交。
• 三条边的法线 $n=(-\Delta y,\Delta x)$：三个顶点在 $n$ 上的投影范围，与方块在 $n$ 上的投影 $[-r,r]$ 有交，其中 $r=0.125(|n_x|+|n_y|)$。

全部用闭区间比较，只在边界上接触的格也算相交。相交的格按格心求重心坐标 $(t,s)$，高度取

格心在三角外时，$(t,s)$ 先夹紧：$t$ 夹到 $[0,1]$，$s$ 夹到 $[0,1-t]$。夹紧后高度总是三个顶点高度的凸组合，落在三角的高度范围内。格心是否真在三角内另记一位 ins，第 3 代用它挑核心样本。

第二趟给每个三角的平面重心所在格再补一个样本，高度取三个顶点高度的均值，ins 记 0。分离轴测试已经保证每个与窗口相交的三角至少出一格样本，这一趟让重心格多出一个样本，span 合并取均值时，这一格的高度向三角中心的高度靠拢。

左：保守栅格化。深蓝格的格心在三角内（ins = 1），浅蓝格只是分离轴测试判为相交、格心在三角外（ins = 0）；星号所在的重心格第二趟再补一个样本，高度取三顶点均值。右下的小三角三个顶点都在格线上：贴左、下边的格（红斜线）分离轴测试判为相交，但不在用 floor 取整的扫描范围里，没有样本；贴右、上边的格（绿框）有样本。右：补缝。上段两侧高差 1.2，补出 $(1.0+2.2)/2=1.6$；下段高差 3.5 超过 3，不补。十字缝的竖臂由 x 向一趟补、横臂由 y 向一趟补，交点四个邻格都是缝格，补不上。单格孔从 x 向拿到 1.4、从 y 向拿到 1.0，相差 0.4 超过 0.25，合并后是两张 span。

两处取整的规则不对称：包围盒的格范围用 floor，分离轴测试用闭区间。三角的最小 x 正好落在格线上时，左边那格在测试里算贴边相交，却不在扫描范围内；最大 x 落在格线上时，右边那格在扫描范围内，测试判为相交，出样本。所以贴在三角左、下边界上的格没有样本，贴在右、上边界上的格有样本。只有顶点坐标恰好是 0.25 的整数倍时才会出现这种情况。

竖直的三角在平面上投影成一条线段，面积为 0，分离轴测试照样命中线段经过的格。这时重心坐标的分母绝对值小于 $10^{-12}$，代码直接把它取成 $10^{-12}$，夹紧后高度落在某个顶点或某条边上。一面墙由多块竖直三角拼成时，墙脚那一列格会拿到一叠高度不同的样本，合并成 span 之后，就是下文立面判据要识别的被栅格化的立面。

补缝

两块三角网拼接处常留下一格宽的缝，AppendSeamBridge 把这种缝补上。参数 $k_b=\mathrm{round}(0.5/0.25)-1=1$，所以只补单格缝：一个空格的左右两格（或上下两格）都有样本时，在两侧各取一列 span，找高差最小的一对；高差不超过 3，就在空格里补一个样本，高度取这一对的均值。

x、y 两个方向各扫一趟。判断两侧有没有样本时用的是补缝前的占用图，补出来的样本不参与后面的判断。所以十字形缝的交点四个邻格都是缝格，两趟都补不上。四周都是地面的单格孔会从 x、y 两趟各拿到一个样本，两个高度可能不同，相差超过 0.25 时，合并后是两张 span。

span 合并

BuildSpans 把同一格的样本按高度分成若干张 span。样本按（格，高度）稳定排序后顺序扫描：与当前 span 的首样本高差大于 kMergeH = 0.25 时开一张新 span，span 的高度取组内样本的均值。

和首样本比，保证每张 span 的高度跨度不超过 0.25。如果改成和上一个样本比，一段连续坡面会整串并成一张。例如一格里的样本是 0、0.1、0.2、0.3、0.45、0.5、3.0、3.1：和首样本比，切成 {0, 0.1, 0.2}、{0.3, 0.45, 0.5}、{3.0, 3.1}；和上一个样本比，切成 {0 … 0.5}、{3.0, 3.1}。kMergeH 最早是 1.0，#4682 改为 0.25；现在的定义是 kSlope * kCS，即最大坡度下一格水平距离对应的高差。span 之间的间距没有下限，同一格的两张 span 可以靠得很近，所以后面的判据都按高度容差找 span，不按下标找。

PackSpans 把 span 存成列式表：sp_cell、sp_h 两列按格号升序排列，同一格内按高度升序；cs 记每个占用格在这两列里的起点。occ_bits 和 occ_rank 负责把格号换成占用格的下标：occ_bits 每格一位，标这一格有没有 span；occ_rank 每 64 格存一个数，是这 64 格之前的占用格总数。查格号 $c$ 时，先找到它所在的 64 位字，再数这个字里排在 $c$ 前面的 1 有几个：

查一次只要测一位、做一次 popcount。每 64 格占 8 字节位图加 4 字节前缀计数，共 12 字节；逐格存 4 字节下标的直查表要 256 字节，约是它的 21 倍。

排序是两级计数排序：先按格号的高 16 位分桶，再在每个桶里按低 16 位排。两级都保持原有次序，结果与按格号稳定排序相同；同一格内再按高度做插入排序。一级计数排序要一张按最大格号开的桶起点表，长度与整区格数相当；两级计数排序只要高位的一张小计数表、低位固定 65537 项的计数表，以及一张最大桶大小的临时表。

排好序后按列搬运，搬完一列就释放一列，输入和输出不会整份同时占着内存。沿置换环原地交换能再省一份内存，但每一步都要跳到环上的下一个位置，访存随机且只能串行，更慢。

合并 span 的同时给每一列标 face 位。记这一列的 span 数为 $n$，最高、最低 span 的高度为 $h_{\max }$、$h_{\min }$：

一列里的 span 摞起来够得上一堵墙的高度，并且多于两张，这一列才算立面（$n=1$ 时跨度为 0，所以实际要求至少三张）。恰好两张的列，是地面上方顶着一层盖子，柱廊、桥下、挑檐都是这个形状，两张之间隔的是层高。

face 只看本列，与邻列无关。三张及以上、跨度超过 3 的列都算立面，所以地面、桥面、屋顶三层叠在一起的列也会被标上。立面列上只按坡度放行，台阶、凸起、浅坑三种放宽都不给，见垂直可达判据。

左：同一格的 8 个样本 0、0.1、0.2、0.3、0.45、0.5、3.0、3.1。与首样本比时，每个样本和本组第一个样本比较，切成三张 span，高 0.10、0.42、3.05；与上一个样本比时，下面六个样本相邻差都不超过 0.15，连成一张跨度 0.5 的 span。右：face 位。墙脚一列 5 张 span、跨 6 米，是立面；桥下地面加桥面恰好 2 张，中间隔的是层高；地面、桥面、屋顶 3 张跨 8 米，也标成立面。

左：武陵主区一片城区每格的记录条数，白色是没有记录的格；虚线是剖面线。右：剖面线上每条记录按（x，高度）画一个点，蓝色是可站立的 Walk 记录，灰色是被墙标成 Dead 或在核心外的记录，橙色是补出来的 Ghost 记录。230 米的地面、242 米的平台、250 米的小块楼板和 264 米的屋顶在同一列上叠着，最多的格有 4 层以上。

标墙

BakeWalls 收集窗口外扩 4 像素范围内的边界边，即可走三角上没有相邻三角的边。三角网只标出哪里可以走，没有记录一条边界边是墙、断崖还是两块网格之间的接缝，所以边界边一律当墙处理。可走标记为 0 的三角不出边：它与可走三角之间的邻接已经在 ZoneClean 里断开，那条边由可走三角一侧作为边界边收进来，水岸因此也成了墙。

每条边记下两个端点、两端高度、两端高度的均值 $h_h$，以及这条边的编号（三角号，边序）。StampWalls 沿边按不超过 0.1 像素的间距取点，取点所在格里满足 $|h-h_h|\le 8$（kMcHBand）的 span 都标为 Dead。8 米的范围相当宽，一面墙会把上下 8 米内其他楼层的 span 一起标上。

一条边在哪些类上算墙，烘焙时另行判定：WallsAtLayer 沿边取点，只要有一个取点所在格的层高与 $h_h$ 相差不超过 8，这条边就在这一层上保留。结果存进旁包的边界边保留表（FWAL），运行期按（三角号，边序，类号）查表。

类号

同一片连续地面上的 span 应当归到一起，规划时只处理这一片。类（代码里叫 region，包里的编号字段是 rid）就是这样一片：两张 span 所在的格四邻相接、高度差不超过 3，就算相连；沿相连关系传递得到的每个连通块是一类。类号是这个连通块的编号。

LabelRegions 用并查集算类号：遍历每个有 span 的格，只与 +x、+y 两个邻格比较，把满足 $|h_1-h_2|\le 3$ 的 span 对合并。相连关系是对称的，所以每对邻格只需比较一次。包里存的 rid 是全区统一编号后的类号。

从任意一张 span 出发，按同样的相连关系泛洪（Flood），走到的正好是它所在的那一类，与出发点在类里的位置无关。所以类号可以离线算好，运行期直接按类号取用。

类的判据比后面的垂直可达判据宽得多：只要高差不超过 3 就相连，不分向上向下，也不看立面。向上一步最多只能走 1.25，所以类里有很多实际走不上去的边。类内哪里能到哪里，由下文的强连通分量细分。

填洞与合缝

Core 位由两步形态学操作得到。FillHoles 填小洞：先求掩膜外格子的 4 连通块，一个块不碰窗口边、不超过 kHoleMaxCells = 32 格（$32\times 0.25^2=2$ 平方像素）、不含受保护的格（被墙标成 Dead 的格），就整块填上。CloseCracks 合窄缝：取 $k=\mathrm{round}(0.5/0.25)=2$，最多迭代 4 轮；每一轮里，在层里、不在核心里、不受保护的格，只要横向两侧或纵向两侧在 $k$ 格以内都有核心格，就并入核心。每轮扫完后统一置位。

CloseCracks 只按横、纵两个方向判断，斜向的缝不处理。宽 $w$ 格的横向或纵向缝：

所以能合上的缝最宽 3 格，即 0.75 像素。

左：CloseCracks，$k=2$。缝宽 1、2 格第一轮合上。缝宽 3 格第一轮只有中间格两侧 2 格内都有核心，先合中间，第二轮合两边。缝宽 4 格的第 2 格左侧 2 格内有核心、右侧没有，第一轮没有新增，迭代结束。右：FillHoles，洞按 4 连通算。封闭的 12 格洞和恰好 32 格的洞填上；碰窗口边的洞、36 格超过上限的洞、含一个被墙标成 Dead 的保护格的洞都保留。

净空

净空是每一格到最近障碍格的距离，单位像素，超过 12 的记为 12。它用截断的欧氏距离变换求，分两遍⁠^[15]⁠^[16]：第一遍逐列，求每格到同一列上下最近障碍格的格数 $g$，超过 196 的记为 196；第二遍逐行，取一族抛物线的下包络⁠^[17]：

窗口 $49=\lceil 12/0.25\rceil +1$，列距上限 $196=4\times 49$。Meijster 等⁠^[16]的第二遍边扫描边维护下包络，每行线性时间；这里净空有上限，窗口固定在 ±49 格，直接取最小，每格最多比较 99 项。

这个截断版本在 12 像素以内是精确的。记 $G_k$ 为第 $x+k$ 列未截断的列距，真实的平方距离是 $D^2={\min }_k(k^2+G_k^2)$。$D\le 48$ 格时，取到最小值的那一项满足 $|k|\le 48$、$G_k\le 48<196$，在计算里原样出现；其余项要么不小于对应的真实项，要么不小于 $196^2$，所以 $b=D^2$。$D>48$ 格时，每一项要么是真实项，大于 $48^2=2304$，要么被截断后仍不小于 $196^2$，于是 $0.25\sqrt{b}>12$，输出 12。$b$ 是不超过 $196^2$ 的整数，float 能精确表示。包里存的 clr 就是 $b$，所以还原出的净空与距离变换的输出逐位相同。

距离按格心到障碍格格心量，紧贴障碍的格净空是 0.25 像素，比到障碍格边缘的距离多半格。窗口外的格按无障碍处理。整类窗口在类的包围盒外多留 32 格（kFieldHalo），旁包按同一个外圈烘焙，类边缘几格的场因此与在整区图上算的结果相同。

中轴

中轴（medial axis）⁠^[18]是通道的中线，由到两侧障碍距离相等的点组成。搜索用的通道掩膜由两部分并成：净空不小于 1.75 的开阔区，加上中轴。开阔区在窄处会断开，中轴把断开处接上，见两段搜索。

地形边界上有很多锯齿。如果直接取净空的局部最大值当中轴，每一个锯齿都会长出一条分叉。λ 中轴⁠^[19]用来去掉这些分叉：锯齿两侧的最近障碍点离得很近，走廊两侧墙上的最近障碍点离得很远，按两点间的距离设一个门槛 λ，就能把两者分开。

代码先用两遍扫描求每格的最近障碍格（NearestSource）。第一遍自上而下逐行：先从左往右，每格从 N、NW、NE、W 四个邻格接过最近源点，再从右往左接 E。第二遍自下而上逐行：先从右往左接 S、SW、SE、E，再从左往右接 W。这是 8SSEDT 式的向量传播⁠^[20]，结果是近似的欧氏最近源，距离相等时保留已有的源。然后看每个可走格和它的 8 个邻格：只要有一个邻格的最近障碍点与本格的最近障碍点相距不小于 λ，本格就在中轴上。代码用平方格距比较，门槛是 $\lceil (\lambda /0.25{)}^2\rceil =4$，其中 λ = kClrLambda = 0.5 像素，即 2 格。

λ 越大，滤掉的锯齿越多，窄缝里也越容易提不出中轴。净空为 $w$ 的缝，两壁相距约 $2w$；λ 大于这个距离时，缝里没有中轴，通道在这里断开，路线只能绕远。所以 λ 的上限由最窄的可通行缝决定。2 格足以滤掉单格的边界抖动。

λ 取 2 格时，只有单格的抖动被滤掉，比这大的锯齿照样有分叉：齿尖旁一格的最近障碍点在齿尖上，相邻一格的在旁边的墙面上，两点可以相距 2 格以上。下图合成走廊里的锯齿都大于单格，λ = 2 格的中轴在每个锯齿处都有分叉，覆盖了净空局部最大的每一格，而且更粗；λ 增大到约 6 格时，分叉才基本消失。

合成走廊，上壁带锯齿。① 净空场，贴墙格 0.25，走廊正中两行 2.5。② 净空局部最大，每个锯齿两侧各长出一条分叉。③ 代码取值 λ = 2 格。A 处两邻格的最近障碍点分在上下两壁，相距 21 格，是中轴；B 处两邻格的最近障碍点挨着，相距 1 格，不是中轴；C 处一格的最近障碍点在齿尖，相邻一格的在旁边墙面，相距 $\sqrt{10}\approx 3.2$ 格，也是中轴。④ 对照：λ 增大到 6 格，锯齿处只剩汇入中轴主线的 2 到 3 格短分叉，代价是两壁相距不到 6 格的窄缝提不出中轴。

垂直可达判据

相邻两张 span 之间能不能走，代码里分三层回答：

类的判据见类号。分量是类内的强连通分量：同一分量里的 span 两两互相可达。每张 span 的分量号和分量之间的有向图离线烘好，存在旁包里。搜索边以 RiseOk 为核心，它决定向上一步或向下一步能不能走。

向上一步

RiseOk 判断一步能不能走：从一列里高 $h_0$ 的 span，沿格步 $(d_x,d_y)$ 走到邻列里高 $h_1$ 的 span。高差 $\Delta h=h_1-h_0$ 用 double 计算。它用到两个辅助查询：

• levelAt(s, h, tol)：沿格步方向走 s 格的那一列里，有没有高度在 $h\pm \mathrm{tol}$ 以内的 span。s 为负时往身后看，越出窗口时回答没有。
• rasterFace(s)：沿格步方向走 s 格的那一列是不是立面，直接读 span 合并时算好的 face 位，见span 合并。RiseOk 只问出发列（s = 0）和到达列（s = 1）。

按代码顺序判定：

第 3 步放行的高差，在后面的分支里本来也会放行：立面列按坡度放行，门槛至少 0.25；非立面列还能放到 0.5。所以这一步不需要知道两列是不是立面，省掉了两次立面查询。格步至少有一维非零，长度不小于 1，所以 0.25 是第 4 步门槛的下界。大多数边几乎是平的，第 3 步一次比较就放行了。

第 5 步规定：出发列或到达列是立面时，坡度以外的放宽一概不给。台阶、凸起、浅坑这几种放宽是为路面准备的。如果立面列也能用，角色可以从地面迈上墙脚的叠层，沿着各列叠起来的 span 一格格往上迈，最后从墙顶迈回地面，整堵墙就爬上去了。立面列上能放行的只有第 3、4 步的坡度范围，它包含在非立面列的放行范围之内。

第 6 步的 0.5 是角色能直接迈上的台阶高。它是角色的属性，所以单独写成常数 kStepUp，与格的边长无关。

第 8、9 步给路面的小起伏补充放行，只在向上的高差超过台阶高时才用到。前方几格之内就回到出发高度，说明落脚处只是路面上一处窄凸起；身后几格之内就有目标高度，说明出发处只是路面上一处浅坑。台阶和立面的高差会一直延续下去，前后都找不到这种依据，所以这两步放行不了它们。

两步都要求那一列里没有另一个高度。前方某一列同时有出发高度和目标高度，说明那一列是上下两层叠着，立面被栅格化成一列叠层时正是这样；如果也当作凸起放行，台阶的侧面会和地面连起来，路线可以从楼梯旁边直接爬上去。身后某一列同时有两个高度，同样说明那里是两层叠着，一级级往上的台阶就是这个形状；排除这种情况，路线就不能顺着台阶爬上立面。

凸起从 s = 2 开始看，因为 s = 1 就是到达列，它一定有 $h_1$。

向上一步的判据。窄凸起在前方第 3 格回到出发高度，浅坑在身后找到目标高度，两者都在 1.25 米以内，放行；每级 1 米的连续台阶前后都找不到依据，只有每级不超过 0.5 米的台阶能走。

向下一步的判据。桥面中途往下：到达列本身还有桥面，按缝拦下；桥面在前方 4 格里都不再出现，才算台沿。

所以向上的一步能走的高差只有四档：

常量 kClimb = 3。高差 3 用在这些地方：类的相连判据、补缝的高差上限、立面判据、下落的起算线和往前看的容差、起点选类的高度带、搜索里区分下落边、高度连续检查里区分下落的门槛。向上一步能走多高，由上面四档决定。

kSlope 是可攀坡度的上限 $\tan \theta$，值为 1，名义上对应 45°。高差以米计，kCS 以像素计，代码直接拿 $\Delta h$ 和 $k_{\text{Slope}}\times k_{\text{CS}}=0.25$ 比较。按约定里的比例，一格水平约 0.33 到 0.36 米，0.25 米的高差对应的实际坡度在武陵约为 $\arctan (0.25/0.333)\approx 36.9^{\circ }$，在四号谷地约为 $\arctan (0.25/0.355)\approx 35.1^{\circ }$。

高度连续检查用的是同一套判据去掉凸起和浅坑：上限是 $\mathrm{UpAllow}(w)=\max (0.5,0.25w)$，再加 1 的取样容差，$w$ 是水平位移的格数，见高度连续检查。台阶高单独列一项，是因为只按坡度判的话，能迈上的台阶高就固定成一格的坡高，路缘、地面的小起伏这些连续地面都会被切成立面。

向下一步

向下的一步分两种。$-3\le \Delta h<0$ 的一步直接由第 3 步放行，不往前看。$\Delta h<-3$ 的一步先往前看：沿格步方向看第 1 到第 4 格，任一格里有高度在 $h_0\pm 3$ 以内的 span，这一步就不通。出发的那一层在前方又出现，说明脚下只是一道窄缝，两侧本是同一片路面；路线如果在这里掉下去，再从下层走出来，角色实际走不出这条线。出发层在前方 4 格里一直没有出现，才是台沿。

几点推论：

• 往前看从 s = 1 开始，也就是到达列本身。桥面高 5、桥下地面高 0 的两层列上，从桥面的一格走向下一格时，只要下一格还有桥面，就只能接着走桥面；桥面在前方连续 4 格（1 像素）里都不再出现，才算台沿，可以落到地面。
• 上层 2 到 4 格宽的空档，两个方向都过不去：往下落会被往前看拦下，跨过去需要超出 8 邻的步长。1 格宽的空档在栅格化阶段已由补缝补上，所以受影响的是 0.5 到 1 像素宽的空档。
• 容差取 3。前方任何一张高度在 $[h_0-3,h_0+3]$ 内的 span 都算出发层回来，包括比出发层低 2.9 的另一层。
• 下落没有坡度限制：通过往前看和碰撞体检查之后，第 3 步直接放行。
• levelAt 对窗口外的列一律回答没有。离窗口边 4 格以内，往前看看不到窗口外的出发层，凸起、浅坑判据也看不到窗口外的依据。

方向不对称是这套判据的直接结果：一条落差 5 米的边，往下走通过往前看和碰撞体检查就通，往上走在第 7 步就不通。所以可达关系是有向图，类内还要再分强连通分量⁠^[21]。

单向边从第 7 代开始才有。#6011（09-26，「吸附按层级破平, 落差边改单向」）之前，第 2 步是 if (dh < -kClimb) return false;，上下对称，落差超过 3 一律不通。这个 PR 加了 kDrop 和 kSeamCells，给 levelAt 加了容差参数；此后向下超过 3 的一步改为先往前看，前方没有出发层就放行，碰撞体检查是后来的 #6121 加上的。kDrop 取 $10^9$：游戏里角色没有摔落伤害，向下的落差不设实际上限，所以第 1 步不会拦下任何一步。

同一个 PR 在搜索里给落差边开了三处例外：

• 落差边的弦不做视线检查。
• 落差边不让 Theta* 把弦直接接到父节点的父节点。下落是单向边，这样接出来的弦会从台沿上方的空中穿过。
• 纯下落的 span 对不查禁步位。禁步位不区分方向，往下跳又用不到台阶，所以这项检查放到逐 span 的循环里，按高差的方向分别判断。

搜索一侧的细节见两段搜索。kStepUp、kBumpUp 和两个格数常量来自 #5405，kSlope 来自 #4682。

可达域

搜索之前先把起点能到的 span 圈出来，叫可达域，搜索只在可达域里展开。它由两部分组成：起点 span 所在分量在分量图上能到的所有分量，以及沿离网连接能到的分量。可达域只取决于旁包里的分量号和分量图，与窗口大小无关。

旁包给每张 span 记了它在类内的强连通分量号，每一类存一张分量之间的有向无环图，格式见旁包。运行期分三步求可达域：

1. 从起点 span 的分量出发，在分量图上做深度优先搜索，得到可达分量集。起点的分量不在图里时报错。
2. 窗口里每张本类的 span 按自己的分量号查这个集合。分量号为 0 或超出集合范围时报错。
3. 分量图里没有离网连接。只要有一条离网连接的起点在域内、终点在域外，就从终点的分量再做一次深度优先搜索并进来，直到可达域不再增长。

示意图。左边俯视：同色块是一个强连通分量，同一分量里的 span 两两互相可达；带三角的黑边是分量之间的单向边，这里画的是台沿下落（高 → 低）；红色虚线弧是离网连接。右边从种子所在的 A 求可达域：① 在分量图上深度优先得到 A、B、C；G 只往 C 落，从 C 上不去。② 离网连接 B → D 的起点在域内、终点不在，从 D 再做一次深度优先，并入 D、E。③ E 并入后，离网连接 E → F 生效，并入 F；再扫一遍没有新增，停止。代码按离网连接表的次序原地更新，② ③ 可能在同一趟扫描里完成。

可达域、旁包里重新判过的禁步位、边界边保留表这三样都按整类算好存在旁包里，小窗和整类窗口读到的值逐位相同。窗口大小只影响净空、通道这些场和搜索范围，这部分由窗口分档里小窗结果的检查把关。

第 6 代之前，运行期现场求可达域：SpanReach 从种子出发逐轮做广度优先搜索，每一步按 8 邻展开、用 RiseOk 判断。和搜索相比，它少三项检查：格掩膜、对角切角、立面禁步位。

搜索失败时，诊断代码按搜索的判据从一端求可达的 span 集，用来报告断开处。它展开一步时检查格掩膜、对角切角、立面禁步位和 RiseOk，也沿离网连接走。从终点一端反向求时，检查的是反方向的那一步 v → u：禁步位和向上一步的判据都有方向，拿正向去判，会把只能往下走的台阶说成两个方向都能走。

台沿下落

#6121（10-01，修 #6107）给下落边加上碰撞体检查。RiseOk 只调用一个回调函数，台沿下落能不能跳由调用方判断。规划器每次建好窗口后，把 FallGate 设为这个回调，用窗口所在区的碰撞体判断。

FallGate 的流程：

1. 区没有碰撞体，或区的平面到世界坐标变换在任一轴上的缩放为 0 时，返回空回调。RiseOk 遇到空回调就跳过这一项，下落照常放行。
2. 两张缓存表按全局格号索引，一次规划里各档窗口共用（#6219）：一张按（起跳格，落点格，起跳高，落点高）记判定结果，一张按（格，高）记投影后的点。
3. 起跳格和落点格各取格心，投影到区网格的三角上：在格心 0.25 像素以内的可走三角里找，跳过顶点高度范围离 h 超过 2 的三角；取三角上离格心最近的点，插值高度与 h 相差超过 2 的也跳过；剩下的按（平面距离，高差）取最小。找不到时直接用格心和 span 的高度。
4. 用区的平面到世界坐标变换把像素坐标换成世界坐标，高度原样作为世界 y。
5. 调用碰撞体的 dropBlocked，角色参数 climb = 0.39、height = 2.1，单位米。被挡住时这一步不通。

碰撞体一侧的 dropBlocked 用两条竖直取样线（代码里的 column）和一个竖直截面做检查。起跳点和落点各有一条竖直取样线，它与碰撞体的所有面求交，每个交点记下高度和朝向（朝上或朝下）；竖直的面与竖直取样线没有交点。某一高度处脚下的地面，取交点里朝上、与这个高度相差不超过 climb 的最高一个。记起跳高为 $y_t$、落点高为 $y_l$、$c=0.39$，判定顺序：

1. 起跳点的取样线取 $(y_t-c,y_t+c)$ 一段；落点的取样线从 $y_l-c$ 一直取到 $\max (y_t,y_l+c)$。两端各放宽 $10^{-6}$。
2. 落点 $y_l\pm c$ 以内没有朝上的面：放行。
3. 落点取样线上有朝下的面，高度在 $y_l+c$ 与 $y_t$ 之间：落点头顶有实体，拦下。
4. 起跳点 $y_t\pm c$ 以内没有朝上的面：放行。
5. 取 $b=\max (\text{起跳地面},y_t)$，沿起跳点到落点的直线立一个竖直截面，高度范围 $[b+0.39,b+2.1]$。有任何面穿过这个截面：起跳路径上有实体，拦下。
6. 其余情况放行。

示意侧视，起跳高 5.0，落点高 1.0，横向放大。① 台沿上有一道 0.25 高的矮沿，顶端在竖直截面下沿 5.39 以下，放行。② 落点上方高 3.0 处有一块实体，底面朝下，在落点头顶 1.39 到 5.0 之间，拦下，竖直截面不再检查。③ 起跳路径上有护栏，顶高 6.1，穿过 5.39 到 7.1 的竖直截面，拦下。

两项检查合起来，检查的是一条 L 形的路径：先在起跳高度水平走出台沿，再竖直落到落点。竖直截面的下沿比起跳地面高 0.39，高不过 0.39 的矮物不算阻挡。落点上方只看朝下的面，所以落点上方另一层平台挡住下落的是它的底面，它的顶面不算。缺地面的两个提前返回的分支都放行。

各处可达判定是否检查碰撞体：

落点留余量做不做，取决于区的平面到世界坐标变换缩放是否非零；区没有碰撞体时照样做，见落点留余量。

前置检查与选类

规划入口 planLocked 在进入窗口分档之前要做一串检查，任何一项不通过都直接返回，这时诊断信息全是默认值。按代码顺序：

声明了终点面时，第 9 项的两块小格图提前到吸附之前解码：起点块的外扩半径取 16 + 8 像素，覆盖放宽后的吸附半径内任一吸附点，再外扩一个选类半径；终点块用来在声明面上找出终点那一类，起点吸附靠它筛三角，见起点所在的面。提前解码失败时，到第 9 项再解码一次，那时仍失败才报错。

装载碰撞体在第 7、8 项之间，没有失败出口。窗口分档里还有五个出口：类过大、外部取消、整类窗口建窗口失败、最后一档求路失败、端点离可达域太远或被禁步位隔开，见窗口分档。最后一个出口报错之前，可能先试台沿下落换类；试的过程中被外部取消，就按取消返回。

引擎装载

引擎构造时依次装载三样东西，任一样失败，之后每次规划都在第 1 项检查返回同一条错误：

1. 主包里的格图段。没有这一段，或这一段解析失败，引擎都不可用。
2. 旁包。旁包与主包同目录、同名配对，缺失或与主包对不上时，整个引擎不可用。
3. 作者禁区表。没有禁区表就当作没有禁区；有表却读不通时，整个引擎不可用。读错的禁区表会让作者封住的地方实际可以通行，所以这种情况下引擎停用。

禁区表是仓库里的配置，由调用方提供路径，与主包分开存放。规划、预热和 regionsNear 三个公开入口共用一把锁，同一个引擎上的规划串行执行。

吸附

起点和终点先吸附到区网格上，半径 8 像素：

1. 从 24 像素见方的分桶里取半径范围内的三角，跳过可走标记为 0 的三角，两轮都如此。
2. 对每个三角，求它上面离端点最近的点和平面距离，距离超过半径的跳过。
3. 剩下的三角按比较键的字典序取最小。
4. 第一轮一个都没有时，把半径放到 16 再来一轮。

比较键有三套：

这里 $h$ 是三角三个顶点高度的均值。高度带只是排序上的偏好：键的第一位让带内的候选排在前面，带内没有候选时，照样取带外最近的。

距离相同只发生在同一平面位置上叠着几层地面时：端点的投影落在每一层的三角里，距离都是 0。这时按高度选：给了楼层就按楼层选，没给就取最高的一层。依据是可达的单向性：高层可以往下跳，低层上不去；选高了最多多绕一段路，选低了会直接报不连通。

取最高的一层在 #5405 就有了，当时的理由是俯视：底图上的一个像素对应俯视图上的一点，从上往下看见的是最上面那一层。按三角号决定先后没有几何含义，三角的编号顺序一变，起点就可能吸到水下或桥下那一层，与终点分属两个分量，直接报不连通。

#6011 把理由换成了可达的单向性，同时把孤岛位从键的第一位挪到距离之后。旧键是（孤岛位，距离，$-h$，三角号）和（带外，孤岛位，距离，高差）。避开孤岛来自 #3645「路线规划 snap 吸附小碎片岛导致目标不可达」，现在它排在距离和高度之后，更近的孤岛三角会胜过更远的主体网格三角。

吸附之后，起点高度 $h_0$ 取起点三角三个顶点高度的均值，后面选类的高度带和种子的高度都用它。

起点所在的面

起点吸附到哪张面，按以下优先次序：

1. 请求带了起点声明面 start_deck_y：用上表第三套键吸附，半径 8，吸不上再放到 16。
2. 没有起点声明面、但声明了终点面：先只在一部分三角里吸附。对每个候选三角，用它上面离起点最近的点和三角高求种子记录：先在起点格附近选，选不到改用这个点重选，与选类相同。种子所在格里有终点那一类、且不带 Fill 位的 span，这个三角才算候选。
3. 前两步都吸不上时，按楼层的两套键照常吸附。

第 2 步要用到终点那一类，所以声明了终点面时，选类用的两块小格图提前到吸附之前解码，见前置检查与选类。这一步来自 9839304「叠层处重规划起点层与下落判定」，第 1 步来自 #6205「滑索落地重规划起点层与同步规划停步计时」。

start_deck_y 在建窗口之后还会用到：起点的吸附锚点按声明面找最近格，起点 span 取离声明面最近的一张，声明了起点面时不做格级回退，见掩膜与吸附锚点和求解器。调用方只在确知角色站在哪张面上时才传它：导航侧在滑索落地、角色还站在架子上时，传架子的高度；台沿下落换类的后一段传落点面的高度。

端点在虚拟禁区内

作者禁区按端点的原始坐标判断，高度取吸附三角的高度。任一端在禁区里，规划立即失败并置 no_go，由调用方处理。如果继续规划，会有两种错误结果：吸附会把端点挪到禁区边上，路线在边上就算到达，交出一条假路线；滑索、盲走这类后备手段不看可走面，接手后会直接穿过禁区。

导航收到 no_go 后，把这条腿的状态记为 NoGo。运行期的虚拟禁区也用同样的方式把禁区里的格标成不可走，但端点落在虚拟禁区里时照常规划。两种禁区怎样标成不可走，见建窗；导航侧的用法见 MapNavigator 一文的虚拟禁区。

端点到核心可走区的距离

第 8 项检查在全区格图上量两端到最近核心格的距离（coreAnchorPx），两端一次量完（#6219）：

1. 以每个端点所在格为中心，各取一个半边长 16 像素（64 格）的方框，收齐与两个方框相交的非空瓦。同一块瓦只收一次，并记下它落在哪个端点的方框里。
2. 这批瓦并行解码。每块瓦只看本瓦负责的区域里的格，跳过外圈里与邻瓦重复的格。
3. 每块瓦为它所属的端点各找出带 Core 位、平方格距最小的格；最后对每个端点取所有瓦里的最小值，开方后乘格的边长。一个核心格都没找到时，距离记为 16。
4. 任一端的距离超过 8 像素，检查失败。

这项检查在全区格图上做。窗口里的核心格取自同一张全区格图，只会更少，所以全区上量出的距离是窗口里距离的下界。全区上都过不了的腿，换多大的窗口也接不上，在这里判掉就省下了后面的建窗口。

这项检查只看平面距离，不分类，也不分高度：屋顶上的核心格也能让地面上的端点通过。端点在哪一层，留给后面的选类和建窗口时的种子格判断。

选类

窗内搜索只在一个类里找路，跨类只有台沿下落换类这一种方式。选类只读两端附近的格，所以只解码两块小格图：以两点的格号为中心各外扩 32 格，旁包的六列不解码，可打通死格表照常读取。

起点块覆盖原始起点和吸附点；终点块只在声明了终点面时才解码。两个选类函数 pickStartRec、pickDeckRec 结构相同，都在中心格外扩 32 格的方框里按（平方格距，高差）取最小。$32=\lceil 8/0.25\rceil$，方框是 $65\times 65$ 格，边长约 16 像素：

起点选类在起点格周围的方框里找可走的 span。定位结果是离散的，还带噪声，贴着崖边站立时，起点常落进被墙标成 Dead 的格，格里只有 Dead span，拿它当种子，可达域就是空的。候选先比格距、再比高差，离起点最近的可走 span 胜出；高度带把其他层的 span 排除在外。

选类流程：

1. 在起点格附近选记录。
2. 没选到就改用吸附点重选。起点离网时附近没有格图记录，而吸附点已经按楼层落在网格上。仍然没有时，报起点附近没有可走的格。
3. 类号取这条记录的类，种子取它的全局格号和高度。
4. 声明了终点面时，在终点附近按声明面选记录，只替换类号，种子仍是起点那一条。终点附近选不到时，报终点附近没有声明的面。

声明了终点面时，类号改用终点一侧的：起点只按平面位置吸附，可能吸到屋顶上，按起点选类会把整条路线放到屋顶那一层。选类只读两端吸附半径内的格，覆盖这两处的任何一块格图给出的结果都相同，所以先在小块上选类、再按类建窗口，与在整区图上选类的结果逐位相同。

第 4 步在建窗口时生效：种子格里只取本类的 span，起点格里没有终点那一类的面时，建窗口失败。选完类后立刻释放两块小格图。

示意图。① 起点选类的搜索范围：实线是中心格外扩 32 格的方框，虚线是 8 像素的吸附半径。② 起点格附近，起点高 $h_0=0$：原始起点格只有墙下的 Dead span，跳过；右邻格的地面 span 键为（1，0.1），入选；同一格里的屋顶差 5、崖下差 8，都超出高度带 3。整个方框里都选不到时，才围着吸附点再找一遍。③ 另一条腿，侧视：起点站在屋顶，记录在类 2；终点声明面 0，终点附近离声明面 2 以内的是地面 span，类号换成 1；种子仍取起点格，建窗口时改取这一格里类 1 的 span，格里没有就建窗口失败。

类定下来以后，按类号扫一遍全区的瓦，求这一类的包围盒，结果按区、按类缓存。包围盒只取决于类本身，每区每类只扫一次瓦，之后的腿直接查缓存。窗口分档按这个包围盒裁窗口。

regionsNear

滑索规划要从一批候选点里挑出能连上的腿，逐条真去规划代价太高。引擎为此另开一个入口 regionsNear，对每个点给出附近 8 像素内的类号集合。窗内搜索只在一个类里找路，两点的类号集合不相交时，类内搜索必然失败，不必真去规划。半径与选类的搜索范围用同一个常量 kSnapRadius。空集表示无从判断：没有格图、区未知，或者点周围没有格图记录。

候选点常集中在少数几块瓦上，所以实现上先把点按瓦分组，每块瓦只解码一次。每块瓦里跳过 Fill 记录，两个选类函数都不会选这种记录；其余记录只要格心离点不超过 8 像素，就把它的类号算进来。集合多算一个类，只会让 regionsNear 少排除一条腿；漏算一个类，会把走得通的腿判成必然失败。所以除 Fill 外的记录都算进来。

窗口分档

整类窗口覆盖整个类，结果精确，但建窗和搜索的开销按类的面积算，与腿长无关：一条很短的腿也要付整类的开销。窗口分档先按搜索椭圆建一个小窗，只在能证明小窗的结果与整类窗口逐位相同时采用；证明不了，就把允许的代价翻倍，再建一个更大的窗口。

证明分两部分。第一，净空、中轴、可达域、禁步这些逐格数据都从旁包读，在任何窗口里逐位相同。第二，搜索的单价不低于 1，弹出的格都落在以两端为焦点、两距之和为最终代价的椭圆里；这个椭圆碰不到可信区的边界，搜索就碰不到窗外。可信区是窗口四边各去掉 64 格后剩下的部分。

面积达到上限的那一档是最后一档，称为封顶档。封顶档不再做与窗口大小有关的检查，结果直接采用，窗内走不通时才改用整类窗口。最坏情况下的耗时和内存由这个面积上限决定。

flowchart LR
    subgraph WA [选窗口]
        direction TB
        T0(["第 tier 轮"]) --> LR{"上一轮要求<br/>改用整类窗口？"}
        LR -->|是| FU["整类窗口"]
        LR -->|否| TR["按 level 算允许的代价<br/>定窗口和种类"]
        TR --> SM{"小窗且与<br/>上一轮相同？"}
        SM -->|是| LV["level + 1<br/>超过 64 改整类"]:::bg
        LV --> TR
        SM -->|否| BG{"整类窗口<br/>超过 4 亿格？"}
        FU --> BG
        BG -->|是| E1(["报错：类太大"])
        BG -->|否| CX{"已取消？"}
        CX -->|是| E2(["结束：已取消"])
        CX -->|否| GO(["建窗、窗内求路"])
    end
    subgraph WB [判结果]
        direction TB
        BW{"建窗<br/>成功？"} -->|小窗失败| U1(["level + 1，下一轮"])
        BW -->|封顶失败| U2(["下一轮用整类窗口"])
        BW -->|整类失败| E3(["报错"])
        BW -->|成功| RW{"小窗：要求换档<br/>或无解？"}
        RW -->|是| U3(["level + 1，下一轮"])
        RW -->|否| CP{"封顶无解且<br/>整类 ≤ 4 亿格？"}
        CP -->|是| U4(["下一轮用整类窗口"])
        CP -->|否| HL{"有路线？"}
        HL -->|否| E4(["报错"])
        HL -->|是| RC{"端点离可达域 > 8 像素<br/>或终点被隔开？"}
        RC -->|否| OK(["输出折线"])
        RC -->|是| HP{"符合台沿下落<br/>换类的条件？"}
        HP -->|是，某处接通| OK2(["输出拼接的折线"])
        HP -->|试的途中取消| E6(["结束：已取消"])
        HP -->|否，或都不通| E5(["报错：走不到终点"])
    end
    WA ~~~ WB
    classDef bg stroke-dasharray: 4 3

左边是每一轮都要经过的步骤，右边是建窗和窗内求路之后的出口。圆角框是本轮的终点：写着“下一轮”的回到左上角，其余是整次规划的结果。虚线框那一步只在极短的腿上出现。

窗口常量

kEdtCells 是净空扫描的半径：净空最大记到 12 像素，一格 0.25 像素，$12/0.25+1=49$ 格。代码用 static_assert(kTrustMargin > kEdtCells + 8) 保证可信余量比它宽。

第 $\ell$ 档（代码里的 level）允许的代价是

单位是格，$L$ 是起点到终点的直线长度。到两端距离之和不超过 $C$ 的点组成一个椭圆，两端是它的焦点，半长轴和半短轴分别是

腿的方向角为 $\theta$ 时，椭圆外接矩形的半宽和半高是

外接矩形以两端的中点为中心，再并上端点包围盒，四边各外扩 $64+8=72$ 格。端点包围盒取原始起点、起点吸附点和终点三处所在的格，终点的吸附点不算在内。椭圆的焦点用原始端点。

整类矩形是类的包围盒四边各外扩 kFieldHalo = 32 格，按区、按类缓存。

第 0 档的椭圆接近圆形。$C=2L+200$ 时

$L=400$ 格（100 像素）时比值是 0.917。$L$ 越长比值越小，但 $C>2L$ 使 $L/C<1/2$，比值始终大于 $\sqrt{3}/2\approx 0.866$。水平腿的第 0 档窗口约 $(C+145)\times (\sqrt{C^2-L^2}+145)$ 格。椭圆要到 $C$ 接近 $L$ 时才变细长，这只出现在封顶档的二分里。

图中是四号谷地的一条长腿，按上面的公式计算，直线 172 像素。第 0 档允许的代价 394 像素，窗口 270 万格；第 1 档的椭圆超过面积上限，二分后窗口回到 300 万格，允许的代价只到 415 像素。水平腿的第 0 档矩形在 $L$ 约 740 格（185 像素）时达到 300 万格；腿比这更长、所在的类又大于 300 万格时，第 0 档就已经是封顶档。实测中有两次封顶档窗口几乎正好等于上限：$1788\times 1677=2,998,476$ 格和 $1620\times 1851=2,998,620$ 格。

三种窗口

enum class Kind
{
    Tentative,
    Capped,
    Full
};

Tentative 是小窗，Capped 是封顶档，Full 是整类窗口。每档按下面的顺序定种类：

1. 整类窗口。整类矩形不超过 300 万格，并且椭圆矩形盖住整个类、或面积达到整类矩形的 80% 时，直接用整类窗口。这种小类的整类窗口结果精确，开销也不比小窗大。
2. 小窗。椭圆矩形不超过 300 万格时用小窗，做全部检查。
3. 封顶档。超过上限时，在 $[L,C]$ 上二分 40 次，找面积刚好不超过上限的椭圆。$C=L$ 时 $b=0$，椭圆退化成两端之间的线段；连这条线段的外接矩形都超限时，直接用它，这时面积会大于 300 万格。实测中有 46 次第 0 档窗口是 $1798\times 2476\approx 445$ 万格，都在 map02base，走的就是这条分支。

可达域、禁步和墙段的取舍都从旁包读，小窗和整类窗口在这三样上逐位相同。小窗需要检查的只剩与窗口大小有关的部分，见小窗结果的检查；有一项不满足，就换到下一档。

椭圆档位

循环里有两个计数：level 是椭圆的档位，决定允许的代价；tier 是循环的轮次。每进一轮 tier 加一；level 只在小窗失败和窗口没有变大时加一。分档实测里的“第几档”指轮次 tier，封顶档失败、改用整类窗口的那一轮也算一轮。

1. 窗口没变大就跳档。腿长为 0 或极短时，允许的代价翻倍后椭圆矩形可能一格都没长，这一轮的窗口与上一轮相同。同一块窗口重跑只会得到同样的结果，所以 level 一直加，直到窗口变大；超过 64 档就改用整类窗口。腿长为 0 时 $C=200$，与 level 无关，窗口永远不会变大，最后一定改用整类窗口。
2. 整类大小检查。要建整类窗口而类矩形超过 4 亿格时，规划报错：类太大。正常的区离 4 亿格很远，这项检查只拦数据本身异常的区。
3. 取消。每轮建窗之前查一次取消回调，已取消就结束规划。建窗和窗内求路进行中不响应取消。
4. 建窗失败。小窗失败时 level 加一，下一轮用更大的窗口；封顶档失败时，下一轮改用整类窗口；整类窗口失败直接报错。建窗的错误大多与窗口大小无关，例如起点格里没有终点所在那一类的面。这类错误会让小窗各档逐一失败，到封顶档后改用整类窗口，最后以同一个错误结束。
5. 小窗的出口。窗内求路要求换档，或者无解，level 加一，进入下一轮。
6. 封顶档的出口。有解就直接采用。封顶档关掉了与窗口大小有关的检查，窗内走不通时，分不清是真的走不通，还是路线要绕出窗口，所以整类矩形不超过 4 亿格时，下一轮改用整类窗口再下结论。改之前不先查整类可达，由整类窗口那次求路给出结论。
7. 最终判定。有路线时还要看两端离可达域的距离。任一端超过 8 像素，或者终点被隔开，这条腿在本类里走不通。终点被隔开指终点格在 walk 掩膜上，却不在起点出发的可达集里：路线的最后一段从吸附点直连终点，这一段等于穿墙，见收尾检查。走不通时，符合条件就先试台沿下落换类，接通就输出拼接后的路线；其余情况报错：从起点走不到终点。两端都通过了全区上的端点到核心可走区的距离检查，端点确实在可走面上，差的是从起点出发的可达域够不着它。可达域取自旁包，小窗里用的也是整类的结果，换窗口不会改变结论。

成功和失败都输出诊断。总耗时从规划入口算起，包括载入区数据、吸附、禁区判定、端点到核心可走区的距离检查、载入端点附近的小块格图、选类，以及所有没有采用的轮次。

小窗结果的检查

小窗结果可以采用，依据是单价不低于 1。走一格的代价至少是 1，累计代价因此不小于走过的格数。代价小于端点到可信区边界的格数时，搜索走不出可信区，弹出的顺序与整类窗口里逐步相同。

带启发式的 A* 能给出更紧的界。记起点为 $s$、终点为 $t$，格 $v$ 的累计代价为 $g(v)$，启发式为 $h(v)$，最终代价为 $\mathrm{cost}$。$g(v)$ 不低于 $v$ 到起点的欧氏格数，$h(v)$ 就是 $v$ 到终点的欧氏格数，所以弹出的格都满足

也就是说，它们都落在以 $s$、$t$ 为焦点、两距之和为 $\mathrm{cost}$ 的椭圆里。

检查用到两个阈值：

• $\mathrm{limit}$：两端到窗口边最近的格数，减去 64。吸附距离和端点接入路径的长度与它比较。
• ${\mathrm{limit}}_2$：可信区外任一格到两端距离之和的下界，再减 1。搜索代价与它比较。

$n_x$、$n_y$ 是窗口的宽和高（格）。${\mathrm{limit}}_2$ 的求法：$f(q)=\Vert q-s\Vert +\Vert q-t\Vert$ 是凸函数，最小值落在两端连线上，在可信区里。区外任一点 $q$ 连向最小点的线段要穿过可信区边界，凸性保证穿越点的值不大于 $f(q)$，所以区外的下界就是边界上的最小值。记 $m=64$，可信区外的格满足 $x\le m-1$ 或 $x\ge n_x-m$（$y$ 同理），边界按这两条线取矩形 $R=[m-1,n_x-m]\times [m-1,n_y-m]$。每条边上三分 100 次求最小值，四条边取最小，再减 1 留给取整：

每次求解完成后检查

$d_s$、$d_t$ 是两端的吸附距离（像素），$\Delta$ 把它们换成格数并入代价。成立就换到下一档。$\mathrm{cost}$ 是带单价的代价，拓扑层单价 1 到 4，几何层 1 到 7，单价越高，代价越早达到阈值。单价不低于 1 时上面的界照样成立，高单价只会让换档提前，结论仍然可靠。

#6219 起，小窗里的基线和拓扑层在搜索中途就能提前放弃，阈值是

A* 弹出的 $f=g+h$ 不会减小。弹出的 $f$ 一旦达到这个值，最终代价也不会小于它，加上 $\Delta$ 后超过 ${\mathrm{limit}}_2$，这一档注定要换。搜索就此停下，按 walk 掩膜上无解处理，换到下一档。最终代价落在 $[{\mathrm{limit}}_2-\Delta ,{\mathrm{limit}}_2-\Delta +1)$ 的解会照常搜完，再由上面的检查换档。几何层带视线判据，不设这个阈值，只在搜完之后比较。

左图是四号谷地一条 102 像素的腿。橙色是第 0 档的窗口椭圆，允许的代价 1019 格；红色虚线是 ${\mathrm{limit}}_2$ 对应的椭圆，1033 格；蓝色是按实际路线长度 524 格画出的椭圆，远在 ${\mathrm{limit}}_2$ 以内，第 0 档一次通过。右图是两层的单价曲线，见拓扑层。

小窗结果与整类窗口逐位相同，要以下八条同时成立：

第 2 条里的离网连接两端不必相邻，代价是两端欧氏格距乘 $\max (k,1)$，$k$ 是连接自带的代价系数。乘数不低于 1，累计代价仍不小于走过的直线距离，椭圆界对它同样成立。

封顶档不做这些检查，结果直接采用，所以封顶档的结果没有逐位相同的保证。

放大窗口的原因

窗内求路时，凡是结果可能被窗口边切坏的地方，都设了一个换到下一档的出口。代码用三个开关控制：tentative 在小窗和封顶档为真，bounded 和 strict 只在小窗为真。封顶档没有更大的窗口可换，后两类出口在封顶档关闭，走不通时按整类窗口的规则回退或报错。

小窗里建窗失败、或窗内求路以报错结束，同样换到下一档。各情形出现的位置见建窗和两段搜索。

台沿下落换类

#6227「同类走不通时经台沿跳下换类续规划」给最终判定加了一条出路：起点所在的类走不到终点、终点在另一个类里时，找一处台沿，从起点那一类跳进终点那一类。前后两段各在自己的类里规划，再接成一条。

四条同时成立时才试：

1. 最终判定为走不通，原因是端点离可达域超过 8 像素，终点没有被隔开。
2. 起点离可达域不超过 8 像素，差距只在终点一侧。
3. 没有声明终点面。
4. 当前规划是最外层的规划；试跳时发起的额外规划里不再嵌套试跳。

找起跳点：

1. 在终点格周围按终点三角的高度选一条记录，用的是起点选类的同一个函数，这条记录的类就是终点那一类。选不到，或与起点同类时不试。
2. 在本次规划最后采用的那块窗口里，枚举起点可达集中、所在格在 core 上的 span，看它的四个正交邻格：邻格里有别类（span 表里 vis3 = 0）、比它低超过 3 像素（kClimb）的 span，且这一步不跨禁步，就是一处候选。这一步只区分本类和别类。
3. 解码所有候选落脚格的包围盒，连同旁包，标出终点那一类可走面（带 Walk 位、不带 Ghost 和 Fill 位）的每张 span 和它的分量号。落脚 span 不在终点那一类的候选丢掉。
4. 候选再经过向上一步的高差判据（RiseOk），往前看几格的接缝检查和碰撞体检查与类内下落相同，见向下一步和台沿下落。
5. 按起跳格心到起点的距离加落脚格心到终点的距离升序排。同一分量只留排第一的一处，从同一分量出发能到的地方相同。最多留 3 处。
6. 区的平面—世界变换缩放 $r$ 非零时，落脚点按落点留余量挪离台沿。这一步需要落点之后的下一个点，这里沿跳下方向，在落脚格心外 $8r+0.25$ 像素处补一个。

逐处试，每处做两次额外规划：

两段都成功就接起来。前段止于台沿，后段起于落点，中间这一步记一次台沿下落，落点下标是后段第一个点，面高取落点面高。点列和下落记录逐段拼接；净空、面高和路点也逐段拼接，任一段缺了就整列清空，接上时落点也记成路点。长度加上台沿到落点这一段，两段的告警合并，再加一条说明这次规划经台沿下落换了类。任一段失败就试下一处。

每次试之前都查取消，试的途中取消就结束规划；试过的几处都不通，照常报错：从起点走不到终点。每处多两次完整规划，最多 6 次额外规划。

分档实测

数据来自本机 16 份运行日志（2026-09-28 到 10-03）里的 3567 次成功规划，失败的规划不在统计内。每次规划在完成之前换过几次档、各因为什么：

另有 24 次是第 0 档的封顶档里够不着声明的终点面，第 1 轮改用整类窗口。

各轮耗时（ms），其余耗时 = 总耗时 − 建窗 − 拓扑段 − 几何段：

第 0 档的其余耗时中位 26 ms，是吸附、选类、拉直、组装路线、拐点抬升这些每次都有的开销；第 1 轮以后，其余耗时主要是前面几轮没有采用的求解。

左上图和右上图的横轴是完成时的轮次。77.6% 的规划在第 0 档完成。右上图是最后采用的那一轮的耗时构成：换过档的规划里，灰色的前几轮耗时占了大头。下图的竖线是 300 万格，线上那一串是封顶档，线右是线段封顶和整类窗口。

按窗口面积分三组：不超过 290 万格的是小窗或小类的整类窗口；封顶档的窗口由二分压到刚好不超过 300 万格，落在 290 万到 300 万格这一组；超过 300 万格的是线段封顶或整类窗口。

封顶档合计 777 次，加上 46 次线段封顶，共 823 次，占成功规划的 23%，这些结果没有逐位相同的保证。第 0 档用小窗或小类整类窗口完成的有 2559 次，占 $2559/3567\approx 71.7\%$。

两个规律：

• walk 掩膜上连续 5 次无解的 125 次规划，全部在第 5 轮的封顶档完成。可达的路线被小窗切断时，窗口要翻倍五次才到封顶档；封顶档不做小窗结果的检查，结果直接采用。
• 够不着声明终点面、改用整类窗口的 24 次都在 map02base，都在第 1 轮完成，窗口 $4230\times 6361\approx 2690$ 万格：第 0 档的封顶档里够不着声明的重叠面，换成整类窗口后走通，每次约 2.5 s。

窗口的演变

建窗

buildWindow 把窗口内的格图和旁包解码，展开成栅格图层和 span 表，标上墙和禁区，接上离网连接，求出可达域。栅格图层是每格存一个值的二维数组。可达域、禁步和墙段取舍是整类量，都从旁包读，小窗与整类窗口在这三样上逐位相同；窗口大小只影响搜索范围，以及端点接入、走廊这些在窗口里现算的结果，这部分由小窗结果的检查负责。

执行顺序如下。任何一步失败，窗口分档都会接住：小窗换到下一档，封顶档改用整类窗口，整类窗口报错。

解码瓦片

loadGridWindow 取与窗口相交的瓦，并行解码：

1. 按瓦目录里每块瓦的记录数求和，一次分配够记录表。窗外和不归本瓦负责的记录随后会被滤掉，这个和是上界。

2. 每块瓦在记录表里占一段，起点是它前面所有瓦的记录数之和。工作线程从一个共享计数器上逐块取瓦，记录多的瓦先取（#6219）；解出的记录直接写进这块瓦自己那一段，全部解完后按瓦的顺序把各段前移拼紧。各段的起点和拼接顺序只由瓦的下标决定，所以记录表的次序与线程数、取瓦顺序都无关，整个过程也只用一份表。

3. 每条记录的瓦内格号换成窗口格号，落在窗外或本瓦负责的区域以外的丢掉。一格只归一块瓦，同格的记录来自同一块瓦，已按（类号，高）排好。

4. 旁包按记录对位：旁包的瓦表与格图同区同序，记录按解出的次序逐条对上。某块瓦的旁包记录数与格图对不上，整体失败。

5. 合并旁包的列：

   旁包列	合并方式
   scc	分量号，原样存
   steps2x	与主包禁步位异或，得到重新判定后的禁步位
   seg	立面段位；中轴位并进 bit7
   tax	台阶税边，原样存
   clr2d	主包净空减去它，直接写回记录

   边界边只会让净空变小，clr2d 大于主包净空说明旁包与主包对不上，整体失败。中轴位并进 seg、净空直接写回记录，都是为了省内存：建窗这一刻，记录表就是内存的峰值。

6. 可打通死格表（FOPN）只查 Core 位为 0 的记录，按全局 $(g_x,g_y,h)$ 匹配，命中时并入表里的标志位，净空取两者中较大的值。这一步要排在写回计入边界边的净空之后，顺序反过来的话，打通的格又会被这份净空压回 0。

可打通死格表是旁包的可选段，格式见旁包，由 #5503 加入。表里收两类记录：只因细缝处的墙被标成 Dead、四周没有碰到悬崖、实墙和虚空的记录，以及离网连接的落点。

展开成栅格图层

记录表按顺序过一遍，每条记录写进几张栅格图层。本类的记录：

dist 写的是解码瓦片时已经换算好的计入边界边的净空。同格记录按（类号，高）排好，后写的覆盖先写的，留下的是本类最高那条记录的净空。栅格图层是平面的，一个类在同一格里有两层面时，两层共用一个净空值和一个中轴位。

本类的 Fill 记录照样写 lay、core、dist 和三张位图，只是不进 lh。Ghost 和 Fill 只出现在补出来、没有实体 span 的格上。

进 span 表的条件和栅格图层不同：排除 Fill，排除别类的 Ghost，本类的 Ghost 和别类的普通记录都留下，别类的用 vis3 = 0 标记。别类的 span 也留在表里，因为高度连续检查（LayerOracle）要看一格里的所有楼层；漏掉别类的楼板，检查就发现不了路线从楼板下面穿过。

台阶税常数 kStepTax 为 0，求解时不使用 step_edges。

记录表展开完就释放。建 span 表是建窗最耗内存的一步，记录表又是其中最大的一块，提前释放能降低内存峰值。

标墙与标禁区

墙段取舍。第 2 步取出的边界边逐条查旁包的边界边保留表（FWAL），表里记着这条边在本类上是否保留。这是整类量，直接查表；表里没有的边说明旁包与区网格对不上，建窗失败。

保留下来的墙段之后进障碍线段表，供视线判据和拉直使用。

作者禁区。作者禁区是多边形环，格心落在环内的格把 core、lay、dist 清零。点是否在环内按奇偶规则判断，手绘的自交环也有确定的结果。画在某个楼层上的禁区带一条高度带，只标高度在该楼层地面 ±12（kBaseNavFloorBand）以内的格。这条带与吸附时选层用的是同一条：楼层坐标的路点吸到哪一层，画在那个楼层上的禁区就标哪一层。

格的高度取 lh，即这一格本类非 Ghost、非 Fill 面的最高高度。画在底图上的禁区不带高度带，环下各层都标。

运行期虚拟禁区。格心到圆心的平面距离不超过半径的格同样清零，不看高度。栅格图层里只有本类的面，按平面距离标就够了。

两种禁区都只清零禁区内的格。core、lay 清零后，搜索范围、视线判据、拉直和拐点抬升都把这些格当墙。净空也要清零：视线判据要看净空，净空留着的话，拉直时路线还能从禁区上空穿过拐角。周围格的净空和中轴照旧取旁包里的值，标禁区的开销只有禁区内这些格的写入。禁区旁边的格保留原来的净空，通道掩膜和单价都按原来的净空计算，所以路线可以贴着禁区边走。

禁步与立面段

建好 span 表后，按四个方向还原禁步和立面段。方向表 dx = {1, 0, 1, 1}，dy = {0, 1, 1, -1}，每个方向在字节里占两位：

1. 主包位为 0 或本格不在 lay 里，跳过。主包位只决定要不要读旁包。
2. 主包位非 0 时，读旁包里重新判定过的禁步位：bit0 置禁步 c → b，bit1 置 b → c。
3. 只有正交两向（i < 2）且立面段位 bit i 为 1 时，在 c 和 b 的公共边上生成一段立面段。

位序和方向表与烘焙时写入的约定一致，第二位对应反方向的边。对角步只禁步，不生成立面段，所以不挡视线。被禁区清零、移出 lay 的格不再生成禁步和立面段。主包位非 0 时，旁包的这两种位就是最终结果，这一步不再看 span。

禁步是平面上的有向边，搜索时每一步都查一次。立面段和保留下来的墙段一起进障碍线段表，视线判据和拉直把它们当墙。

示意图。左边是一格里的一列记录：本类的地面（Walk、Core）和墙下的 Dead 面（Dead、Core）进 span 表，vis3 = 1；别类的楼板进表，vis3 = 0；别类的 Ghost 和本类的 Fill 丢掉。图里按高度从下往上画，记录表里的实际次序是（类号，高）。Fill 没有真实高度，解码时高度固定为 0。下方是这一格展开成的栅格图层。右边俯视，y 向上，c 是本格，b 是方向 i 上的邻格：(a) 主包这一向为 0，旁包位不读；(b) 主包非 0、旁包 bit0，只禁 c → b；(c) 正交方向带立面段位，在公共边上生成一段立面段；(d) 对角方向只禁步，不生成立面段。主包位非 0 时，立面段只看段位，与旁包的禁步位无关。

种子与离网连接

种子。可达域从一张种子 span 出发求出。种子格里离选类高度最近的本类 span 就是种子；高度取选类时选中那张 span 的高度，同格里另有 Dead 面时也不会被它替换。种子格里没有本类 span 时建窗失败：终点面改了类、起点格却没有那一类的面，就是这种情形，见选类。

离网连接。离网连接（off-mesh connection）表里本区的记录，只收两端都能落脚、都在窗内的。落脚 span 在端点格的本类 span 里取高差不超过 8（kMcHBand）、最近的一张；任一端选不出，整条连接丢弃，只有一端的连接会凭空造出可达性。代价是 $\max (k,1)$ 乘两端的格距，$k$ 是连接自带的代价系数；乘数不低于 1，单价不低于 1 的前提照样成立，见小窗结果的检查。双向连接正反各存一条。离网连接存三张表：格级、span 正向、span 反向，反向表用来求反向可达集。两端都在本类、却选不出落脚 span 的连接会被计数，收尾检查据此给出告警。别类的连接在本类 span 里本来就选不出，只有本类连接选不出时，才说明连接表与格图对不上。

可达域。按可达域一节的步骤求出：先从旁包的分量图取种子所在分量能到的全部分量，再沿两端都在窗内的离网连接反复扩展，直到不再增长。闭包每加一条新的离网连接，都对分量图做一次深度优先搜索，再扫一遍全部 span。

最后把保留下来的墙段和立面段合成一张障碍线段表 segA / segB，源表随即清空，同一批点不存两份。

建窗的内存

建窗是规划中内存占用最高的阶段。按各字段的类型计算，每格和每条记录的字节数：

代码在几处提前释放：链表头在种子格换号后释放，记录表展开完释放，墙段取舍完释放，lh 在标完作者禁区后释放，三张位图在还原完禁步和立面段后释放。span 向量一开始就按记录数预留空间，span 数不会超过记录数。std::vector 扩容时要先分配新缓冲再拷贝，新旧两份同时存在；预留可以避免在内存峰值时再多占一份。

按每格 15 字节计算，300 万格的小窗栅格图层约 $15\times 3\times 10^6=45$ MB；4 亿格的整类上限约 6 GB，还不算 span 表和求路的临时数据。整类窗口的最坏内存由 kMaxCells 决定。

两段搜索

routeWindow 在一档窗口里求三次解：基线、拓扑层、几何层。三次用同一个求解器 solve，掩膜一次比一次窄，单价和视线判据各不相同。可达性的判据在每次求解里都完整执行：掩膜先用 walk、不通再用 core，基线在 span 级不通时再退到格级；向上一步的高差（RiseOk）、禁步、目标面声明和高度连续检查都照常检查。掩膜 lim 只能去掉格，不能放宽其中任何一条判据。拓扑层和几何层失败时都有回退，走不通的结论只由基线给出。

求解器一共被调用五次：

黄色粗线是拓扑层的逐格路径，红色是最终路点。左图在四号谷地，拓扑层沿道路中轴走，几何层在路面内拉直，502 个拓扑格最后剩 21 个路点，规划共 161 ms：建窗 65 ms，拓扑层 51 ms，几何层 24 ms。右图在武陵，路线经过水面上的一段折线桥，桥面窄，几何层贴着拓扑层走，51 个路点，共 116 ms。

掩膜与吸附锚点

routeWindow 先把 core 和 lay 合成 walk 掩膜，$\mathrm{walk}=\mathrm{core}\wedge \mathrm{lay}$，随即释放 lay。窗口里的大数组都在最后一次使用之后立刻释放，用完的数组不会一直占着内存到峰值时刻。

#5137 起，区网格的边界边不再用来禁步。填洞与合缝已经判定这些细缝可以跨过，再用同一批边禁止跨缝的一步，就等于在每道接缝上多加一堵墙。

端点的窗口格号是 $\lfloor (x-x_0)/0.25\rfloor$，$x_0$ 是窗口原点，$y$ 同理。搜索只用可达域里的 span，所以端点要先吸到 cw3 上：cw3 是 walk 里至少有一张可达 span 的格。端点吸到的那一格叫吸附锚点。

• 起点吸附锚点：没声明起点面时，nearestCell 把整个窗口扫一遍，取平方格距最小的格，同距时取行优先的第一个。这里不设半径，吸附距离留到最终判定时和 8 像素比较。声明了起点面时与终点用同一套：遍历离声明面 2 以内的可用 span，按（平方格距，高差）取最小。
• 终点吸附锚点：没声明面时同上。声明了面时遍历离声明面 2 以内的可用 span，按（平方格距，高差）取最小。最近的可走格未必带着这张面，只按距离吸的话终点集合可能为空；同距再比高差，吸附结果与选终点 span 时选中的那张一致。

吸不上时规划报错：窗口里没有可吸附的格，或起点、终点附近没有未封堵的声明面。小窗里任一端吸附距离不小于 $\mathrm{limit}$ 时换到下一档。nearestCell 每调用一次就扫描整个窗口，整类窗口最大 4 亿格，单次扫描最多比较 4 亿次。

搜索的起点 span 取起点吸附锚点里离起点高度 $h_0$ 最近的一张；声明了起点面时，取离声明面最近、且在 2 以内的那一张。终点集合是终点吸附锚点里的可用 span；声明了面时只留离声明面最近、且在 2 以内的那一张。

求解器

solve 的回退顺序：

flowchart LR
    subgraph S1 [span 搜索]
        direction TB
        L{"两端在 core∧lim<br/>里八连通？"} -->|否| X1(["无解"])
        L -->|是，或基线| W["walk∧lim 上<br/>span 搜索"]
        W -->|无解| SW{"小窗？"}
        SW -->|是| U1(["换到下一档"])
        SW -->|否| K["core∧lim 上重跑"]
        W -->|有解| C{"小窗里代价 + 吸附<br/>≥ limit2？"}
        K -->|有解| C
        C -->|是| U2(["换到下一档"])
        C -->|否| OK(["返回 span 路径"])
        K -->|无解| G1(["转格级判断"])
    end
    subgraph S2 [格级回退]
        direction TB
        D{"基线，且两端都<br/>没有声明面？"} -->|否| X2(["无解"])
        D -->|是| SL{"小窗？"}
        SL -->|是| U3(["换到下一档"])
        SL -->|否| R["walk∧lim 上<br/>重选两端吸附锚点"]
        R --> CA["格级 A*<br/>无解再退回 core"]
        CA -->|有解| OK2(["返回逐格路径"])
        CA -->|无解| X3(["无解"])
    end
    S1 --> S2

1. 连通检查。基线以外的四次调用先检查两端是否连通（linked）：在 $\mathrm{core}\wedge \lim$ 上从起点吸附锚点做八连通泛洪，泛洪停下后再沿离网连接补充，重复到不再增长。碰不到终点吸附锚点就不建图：小窗换到下一档，其他窗口返回无解。span 图上的解投到格上，一定是掩膜里的一条八连通链，所以八连通是有解的必要条件；检查不通过时 solve 一定失败，不必再为接不通的掩膜建图。检查用 $\mathrm{core}\wedge \lim$，它是 solve 两次尝试里最宽的集合。

   基线跳过这项检查：基线可能在格级回退里重选吸附锚点，检查用的两端到那时就变了。

2. span 搜索。在 $\mathrm{walk}\wedge \lim$ 上跑 SpanAstar。两端吸附锚点在同一格时，直接返回起点 span 或声明面那张 span。小窗里基线和拓扑层带着提前放弃的阈值，见小窗结果的检查。

3. 退回 core。walk 上无解时，小窗换到下一档，小窗里的无解可能是窗口切出来的。其他窗口改在 $\mathrm{core}\wedge \lim$ 上重跑，成功就记一条告警，说明这次退到了 core。

4. 检查代价。有解时，小窗检查搜索代价是否碰到可信区边界，见小窗结果的检查。

5. 格级回退。span 级两次都无解时：

   • 声明了终点面或起点面就放弃。格级搜索不分层，退到这一级等于把选层交给不分楼层的搜索。
   • 基线以外的调用放弃。吸附锚点决定能不能走到，拓扑层和几何层只负责在走得通的路线里挑离墙更远的一条，不能改动它；够不着就返回无解，由基线给出结论。
   • 小窗换到下一档。
   • 其余情况在 $\mathrm{walk}\wedge \lim$ 上重选两端吸附锚点，跑格级 A*（CostAstar），无解再退到 $\mathrm{core}\wedge \lim$；成功就记一条告警，说明这次退到了格级。

格级回退只有基线会走到。格级的掩膜不经过可达域筛选，能走到分量图判为不可达的格。吸附锚点重选之后，后面的端点接入、连通检查和最终的 8 像素判定都用新的吸附锚点。

实测的 3567 次成功规划里，退回 core 和退回格级都没有发生过。

基线

const Mask all(nx, ny, 1);
const PriceField unit {};
const std::optional<Topo> base = solve(all, unit, nullptr, nullptr, true);

掩膜是整个窗口；unit 不带净空场，单价恒为 1，正交一步代价 1、对角 $\sqrt{2}$，基线就是只按长度计的最短路。只要满足可达性判据的路线存在，基线就一定有解，所以后面的拓扑层和几何层不会把走得通的腿判成走不通。最后一个参数允许基线在格级回退时重选吸附锚点。基线提供四样东西：

1. 可达判定。小窗无解时换到下一档。其他窗口无解时，先找出断开处写进诊断（见诊断），再报错：声明了终点面时报终点面不可达，并列出声明面的高度和终点吸附锚点里所有可用 span 的高度；没声明面时报两端不连通。
2. 基线可达集。基线这次求解实际用的掩膜，收尾检查判断终点是否被隔开时用。
3. 经过的离网连接。决定给哪些离网连接开接入路径。
4. 备用路线。拓扑层两次都无解时，直接用基线的路径，几何层不再运行。

基线有解以后，逐 span 的可用表就释放，后面不再用到。

端点接入

拓扑层的通道由开阔区和中轴组成。作者放的端点常贴着墙，既不在开阔区里，也不在中轴上，要先接进通道。VV(c)（visibility–Voronoi complex）⁠^[22]原文把起点和终点单独接进图，这里的做法相同：access 在可走面上求端点到开阔通道 chan0（净空 ≥ 1.75 的格）的最短路径，只把这条路径放进通道。接入路径只负责连接，取最短的一条，往通道里加的格最少；同长时取瓶颈最高的一条，再按格号排出唯一的先后。代价用整数的倒角距离（chamfer distance）⁠^[23]，整数相加没有舍入误差，比较结果在任何机器上都相同。搜索在整片可走面上进行，只要端点与 chan0 在可走面上连通，就一定能找到接入路径。

算法是 cw3 上的 Dijkstra⁠^[24]：

1. 八邻域展开，整数代价，正交 100、对角 141。
2. 堆按以下顺序比较：代价小的优先，瓶颈高的优先，格号小的优先。瓶颈是路径上的最小净空，含起点格。松弛时按同样的顺序比较，三者都相等时前驱格号小的优先。
3. 第一个弹出的 chan0 格就是终点，回溯得到路径。

结果有三种：吸附锚点已在 chan0 里，返回空路径；泛洪完整片可走面都没碰到 chan0，小窗换到下一档；路径长度（代价除以 100）不小于 $\mathrm{limit}$，小窗也换到下一档。端点接入不检查禁步、垂直可达判据和对角切角。它只决定往掩膜里加哪些格，路线能不能走过这些格，仍由后面的 span 搜索按全部判据检查。

两端各对 chan0 求一次。chan0 是 limw 的子集，接到 chan0 就接进了通道；两端各自独立计算，先后不影响结果。对 chan0 求不到的那一端，才改对整个通道 limw 重算。小窗里任一端对 chan0 求不到就直接换档，所以改对 limw 重算只发生在封顶档和整类窗口里。

离网连接的接入路径。离网连接的两端也常落在细缝边上，净空低，又不在中轴上，不在通道里，要像路线端点一样接进开阔通道 chan0。只接到 limw 不够：细缝边上的中轴常常是孤立的小段。窗口里的离网连接可能很多，所以只给基线实际经过的离网连接开接入路径；窗口里有离网连接、而 limw 中两端仍不连通时，再给全部离网连接开接入路径，重试一次。

linkChains 与 access 用同样的代价和比较顺序，区别有两处：

• 每端最多走 64 格（kLinkChainCells，代价 $64\times 100=6400$），走不到就不开，也不换档。接入路径只用来补上端点旁边的一小段，超过 64 格就不再按接入处理。
• 三张工作数组只分配一次，每处理完一端，只把改动过的格复位。端点多时，这样可以避免每端都重新分配、清空整窗的数组。

示意图。浅绿是开阔通道 chan0，灰色不可走，橙点示意中轴。终点离墙 2 格，净空 0.5，不在 chan0 里，也不在中轴上。向左、向右两条路径都是 2 步对角加 16 步正交，代价同为 $2\times 141+16\times 100=1882$；左边那条贴着一处凸起走，瓶颈 0.25，右边瓶颈 0.5，取右边。

示意图。基线（灰虚线）从 S 经离网连接 J1 到 G，J1 两端各接一条 6 格、代价 600 的路径到 chan0；基线没有经过 J2，J2 两端不开接入路径。

拓扑层

拓扑层的掩膜是

$d(c)$ 是格 $c$ 的净空（像素）。窗口里有离网连接、而 limw 中两端仍不连通时，给全部离网连接开接入路径，再试一次：基线经过的那道细缝在通道里可能太窄，改走离网连接有机会接通。

1.75 是 kClrPref，等于角色半宽 kR，也就是 VV(c) 里的期望净空 $c$。VV(c) 的思路是：把障碍向外膨胀 $c$，膨胀后仍空着的地方走可见图（visibility graph）⁠^[25]，被膨胀占掉的窄处走中轴。这里 $c$ 用作掩膜的门槛：如果改成按每格加价，中途钻过的一小段窄缝会被整条路线的长度平均掉，那一段再窄，也只让平均单价高一点。

代码里的拓扑层是这张掩膜上的逐 span A*，按格步走；可见图那一半由几何层的 Lazy Theta* 完成。

单价。PriceField 给每格一个单价：

$d$ 是格的净空。净空达到 hi 时单价为 1，净空越小单价越高，低于 lo 以后不再变。拓扑层用 multw，$[\mathrm{lo},\mathrm{hi}]=[1,4]$ 像素（kClrNarrow、kClrWide），单价在 1 到 4 之间。

上限如果取 kClrPref（1.75），中轴上净空够 1.75 的格单价都是 1，几条平行分支里最短的那条一定被选中；窄缝通常比宽道短，路线就会去钻缝。上限抬到 4，净空在 1.75 到 4 之间的格也有差价，宽道多出的长度可以靠更低的单价抵回来。上下限之比 4 决定了这一层最多愿意多绕多远：一条全程走在窄处的路线，代价最多是长度的 4 倍，所以比它长不到 4 倍的宽路都会被选中。净空低于 1 不再细分，交给几何层处理。

单价的基准取在最宽处，所以单价不低于 1，搜索用欧氏距离作启发式时不会高估剩余代价。基准如果取在窄处，宽处单价会低于 1，启发式会高估，A* 就不再保证找到最短路。所有格的单价同乘一个常数，格与格之间的相对贵贱不变，最优路径也不变。

两层单价对照：

曲线见小窗结果的检查一节的右图。拓扑层在 1.75 到 4 之间仍有差价，宽道可以靠这点差价胜过稍短的窄道；几何层只在 1.75 以下加价，开阔区里单价恒为 1。

一步的代价是步长乘两端单价的平均值：

正交步 $w=1$，对角步 $w=\sqrt{2}$。启发式是到终点格的欧氏格数。拓扑层不带视线判据，跑的是逐 span 的 A*。台阶税常数 kStepTax 为 0，求解时不加台阶税。

失败。小窗无解时换到下一档。其他窗口把 limw 换成全窗，用同样的单价再解一次，并记一条告警；这一次掩膜不再限制，单价仍随净空不足而上升。两次都无解时用基线的路径。

拓扑层的逐格路径和每格高度写进诊断；拓扑层两次都无解时写基线的。

几何层

通道确定之后再求几何形状：在拓扑层的通道里再解一次，这次带视线判据。每个节点记下它从哪个节点过来，这个记录叫父指针；从终点沿父指针回溯得到的点列叫父指针链。几何层得到的父指针链已经是紧绷（taut）的折线。弦只能落在开阔区 solidc 里。中轴是净空最大的那条线，在中轴附近拉直会把路线拉向墙，所以那一段仍逐格走；开阔区里单价恒为 1，弦的欧氏长度就是它的精确代价。拐角余量 kGeoMargin 可以把开阔区再收窄：弦贴着障碍角切过时，那里的净空正好等于门槛，门槛抬高一点，拐角就离墙远一点；收窄后仍是单价为 1 的子集，计价不受影响。

走廊。以拓扑层的逐格路径为种子，按路径自身的净空张开一条走廊：

1. 对种子做最近点变换（feature transform），每格找到离它最近的种子格。
2. 每格的走廊半宽 $c_w$ 取最近种子格的净空。
3. 到最近种子的距离不超过那个种子的净空、或本身就是种子的格，进入走廊带 band。

$c_w$ 就是走廊在这里有多宽。band 相当于在每个种子格上画一个半径等于它净空的圆，所有圆的并集就是走廊。每个圆都与最近的障碍相切，并集越不过任何一堵墙，隔壁那条平行道进不来，半宽也不会量到墙那边的窄缝上。

开阔区的门槛。solidc 是净空不低于门槛的格：

弦贴着障碍角切过时，那一点的净空正好等于门槛。门槛按走廊半宽的比例定：宽走廊里门槛高，路线被推离墙；窄处门槛降到下限 1.75，弦仍能通过。如果用一个全局常数，取高了会把窄段的弦全部否掉，路线逐格走成锯齿；取低了，宽处会一路贴着拐角切。

走廊半宽 $c_w=2$ 像素时门槛是 $\max (1.75,1.6)=1.75$，$c_w=4$ 时是 3.2，开阔地 $c_w$ 到净空上限 12 时是 9.6。拐角余量 kGeoMargin 是 0。小窗里走廊带有格落在可信区外圈时，换到下一档：走廊带在窗口边上会被截断。

视线。搜索时的视线判据只用 solidc 掩膜，不带轮廓上的障碍线段；禁步、立面和高度连续检查照常，见视线。

走廊固定。几何层的掩膜是 $\mathrm{limw}\wedge \mathrm{band}$。开阔区里单价恒为 1，如果放开走廊重解，几何层会重新选回拓扑层靠加价才避开的那条窄分支。走廊包含整条拓扑路径，两端吸附锚点也在上面，两端照样连通。

单价换成 mult，$[\mathrm{lo},\mathrm{hi}]=[0.25,1.75]$，取值 1 到 7。中轴附近的单价随净空不足按比例上升，开阔区里恒为 1，这个单价只在几条窄缝之间做取舍。

失败。小窗无解时换到下一档。其他窗口放开走廊，在 limw 上重解，得到的仍是紧绷折线，只是不再受走廊宽度限制。仍无解就保留拓扑层的逐格路径；这时没有父指针链，后处理按逐格路径拉直。

Lazy Theta*

几何层是带视线判据的 SpanAstar，按 Lazy Theta*⁠^[26]展开。Theta*⁠^[27]在松弛时就检查视线；Lazy Theta* 把这一步推迟：松弛时先把父指针接到祖父，弹出时才检查一次视线，不通过就退回格步。路径由父指针链上的直线段构成，搜索结束时路线已经是紧绷的。返回值仍是逐格路径，拓扑相关的判据按格读取；父指针链另外返回，那才是要走的折线。终点的累计代价也一并返回：单价不低于 1，它是路径格长的上界，小窗用它检查是否碰到可信区边界。经离网连接到达的节点不把父指针传给弦，也不检查视线，展开成逐格路径时不插值。

展开 u 时，邻格里已关闭的 span 直接跳过，其余的先算格步价，再试弦：

int64_t np = u;
double ndp = nd;
if (pu >= 0 && !pj && mult.v(static_cast<size_t>(cv)) <= 1.0F) {
    const int64_t cp = st.sp_cell[static_cast<size_t>(pu)];
    if (mult.v(static_cast<size_t>(cp)) <= 1.0F) {
        const double cd =
            dist[static_cast<size_t>(pu)] + std::hypot(static_cast<double>(a - cp % nx), static_cast<double>(b - cp / nx));
        if (cd < ndp - 1e-12) {
            np = pu;
            ndp = cd;
        }
    }
}

1. 走弦的条件。u 有父节点 pu；u 不是经离网连接或下落到达的；邻格和祖父格的单价都不超过 1，即净空不低于 1.75。起点没有父节点，它的直接邻居都走格步。整段弦是否都在开阔区里，由弹出时的视线判据检查。
2. 弦的代价。$g(\mathrm{pu})$ 加上邻格与祖父格格心之间的欧氏格距，不乘单价，不加罚项。弦比格步便宜超过 $10^{-12}$ 才采用，相等时取格步。
3. 下落。落差超过 kClimb（3 像素）的一步，父指针直接指向 u。下落是单向边，接到祖父的弦会从台沿上方的空中穿过。离网连接同样把父指针指向 u。
4. 更新。新代价比邻格现有的代价小超过 $10^{-12}$，才更新它的代价和父指针，并重新入堆。已关闭的 span 不参与松弛，八邻和离网连接对端都一样（#6214「规划松弛跳过已关闭的 span」）：已关闭的 span 弹出时已经检查过一次视线，之后不会再弹出；如果松弛还能改它的父指针，新接上的弦就没有机会再检查。
5. 弹出。同一 span 在堆里可能有多个条目，代价更新后留下的旧条目满足 $f>g+h+10^{-9}$，弹出时跳过；已关闭的也跳过。父指针不是离网连接或下落时，检查一次视线，不通过就 reparent，对应 Lazy Theta* 的 SetVertex：在八邻里已关闭的 span 中，按展开时的同一套判据（切角、禁步、垂直可达判据）挑代价加步价最小的作父节点。视线全部不通过时，整条路线退化成逐格 A*，所以弦不会把一条走得通的腿变成走不通。
6. 到达。终点集合里任一张 span 弹出就停。

弹出时才检查视线、不通过就从已关闭的邻格里重挑父节点、松弛时跳过已关闭的节点，这三点沿用 Nash 等人的 Lazy Theta*⁠^[26]。原版跑在单层、处处同价的格图上；这里有单价场、多层 span、单向下落和离网连接，有几处相应改动：

下游按逐格路径读取，所以拿到父指针链以后，每条弦再展开成逐格路径：中间格的 span 按弦两端的高度线性插值，取最接近的一张。视线判据已经检查过整条弦上的逐点高度，这一步只是给每个点对上 span。离网连接段不展开，它的两端之间没有地面。

示意图，一格 0.25 像素。灰线是逐格 A* 的父指针链，每格一个点，代价 33.6；蓝线是 Lazy Theta* 的父指针链，由直线段组成，代价 32.3。黄色窄道单价 1.6，只能逐格接父节点；开阔区单价为 1，可以走弦。放大框里，弹出 (12,12) 时才检查它接在祖父 (8,11) 上的弦，这条弦擦过障碍角，视线不通过，父节点改成已关闭的邻格 (11,12)，后面的弦从 (11,12) 出发。下排左边是三条规则，右边是侧视：从台沿跳下的一步，父指针指向台沿格，弹出时不检查这一步。

窄道里的格不在 solidc 里，弹出时即使父格就在隔壁，视线也不通过，于是每格都走一遍 reparent，结果与逐格 A* 相同。

格级回退

CostAstar 是格上的 A*，只在基线的格级回退里用。它与 SpanAstar 的差别：

• 节点是格，不分层，没有垂直可达判据、高度连续检查和视线判据。
• 堆里代价相同时先比 x 再比 y；SpanAstar 比 span 下标，相当于先比 y 再比 x。
• 离网连接只检查对端格在掩膜里，不计单价和禁步。

两者共用八邻域、禁止切角、禁步、$10^{-12}$ 的松弛容差，步价都先在 float 里算、再转成 double 累加。不计浮点舍入时，单价不低于 1、离网连接代价不低于两端欧氏格距、罚项非负，启发式满足一致性（consistent），节点第一次弹出时的代价就是最优代价。

收尾检查

几何层之后还有三项检查：

1. 终点被隔开。终点格在 walk 里、却不在基线可达集里时，标记终点被隔开。路线最后一段从终点吸附锚点直连终点，这一段不做障碍检查。终点自己踩在可走面上、却不在可达集里时，这一段等于穿墙；终点不在可走面上时，偏差按作者点位的误差处理，照常直连。判据用基线可达集：此时的求解掩膜是拓扑层和几何层的通道，贴墙的终点本来就不在里面，用它判断会把所有贴墙的终点都当成被隔开。

   基线走了格级回退时，基线可达集就是格级掩膜，这个标记一定为假。标记为真时，窗口分档的最终判定报错：从起点走不到终点，见椭圆档位。

2. 无法避开的立面。最终路径里相邻两格之间跨过禁步、又不是离网连接的，每处记一步，诊断里给出告警和步数（#4632）。

3. 落不到面的离网连接。建窗时有本类离网连接选不出落脚 span，诊断里给出告警和条数。

搜索实测

计时分两段：拓扑段从 routeWindow 入口算起，包括 walk 掩膜、吸附、端点接入、基线、轮廓追踪和拓扑层；几何段包括走廊和几何层。实测中第 0 档完成、没有告警的 2698 次规划，拓扑段中位 8.8 ms，几何段中位 6.9 ms，两段合计分别是 200 s 和 101 s。

3567 次成功规划里只出现过一种回退：拓扑层在通道掩膜上无解，改在全窗上重解，共 416 次，占 11.7%。

416 次里有 314 次的窗口在 290 万到 300 万格之间，即封顶档；347 次在之前几轮换档的原因都是 walk 掩膜上无解，其余 69 次没有换过档。改到全窗以后，拓扑层要在整个窗口上按单价再解一遍，拓扑段中位约是没有回退时的 12 倍，窗口格数中位也大了约 6 倍。#6104 那台机器的记录里有 18 次这种回退，中位 4.3 s，见 MapNavigator 一文的规划耗时。

视线

几何层搜索、拉直和拐点抬升都要回答同一个问题：从点 p 沿直线走到点 q，这条弦中途会不会撞墙、跨过不许跨的格边，或者换到另一层上。三处都调用 Visibility::ok 回答，一次调用把三项检查做完。禁步按格边逐格查，查的格边与拓扑层逐格走同一串格步时查的相同。台阶税常数 kStepTax 为 0：走过台阶不额外加代价，台阶边表也不传给视线判据。

ok(p, q, hp, hq) 依次做三项检查，任一项不通过就返回假：

1. 障碍线段。弦与障碍线段（BlockerSegments）求交；一段都没交上，再查 on 掩膜。
2. 立面禁步。弦依次经过的相邻两格之间有禁步边，视线不通过。
3. 高度连续检查。从 p 的高度 hp 出发，沿弦逐格跟踪高度（LayerOracle），到 q 时能落到 hq 才算通过。

routeWindow 拼出三个视图。三个视图的立面禁步和高度连续检查完全相同，差别在障碍线段和 on 掩膜：

• vis：搜索时的视线不带障碍线段，只靠 on 掩膜拦。开阔区（solidc）是净空不低于 $\max (1.75,0.8c_w)$ 的格，$c_w$ 是这一格所在走廊的半宽，见几何层。开阔区的格离墙至少 1.75 像素，弦整条落在开阔区里就碰不到墙。
• vis_geo：把 on 掩膜从开阔区换成这条路线自己的路线掩膜 tm。开阔区里单价恒为 1，弦的欧氏长度正好等于代价，这个性质只在搜索计价时需要；拉直不计价，只问能不能走过去。tm 不超出最终那次求解的掩膜，拉直出不了这条通道。
• vis_hard：只用障碍线段，不带 on 掩膜。拐点贴着障碍角，那一带净空低于开阔区的门槛，tm 在那里只比路径宽一格；拐点抬升如果用 tm 判，拐点就离不开原路径。

后两个视图的障碍线段完全相同，共用一份线段表和桶索引，只建一次。路线掩膜 tm 的构造见拉直的输入。

取格

判据要知道一条弦经过哪些格。代码里有三种取法：

数字直线从起点格 a 走到终点格 b，$\Delta =b-a$：

nearbyint 把两个分量各自舍入到最近的整数。立面禁步和高度连续检查用同一套数字直线，两项检查对“弦经过哪些格”给出同一个答案。

数字直线沿主轴（$|{\Delta }_x|$、$|{\Delta }_y|$ 中较大的那个方向）每列取一格，取离直线最近的那一格，与 Bresenham 直线算法⁠^[28]思路相同；相邻两格总是八邻，正好是一个格步。另一种常见的取法是 supercover⁠^[29]⁠^[30]，取弦碰到的全部格，更保守。这里选数字直线，是因为禁步记在格与八邻格之间的边上：弦拆成一串格步以后，视线要查的格边，正是拓扑层逐格走这串格步时要查的那几条。这样取格有两点性质：

• 擦角的格。弦只擦过一个角的格不在数字直线上，它两侧的格边也不查。
• 方向。nearbyint 在默认舍入模式下四舍六入五取偶，副轴偏移正好是半格时，p → q 和 q → p 取到的格不同，见下图右边。

示意图。左边是从格 (0,0) 到格 (7,4) 的弦。蓝色是数字直线取到的 8 格；虚线框是弦实际碰到的全部 12 格（supercover），作对照；红点是 on 掩膜的 18 个采样点；打叉的两格弦只擦过一角，采样点也没落进去，三种取法都不取它们。右边是 (0,0) 到 (2,1)：正向 $k=1$ 时副轴偏移 $\mathrm{nearbyint}(0.5)=0$，取到 (1,0)；反向是 $\mathrm{nearbyint}(-0.5)=-0$，取到 (1,1)。

障碍线段

障碍线段是视线判据里的墙：一组平面线段，弦与其中任何一段相交就算被挡。它有三个来源：

1. core 轮廓。TraceContours 把窗口的 core 掩膜描成闭合折线。
2. 墙段。标墙时保留下来的边界边，见标墙与标禁区。
3. 立面段。见禁步与立面段。

轮廓追踪。格角按 $y(n_x+1)+x$ 编号，每个格角一个字节：低四位记四个方向上有没有出边，高四位记这条出边走过没有。给定格角和方向，出边的终点就确定了，两个格角编号之差是每个方向固定的常数 kStep，所以方向号本身就能代表一条出边，邻接表和“已走过”集合都不用另建散列表。

1. 建边。掩膜格的某一侧邻格不在掩膜里（或在窗口外），就在这条边的起点格角置出边位。边的走向让掩膜格落在行进方向左侧，y 轴向上时外轮廓是逆时针，洞是顺时针。
2. 追踪。从每个还有未走出边的格角出发，沿出边一路走，走到已经走过的出边就闭合成环。
3. 岔口。两个掩膜格只在对角相接时，那个格角有两条出边，优先右转。
4. 输出。每个格角都输出，共线点不合并，所以障碍线段都是 0.25 像素长的格边。

示意图，y 轴向上。左边两个掩膜格对角相接，格角 (3,2) 有两条入边、两条出边。中间是代码的右转规则：从左下那一格的右边向北走到岔口，右转向东，接着绕右上那一格，两格连成一个 8 字环。右边是左转的结果，两格各成一个 4 边环。下方是格角 (3,2) 走完以后的那个字节。两种分组拆成线段以后是同一批格边，障碍线段只看线段，分组不影响结果。

桶索引。障碍线段按边长 4 像素（16 格）的方桶建 CSR 索引：所有桶的线段编号连续排在一个数组里，另用一个起点数组记每个桶从哪里开始。索引在第一次查询时才建，因为一条腿要造好几个视图，其中有的视图一次都不查询。线段登记在它的包围盒覆盖的每个桶里。弦与某段相交时，交点既在这段的包围盒里，又在弦上；只要弦的取样覆盖到交点所在的桶，这段就会被测到。所以只测弦扫过的桶，结果与扫全表相同。

查询时沿弦取 $\lfloor L/2\rfloor +2$ 个等距点（L 是弦长，单位像素），间距小于 2 像素，也就是半个桶；每个点扫它所在桶的 3 × 3 邻桶。弦上任何一点离最近的取样点不超过半个桶，它所在的桶必在那个取样点的 3 × 3 邻桶里，不会漏掉线段。

线段和桶各带一个 epoch_ 计数。每次查询先把 epoch_ 加 1，测过的线段、扫过的桶记下当前值，同一段、同一桶在一次查询里只测一遍。epoch_ 是 32 位整数，加到回绕成 0 时把整张表清零。

求交。弦从 p 到 q，记 $r=q-p$；一条障碍线段从 a 到 b，记 $s=b-a$。交点在弦上的参数 t 和在线段上的参数 w 是：

这里 $u\times v=u_x{v}_y-u_y{v}_x$ 是二维叉积。对每条候选线段：

1. 包围盒不重叠，跳过。
2. $|r\times s|\le 10^{-12}$，即弦与线段平行或共线，跳过。共线重叠因此不会判为相交。
3. 取 $\epsilon =10^{-7}$，满足 $\epsilon <t<1-\epsilon$ 且 $-\epsilon <w<1+\epsilon$，判为相交。

两侧区间的开闭不同。线段一侧把区间放宽到端点以外：障碍线段是格边，精确 45° 的弦每次都正好交在格边端点上，如果端点不算，它会从两段轴对齐线段的公共顶点之间穿过去。弦一侧把区间收到端点以内：弦的端点搭在障碍线段上，算贴墙走。

on 掩膜。障碍线段都没交上，再按 on 掩膜密采样：取 $\lfloor L/0.125\rfloor +2$ 个等距点，最后一点就是 q，任一点所在格在窗口外或不在掩膜里，视线就不通过。

搜索用的 vis 没有障碍线段，桶索引是空的，直接查 on 掩膜。终点格不在开阔区里时，最后一个采样点（也就是 q）必然落在掩膜外，所以窄处的格在搜索里总是验不过视线，见 Lazy Theta*。

示意图。上图是障碍线段求交：红弦以 45° 正好穿过两段格边的公共端点，左段 $w=1$、右段 $w=0$，线段一侧的区间放宽到 $(-\epsilon ,1+\epsilon )$，两段都算交上；绿弦的端点落在障碍线段上，$t=1$，弦一侧取开区间，不算相交。下图是桶索引：桶边长 4 像素（16 格），这条弦取 11 个点，橙色是其中一点要扫的 3 × 3 邻桶。

立面禁步

crossesStep 沿数字直线逐步查：前后两格都在窗口内，且两格之间有禁步边，视线不通过。禁步边是有向的，按行进方向查。

搜索逐格展开时，禁步边只拦水平方向的一步，落差超过 3 的下落可以越过它。视线判据一律拦：一条弦里不能夹带下落，下落只能作为单独的一个格步出现，Lazy Theta* 也不会把下落之后的格直接连到祖父节点上。

禁步边的判据见禁步与立面段。正交方向的禁步边同时生成立面段，进入障碍线段；对角方向的禁步边没有对应的立面段，只靠 crossesStep 拦。

高度连续检查

障碍线段和立面禁步都只在平面上判断。叠层地形上，一条弦的水平投影可能一半在桥上、一半在桥下，平面判据分不出来。高度连续检查（LayerOracle）沿弦逐格跟踪高度，判断弦是否一直走在同一层上。

这项检查只负责不换层。立面已经由障碍线段和禁步拦住，所以向上的容差按体素取样的误差放宽：高度取自格心，斜面和接缝上相邻两格的取样差本来就可能超过一步向上的上限。按拓扑层的标准卡，大量本可直走的弦会被判为不通，拉直就退化成沿网格的锯齿线。

walk(pts, h) 的步骤：

1. 用数字直线取折线经过的格，去掉连续重复的格，再去掉窗口外的格。
2. 当前高度集合 cur 取起点高度，参考格 pc 取起点格。起点格不检查。
3. 对后面每一格：
   1. 取这一格的全部 span 高度。没有 span 的空列跳过，pc 不前移。
   2. 按下式算向上的上限 up。
   3. 一张 span 的高度 t 只要相对 cur 里某个高度 c 满足 $-3\le t-c\le \mathrm{up}$，就留下。
   4. 一张都没留下，返回无解；否则 cur 换成留下的高度，pc 前移到这一格。
4. 返回 cur，即弦末端可能所在的高度。

w 是本格格心到 pc 格心的欧氏距离，以格为单位。常数 1 是 kQH，体素取样的高差容差，要容得下斜面上一格的起伏和格心取样的偏差。UpAllow 取两项的较大者：0.5 是可直接迈上的台阶高 kStepUp；$0.25w$ 是坡度上限 kSlope = 1 乘以水平距离 $0.25w$ 像素。

ok(p, q, h, hq) 在 walk 的结果里找一个与 hq 相差不超过 $10^{-3}$ 的高度。walk 另有放行下落的模式，只在落点留余量求高度时用。

几个要点：

• 一组可达高度。cur 是集合，同一列里几层都接得上就一起留下，到终点再看落在哪一层。
• 上限。相邻两格正交时 $w=1$、对角时 $w=\sqrt{2}$，UpAllow 都是 0.5，上限 1.5；沿正交方向跳过一列空列时 $w=2$，上限仍是 1.5；连跳两列时 $w=3$，上限放宽到 1.75。
• 下限。一步最多降 3（kClimb），与搜索里向下一步的上限相同；落差更大的下落在搜索里单独成一步，所以弦里不能有下落。
• 空列。空列直接跳过，弦越过一片没有 span 的空洞时，这项检查不拦，要靠障碍线段和 on 掩膜拦。
• span 来源。检查读窗口 span 表里这一列的全部 span，不看可用位，别类的普通记录也在表里，见展开成栅格图层。多出来的候选高度只会让检查更宽松，能通过的弦仍然能通过。

示意侧视，横轴是弦依次经过的列。起点格高 10.0，不检查。每一列的绿带是允许的高度范围 $[c-3,c+\mathrm{up}]$。第 3 列有桥面 10.2 和桥下地面 6.0，地面低于下限 7.1，丢掉，cur 只剩桥面。第 5 列是空列，直接跳过；第 6 列到参考格的距离是 2，上限仍是 $c+1.5$，连空两列才放宽到 $c+1.75$。终点高 10.6 在最后的 cur 里，视线通过。

拉直和拐点抬升也用高度连续检查。拉直时 h 是这一段起点的 span 高度。拐点抬升逐段检查，第一段从起点 span 的高度出发，每段检查完从结果里取离出发高度最近的那个，作为下一段的出发高度。

后处理

几何层交出父指针链以后，routeWindow 还要做七步：拉直、端点拼接、对回搜索面高、拐点抬升、逐点高度、落点留余量、路点。拉直、端点拼接和拐点抬升三步各自计时，各步的中间折线随诊断一起交出。

拉直的输入

拉直的输入按几何层的结果分三种：

第二种发生在几何层两次都无解、保留拓扑层的逐格路径时，或者两端吸附锚点在同一格时。

路线掩膜 tm。拉直用的障碍线段是 core 轮廓、墙段和立面段，on 掩膜是这条路线自己的路线掩膜 tm，由四步得到：

1. 从开阔区 solidc 出发。
2. 并上两端的端点接入路径。
3. 与最终那次求解的掩膜取交集。
4. 逐格路径上每一格的 3 × 3 邻域里，凡在最终那次求解的掩膜里的格都置 1。

tm 从开阔区出发，是因为几何层搜索计价时 on 掩膜也是开阔区。两处用同一套判据，搜索挑出来的居中拐点在拉直时依然成立；换一套阈值，拉直会把它们切回墙边。拓扑层放宽过的腿也这样处理：放宽只是为了让拓扑层接通，几何层再跟着放宽，弦就会穿过那些窄缝。连不成弦的段退回逐格路径，那条路径本来就沿着中轴。第 4 步把逐格路径本身向外扩一格并进来，端点接入路径和格级回退的路径走过的格才不会被自己的掩膜挡掉。

拉直

拉直（string pulling）把折线上能互相看见的两点之间的中间点删掉，像把一根松弛的绳子拉紧。它在整条折线上做：一段能直走就直走，判断标准只有两端能否互相看见。障碍线段和路线掩膜就是这条路线的通道边界，拉直出不了通道，也就不必再把落点限制在原路径两侧。

Lazy Theta* 交出的父指针链只是近似紧绷（taut）：在净空不到开阔区门槛的窄处，搜索验不过视线，只能逐格走，留下一串相邻的格心。拉直按“最远可见”再做一遍，判据换成 vis_geo，它的 on 掩膜是更宽的路线掩膜，这些点还能并成弦。

StringPull 的做法：

1. 锚点 i 从第一个点开始。
2. j 从最后一个点往回扫，扫到 i + 2 为止，第一个看得见的 j 留下。
3. 扫到 i + 2 都看不见，就取 j = i + 1，这一步不验视线。
4. 锚点跳到 j，重复，直到最后一个点。

这个过程做一遍就稳定，对输出再做一遍，结果不变。第二遍从某个锚点 c 出发时，候选是输出里 c 之后第二个起的那些点；它们在原序列里的下标都大于第一遍从 c 选中的那个点，第一遍从 c 往回扫时已经判过看不见。视线判据只看两个端点，同一对端点每次结果相同，所以第二遍会找回同一个点。

示意图。① 锚点 0：从 9 往回扫，9 到 5 都被挡，4 第一个看得见，留下 4。② 锚点 4：9 到 6 都被挡，扫到 $i+1=5$，不验视线直接收下。③ 锚点 5 直接看到 9，结果 0 → 4 → 5 → 9，10 个点剩 4 个。

相邻两点之间默认可走。输入是父指针链时，相邻两点之间要么是搜索用 vis 验过的弦，要么是一格的邻步。vis 不带障碍线段，邻步也不看墙段，所以跨过墙段的那一步 vis_geo 判不过，拉直照样收下，实测见直接收下的邻步与 Dead 格。输入是逐格路径时，相邻两点是八邻格心。

端点拼接

1. 折线前面接原始起点，后面接原始终点。端点用的是吸附之前的坐标。
2. 中间点离起点或终点不超过 0.4 像素的去掉。
3. 相邻两点距离不超过 $10^{-9}$ 的去重。
4. 输入是父指针链时再去共线点：上一个保留点 a、当前点 b、下一点 c 满足下式，就删掉 b。

其他常见的折线清理在这里都用不着。父指针链取自搜索树，树上的路径不会两次经过同一个点，折线没有环要去；拉直之后留下的点都是拐点，也没有可抽稀的点。三点共线时，a → b 和 b → c 首尾相接正好就是 a → c，删掉 b 折线形状不变。

拐点抬升

拉直后的折线贴着障碍角转弯。拐点抬升（LiftCorners）把拐点朝净空更大的一侧挪，最多挪 kLiftMax = 0.5 像素。挪过的拐点连出两条新弦，新弦要通过视线判据，沿线的最小净空也不能比原来低：新弦如果穿过一道窄缝，沿线最小净空必然下降，这一条就能把它拦住。只有净空严格大于拐点所在格的格才算候选；拐点所在格的净空已经是附近最大的，拐点就一格不动，这时它离墙近是因为通道本身就窄。

拐点抬升放在拉直之后。顺序反过来的话，挪开的拐点让前后两点更容易互相看见，拉直会直接把它删掉。

搜索半径 $\mathrm{lround}(0.5/0.25)=2$ 格，候选是满足 $d{x}^2+d{y}^2\le 4$ 的 12 个格，不含拐点自己所在的格。对每个中间拐点 $P[i]$ 按顺序原地修改，后一个拐点看到的是前一个挪过之后的位置：

1. 从上一段的出发高度沿 $P[i-1]\to P[i]$ 做高度连续检查，不通就结束整个拐点抬升，后面的拐点都不再挪。拐点所在格在窗口外时跳过这个拐点。
2. 拐点所在格的净空记为 here；两条原弦 $P[i-1]\to P[i]$、$P[i]\to P[i+1]$ 沿线最小净空的较小者记为 keep。
3. 候选是圆内净空严格大于 here 的格，按净空从大到小排；净空相同时按线性格号 $y{n}_x+x$ 从小到大排。这个顺序没有并列，同样的输入每次挑中同一个格，输出逐位可复现。
4. 每个候选取格心 w，依次做五项检查，第一个全部通过的候选替换 $P[i]$：
   1. w 离 $P[i-1]$ 或 $P[i+1]$ 不到半格（0.125 像素）就跳过。挪到与邻点重合会产生零长度的线段，导航侧从零长度线段上取不到方向。两个不同格心至少相距一格，半格的阈值能拦住重合，又不会挡掉合法的一格位移。
   2. 两条新弦 $P[i-1]\to w$、$w\to P[i+1]$ 沿线的最小净空都不低于 keep（比较时留 $10^{-9}$ 的浮点余量）。
   3. 新弦不与隔一段的折线段相交：$P[i-1]\to w$ 不与 $P[i+1]P[i+2]$ 相交，$w\to P[i+1]$ 不与 $P[i-2]P[i-1]$ 相交。中间那一段比位移还短时，挪一下就可能把它翻过去，折线出现自交。
   4. $P[i-1]\to w$、$w\to P[i+1]$ 的高度连续检查都能通过。
   5. 两条新弦都通过 vis_hard。

弦沿线的最小净空由 SegMinClr 计算：沿数字直线取格，取各格净空的最小值，窗口外的格不计。它取格的方式与高度连续检查相同，两项检查对“这条弦经过哪些格”给出同一个答案：

double SegMinClr(const Grid<float>& d, double x0, double y0, const WorldPoint& a, const WorldPoint& b)
{
    const int64_t ax = static_cast<int64_t>((a.x - x0) / kCS);
    const int64_t ay = static_cast<int64_t>((a.y - y0) / kCS);
    const int64_t bx = static_cast<int64_t>((b.x - x0) / kCS);
    const int64_t by = static_cast<int64_t>((b.y - y0) / kCS);
    const int64_t n = std::max<int64_t>(std::max(std::abs(bx - ax), std::abs(by - ay)), 1);
    double m = std::numeric_limits<double>::infinity();
    for (int64_t k = 0; k <= n; ++k) {
        const int64_t cx =
            ax + static_cast<int64_t>(std::nearbyint(static_cast<double>(bx - ax) * static_cast<double>(k) / static_cast<double>(n)));
        const int64_t cy =
            ay + static_cast<int64_t>(std::nearbyint(static_cast<double>(by - ay) * static_cast<double>(k) / static_cast<double>(n)));
        if (cx < 0 || cy < 0 || cx >= d.nx || cy >= d.ny) {
            continue;
        }
        m = std::min(m, static_cast<double>(d.at(cy, cx)));
    }
    return m;
}

新弦与隔一段的折线段是否相交由 SegCross 判断。记 $\sigma (a,b,c)=(b-a)\times (c-a)$，它的正负表示 c 在直线 ab 的哪一侧。SegCross 把 $\sigma >0$ 算作一侧、$\sigma \le 0$ 算作另一侧，两条线段都满足“对方的两个端点分在两侧”才算相交。完全共线时四个叉积都是 0，不算相交。

只有能做高度连续检查（前两种输入）且折线至少 3 个点时才做拐点抬升。

示意图。拐点 $P[i]$ 贴墙，净空 0.25，两条原弦沿线最小净空的较小者 keep 也是 0.25。圆内净空严格大于 0.25 的格按净空从大到小编号，打叉的格净空不高于 here，不是候选。① 净空 0.75，新弦 $P[i-1]\to$ ① 与隔一段的 $P[i+1]P[i+2]$ 相交，放弃；② 净空 0.56，新弦穿墙，沿线最小净空 0 低于 keep，放弃；③ 净空 0.56，五项检查都通过，$P[i]$ 挪到这里。

逐点高度

每点的高度有两份。

搜索面高。端点拼接之后，中间点按顺序对回拉直输入里坐标相同的那一点，取搜索给它挑的那张 span 的高度。匹配位置只往前推进，路线在叠层处两次经过同一坐标时，各自对上自己那一遍的高度。起点和终点用拉直输入首尾两点的高度。拐点抬升挪过的点，换成新格上与原高度相差不超过 1.0（kQH）的面里最近的那一张。任一点对不上或找不到，整列清空；拉直输入没有每点高度时（基线走了格级回退），这一列为空。这一列随路线交给展开器（9839304「叠层处重规划起点层与下落判定」、ff3a956「下落落点面高与抬升拐点面高」）。

沿线推算的高度。从起点 span 的高度出发，对每一段做高度连续检查，下一段从这一段返回的整个高度集合出发，每点记下集合里离上一点最近的那个高度。起点高度是唯一的外部输入，后面每点都由上一点推出来，叠层处因此不会串到另一层。任一段不通就清空整列。这一列只在进程内给路点用。

落点留余量改过的高度（挪过的落点、找台沿时顺着上层经过的点）随后写回：有搜索面高时两列都更新，没有时只更新沿线推算的那一列。

最终路线还有一份逐点净空：每点所在格的净空，坐标夹进窗口，上限 12，禁区里为 0。它是点到最近障碍的距离，点在中轴上时等于通道半宽。

落点留余量

区的平面变换缩放非零时，后处理把台沿下落的落点从台沿脚下往外挪，并把落点记进落点表（#6147「台沿下落落点留余量」、9839304「叠层处重规划起点层与下落判定」、ff3a956「下落落点面高与抬升拐点面高」）。缩放为 0 时整步跳过。

判下落用的高度。每点取搜索面高；搜索面高这一列为空时，用沿线推算的高度；那一列也为空时，用放行下落的高度连续检查重算一遍。放行下落的模式里，比当前高度低 3 以上的面也收下；但如果沿行进方向往前 1 到 4 格（kSeamCells）又出现出发的那一层，就判为路面上的一道缝，留在出发那层跨过去。某格的面一张都接不上时，保留原来的高度集合，再把这一格的面全部加进去（跨缝时只保留原来的）。这种模式下检查总能走完。

找台沿。相邻两点高差超过 3（kClimb）、且两点不重合时，后一点是下落候选；首末两点不当落点。从前一点出发，沿折线每 1/16 像素取一个采样点，在采样点所在格里找离当前上层高度不超过 1.0 的面，跟着它走：

• 中途某格接不上：这时的上层高度比这一段终点高 3 以上，这一段的终点就是落点；否则跳过。
• 走完这一段时，上层高度已经降到终点 3 以内：这是一道坡，跳过。
• 走完这一段，上层仍比终点高 3 以上：上层覆盖了这一点，顺着折线接着找下一段，途经各点的高度改成上层高度。上层一直延伸到终点的前一点都没断开，跳过。

挪落点。落点要挪到离上层可走面 $4r$ 远的地方，$r=0.41\times |s_x|$：0.41 米是角色半径（kFallRadius），$s_x$ 是区的平面变换在 x 方向的缩放。取 $4r$ 是因为可走面本身已经从地面边缘向内缩了约 $r$，角色离开台沿还要再走 $r$，余下 $2r$ 留作余量。

1. 从落点所在格出发，在下层按格心到原落点的距离由近到远逐格扩展（四邻）。邻格上有与当前格的面相差不超过 1.0 的面才接得上；格心离原落点超过 $8r$ 的格不扩展。
2. 取出的格要能从格心直走到下一点，原落点本身免检；不通的格仍然继续向外扩展。直走只用高度连续检查判断：障碍线段和立面都是平面判据，叠层处上层的墙会连下层的弦一起挡掉。
3. 量这一格离上层面的距离。上层面指高度 v 满足 $h+3<v\le h_{\mathrm{up}}+3$ 的面，h 是本格的面高，$h_{\mathrm{up}}$ 是台沿高度；距离量到那一格方块上的最近点。距离达到 $4r$ 就取这一格，停止；一直达不到，就取检查通过的格里离上层面最远的一格。
4. 在落点表里记一项（落点下标，下层面高）。落点挪动后，坐标改成新格的格心，高度换成下层面高，净空换成新格的净空。

落点留余量的判据全部来自窗口格图。落点在路点里总会被留下。展开器把它标成严判点，带上下层面高和起跳点，见 MapNavigator 一文的规划结果。

路点

PullWaypoints 在最终路线里挑出导航侧要停靠的点，记下它们的下标。做法是贪心：从上一个路点出发，沿折线尽量往前延伸，直线走不通就把停下的那个顶点收为路点。一条弦要同时通过两项判断：区网格上的高度连续，以及不穿过窗口里的障碍线段。只查前者，叠层处可能顺着另一层走通；后者按窗口里的墙把这种弦挡掉。

1. 没有高度连续检查（第三种输入）时不出路点，交给调用方拉直。
2. 从当前路点出发，依次试能不能直接连到下一个顶点，两项判断都通过就再往前试一个：
   • 区网格上的 isRouteSegmentDrivable：沿弦大约每 0.5 像素取一个采样点，每个采样点都要落在区网格的三角形上，相邻采样点的地面高差不超过 3。半宽取这条弦跳过的中间顶点里最小的净空，还没有跳过任何顶点时取 0。半宽大于 0 时，除了中线，再查左右各平移一个半宽的两条边线；边线两端各往里收 $\min (\text{半宽},L/2)$，L 是弦长。端点是路线已经定下的位置，常常贴着墙，往里收是为了不让端点旁边的地面影响判断。起点高度取沿线推算的高度里当前路点那一个：不给起点高度时，第一个采样点没有参照，叠层处会取最低的面，判断可能顺着下面那层一路走通；给了以后，整段采样都锚在起点所在的层上。
   • 拉直用的那组障碍线段和路线掩膜。
3. 一次最多跨过 64 个顶点（kMaxPullSpan）。每多延伸一个顶点都要把整条弦重测一遍，不设上限的开销是平方级；碰到上限只是多留一个路点。
4. 往前延伸时不越过下一个落点：落点下标落在这次的延伸范围里时，上限截到落点，落点因此总会留成路点。导航侧要靠这个点判断角色有没有跳下去。展开器自己的拉直也按同样的规则截断。
5. 一个都延伸不了时强行前进一个。这时连折线自己的下一条边都过不了判断，把那个顶点原样留下已经是最好的选择，也保证循环一定往前走。
6. 停下的顶点记为路点，下一轮从它出发；最后总记上终点下标。

半宽取跳过的顶点里最小的净空，捷径因此不会比它跳过的最窄处更窄；那个宽度是路线在这段通道上自己走出来的，拉直沿用它。导航侧怎么用这些路点，见 MapNavigator 一文的走廊跟随。

诊断

规划器除了交出路线，还把每一段算法的中间结果一起交出：拓扑层的逐格路径、几何层的父指针链、拉直和端点拼接之后的折线。调试工具把这些点列叠在地图上，就能看出路线在哪一步走歪。规划失败时同样交出这些结果，另外尽量给出断开处的位置。

断开处的定位

断开处是起点一侧能走到的格与终点一侧能走到的格之间，平面上离得最近的一对格。基线在最终那一档窗口里无解时，routeWindow 先定位断开处，再写错误说明。小窗里基线无解直接换到下一档，不定位；封顶档会定位，但只要整类窗口不超过 kMaxCells 格，就换整类窗口重算，封顶档的结果随之作废。

1. 两端的 span。先用 core 掩膜和可达域筛出可用的 span。起点取吸附锚点里与种子高度最接近的那一张；终点取吸附锚点里的全部可用 span，声明了终点面时只取声明的那一张。任一端为空就不定位。
2. 两次泛洪。从起点正向泛洪，得到起点能走到的 span 集合 ra；从终点反向泛洪，得到能走到终点的 span 集合 rb。终点一侧要找的是“从这里能走到终点”的 span，下落又只能单向走，所以要沿着边的反方向泛洪。两次泛洪都按搜索的展开规则走，差别见可达域。
3. 距离场。把 rb 覆盖的格的距离记为 0、来源记为自己，再用倒角距离变换把距离传播到整个窗口。
4. 取最近的一对。在 ra 覆盖的格里找距离最小的那一格，距离相同时取格号小的。这一格和它的来源格就是断开处的两端。
5. 输出。两端各取格心坐标，距离是两个格心之间的欧氏距离，单位像素。

倒角距离变换（chamfer distance transform）⁠^[23]用整数权重近似欧氏距离：正交走一格记 100，对角走一格记 141，约等于 $100\sqrt{2}$。它只扫两遍网格：第一遍从左上到右下，每格看左上、上、右上、左四个已经扫过的邻格；第二遍从右下到左上，看右下、下、左下、右四个邻格。每看一个邻格 b，就对当前格 c 做一次更新：

更新成功时，c 的来源也换成 b 的来源。两遍扫完，每格记着到最近一个 rb 格的倒角距离，以及那个格是哪一格。墙格和窗口里所有格都参与传播，所以这是平面上的距离，不管中间能不能走。

逐对比较要把 ra 的每一格和 rb 的每一格都算一次距离，开销是两边格数的乘积；倒角距离变换的开销只与窗口格数成正比。倒角距离最多比欧氏距离偏大约 8%，挑出的是近似最近的一对；报出的距离是这一对格心之间的欧氏距离。

泛洪用的是 core 掩膜，它是最宽松的可走掩膜。在 core 上两侧都连不上，说明断开是真实存在的，换哪一档更严的掩膜都接不上。

示意图。(a) 俯视：蓝色是起点侧 ra，绿色是终点侧 rb，灰色不在 core 里，黑线是距离场的等值线（倒角距离 / 100，单位格）。距离场从 rb 向外传播，穿过灰格也照常传播。ra 里距离最小的格离 rb 3 格，两格心相距 0.75 像素。斜线格在 core 里，起点却走不到，它不属于 ra，倒角距离 200 也不参与比较。(b) 侧视：起点在桥面上，终点在桥下的路面上，两侧可达集在平面上重叠。

上下两层。两侧可达集在平面上有重叠格时，重叠格的距离是 0，最小值必然是 0：断开处两端重合，距离为 0，位置是格号最小的那个重叠格。定位只量平面距离，不区分上下层。

用途。调试工具在断开处两端画圈并标出距离；展开器在声明了目标面的腿上用它给失败分类，见下一节。

失败的情形

规划从入口到出结果，失败可能发生在下面几处。每种情形规划器只给出一句错误说明，展开器再按情形决定接下来怎么做。

建窗之前。这些情形在整区上就能判断，失败即结束：

1. 起点或终点离区网格太远：吸附半径 8 像素（kSnapRadius）内找不到三角形。
2. 起点或终点落在虚拟禁区里。规划器把这次失败标成禁区失败。
3. 端点到核心可走区的距离超过 8 像素。全区的核心包含任何窗口里的核心，在全区上都接不上，换多大的窗口也接不上，见端点到核心可走区的距离。
4. 数据读不出来：预烘格图解码失败、旁包读不出来、旁包的判据常数与运行期不一致，见读取路径和旁包校验。

建窗与窗内搜索。这些情形按档处理，档位见椭圆档位：

5. 整类窗口超过 kMaxCells（4 亿格）：直接失败。
6. 建窗失败，例如起点的种子格在窗口外、起点格里没有与终点同类的 span（见建窗和种子与离网连接）：小窗换到下一档，封顶档换到整类窗口，整类窗口直接失败。
7. 小窗里求不出路线，或者小窗结果没通过检查：换到下一档，不定位断开处，见放大窗口的原因。
8. 封顶档里求不出路线：基线无解时先定位断开处；之后只要整类窗口不超过 kMaxCells 格，就换整类窗口重算。
9. 最终那一档基线无解：定位断开处，然后失败。没有声明终点面时报两端不连通；声明了终点面时报目标面不可达，并列出终点格里各张面的高度。

有路线，端点没接上：

10. 路线求出来了，但起点或终点到起点可达域的距离超过 8 像素，或者终点所在格可走、却被不许跨的格边隔开。这时先试台沿下落换类：起点一侧在 8 像素以内、终点没被格边隔开、也没有声明终点面时，从本类的台沿跳进终点所在的类，前后两段分别规划。跳不过去就失败，错误说明里带上两端到可达域的距离。

第 10 种失败不带断开处。端点先吸附到起点可达域里的格上（见掩膜与吸附锚点）。终点在另一片可达域时，它的吸附锚点落在起点这一侧离它最近的格上，基线照常走通，断开表现为终点到可达域的距离。断开处的定位要等基线在可达域内部都接不通才会运行。

展开器的处理：

• 禁区失败：记 route_no_go，结束。滑索、盲走探针这些替代办法都不看可走面，交给它们就会穿过禁区。
• 其余失败先试连续滑索：步行走不通时，滑索可能分别接上起终两侧的可走面。
• 声明了目标面的腿不用盲走探针。盲走只看平面位置，走到目标正上方也算到达，会把走错层当成成功。这种腿按有没有断开处给失败分类：两端都有，记 route_disconnected（目标面与起点不连通）；没有，记 target_deck_unreachable（目标面不可达）。终点格里没有声明的面时，终点一侧的 span 为空，不定位断开处，分类为 target_deck_unreachable，与实际情形一致。
• 没有声明目标面的腿，按 MapNavigator 一文规划结果里的顺序改用盲走探针或作者路线。
• 规划器没给错误说明、或给出的点不到 2 个时，展开器同样按失败处理。

实测

前面几节已经用过本机日志里的数字：分档的分布见分档实测，拓扑段和几何段的耗时见搜索实测。日志不记录点列，也不记录拉直、端点拼接、拐点抬升三段的耗时，这一节前四小节的数字来自路线预览查询（route_preview），最后一小节是日志里的失败分布。

取样

仓库里任务路线的 NAVMESH 路点，每个和它前一个路点组成一条腿，按（区，起点，终点）去重得到 37 条：Wuling_Base 23 条，ValleyIV_Base 12 条，Wuling_L4_328 2 条。每条腿单独做一次路线预览查询，路线是起点加一个 NAVMESH 路点，在同一个进程里依次跑，代码版本是 28de7e4。

34 条成功，每条恰好产出一项诊断，诊断里的起终点与请求逐位相同，没有走滑索，也没有改用盲走探针。失败的 3 条：Wuling_L4_328 的 2 条起点离区网格太远，Wuling_Base 的 1 条终点不在起点的可达域里，见失败的情形。

分段耗时

34 条腿的各段耗时：

建窗只计最终那一档。「其余」是总计减去前六项，包括建窗之前的检查与选类、被放弃的前几档、拐点抬升之后的逐点高度、落点留余量和路点，这几样都没有单独计时。窗口小于 290 万格的 28 条腿，其余部分中位 30.1 ms，最大 137 ms；其余部分超过 340 ms 的 5 条腿，最终窗口都在 300 万格上下，合计 3114 ms，占其余部分的 72%。

拉直、端点拼接、拐点抬升三段合计 106 ms，占总计的 0.95%。路线预览查询的墙钟时间中位 124 ms，比规划器自己记的总计多 10 ms 左右，这部分是展开器和查询本身的开销。

点数的变化

几何层的父指针链只有逐格路径的一半，拉直再去掉 85%。按端点拼接一节的四步离线重算，34 条腿的结果逐点相同：

1. 两端接上原始起终点，加 68 个点。
2. 离端点不超过 0.4 像素的点去掉 71 个，其中 63 个是拉直结果的首点或末点，也就是两端吸附锚点的格心。
3. 重合点去重 0 个。
4. 共线点删掉 155 个，分布在 21 条腿里。

拐点抬升只挪点、不增删，最终路线的点数与端点拼接之后相同。

拐点抬升的位移

去掉两端，34 条腿共有 525 个中间拐点，拐点抬升挪动了其中 172 个，分布在 27 条腿里。搜索半径 2 格，候选格心相对原拐点的位移只有三种：

七成挪到了半径的上限。候选按净空从大到小试，离墙越远净空越高，第一个通过五项检查的候选往往就在圆的边上。

直接收下的邻步与 Dead 格

拉直的第 3 步在扫到 i + 2 都看不见时直接收下 i + 1，不验视线，见拉直。34 条腿的 751 个拉直点之间有 717 段，其中 290 段（40%）直接取了父指针链上的下一个点：10 段是父指针链的最后一段，没有更远的候选；其余 280 段是更远的候选全部被 vis_geo 否决。29 条腿里都有这种直接收下的邻步，最多的一条 128 段里有 56 段。

把这些邻步两端所在的格在格图里查出来，看格里有没有高度相近的 Dead span（点的高度取拓扑层逐格路径上平面最近那一格的高度，相差 3 以内算相近）：

Dead 位来自标墙（StampWalls）：沿可走三角的边界边取点，点所在格里高度相近的 span 都标成 Dead，见标墙。这些邻步落在 Dead 格上的比例是对照的 9 倍。

这些 Dead 记录的净空：邻步两端共 246 条，245 条带 Core；净空中位 1.75 像素，1 像素以上 152 条，为 0 的 58 条。净空场把大部分这类 Dead 格当成路面中间的格。开阔区只看净空，净空达到门槛的 Dead 格也在开阔区里，搜索的弦可以越过它们。

实测图，Wuling_Base 的一条腿，起点 (1252.24, 1744.17)，终点 (1369.87, 1533.92)。(a) 整条腿：灰带是拓扑层逐格路径，蓝线是最终路线，红圈是 56 处直接收下的邻步。(b) 一段直路放大：白格是本层 core，深灰是 Dead 格，橙点是父指针链，空心圈是拉直点，红线段是直接收下的邻步，红叉是端点拼接删掉的共线点。路面上横着几道一格宽的 Dead 格带，这些格同时带 Walk 和 Core，父指针链逐格走过去；拉直从格带前的点看不到格带后的任何一点，只能逐格收下，到下一道格带之前才又能拉直。图中这一段的邻步两端高差不超过 0.12，格之间也没有禁步位，跨过去的是同一层路面。

标墙保留下来的墙段只进障碍线段，拦的是 vis_geo、vis_hard 和路点。几何层搜索用的 vis 不带障碍线段，逐格展开只看掩膜、切角、禁步和向上一步的判据，所以父指针链照常跨过这些格带，拉直再把跨过去的那一步当作邻步直接收进最终路线。

共线点。端点拼接删掉的 155 个共线点，前后的 a、c 都是拉直点，删点只算叉积。三点共线，删 b 不改变折线的形状，只把相邻几段并成一段。并出来的弦有 72 段（端点拼接后共 559 段），在 21 条腿里，长度中位 2.8 像素，10 像素以上 9 段，最长 47.75 像素；拐点抬升只挪过其中 1 段的端点。

失败的分布

本机 27 份日志（含滚动备份，时间 2026-09-26 到 10-03）里共有 1444 次规划失败，这批日志早于 #6227「同类走不通时经台沿跳下换类续规划」。组成如下：

1. 终点不在起点的可达域里。全部在 map02base，端点都在可走面上，没有一次是被不许跨的格边隔开。1316 次只对应 76 种（区，终点到可达域的距离）组合，同一批腿被反复规划。终点到可达域超过 500 像素的 948 次，16 到 50 像素的 120 次，16 像素以内的 248 次；起点到可达域的距离大于 0 的只有 12 次。
2. 种子格在窗口外、起点格里没有同类 span、端点离核心可走区太远。这三种集中在 2026-09-30 20:12 到 10-01 15:02 的 19 个小时里，map01base 和 map02base 都有。
3. 端点离核心可走区太远。24 次只有两种距离：起点 10.0 像素、终点 0.0 像素，和起点 15.8 像素、终点 0.0 像素，各 12 次，都是起点超过 8 像素。

这些失败发生时都没有运行期虚拟禁区。日志里没有一次是两端不连通或目标面不可达，断开处的定位一次也没有运行过。路线预览实测里失败的那条 Wuling_Base 腿，终点离起点可达域 26.0 像素，同样没有断开处。

参考资料

1. ↑ M. Mononen 等. Recast & Detour. GitHub，高度场与 span 的定义见 rcHeightfield 文档
2. ↑ P. E. Hart, N. J. Nilsson, B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2): 100–107, 1968. doi:10.1109/TSSC.1968.300136
3. ↑ M. Mononen. Simple Stupid Funnel Algorithm. 2010. 博客
4. ↑ D. T. Lee, F. P. Preparata. Euclidean Shortest Paths in the Presence of Rectilinear Barriers. Networks, 14(3): 393–410, 1984. doi:10.1002/net.3230140304
5. ↑ P. Deutsch. GZIP File Format Specification Version 4.3. RFC 1952, 1996. rfc-editor.org
6. ↑ DWARF Debugging Information Format Version 5, §7.6 Variable Length Data. 2017. PDF
7. ↑ Protocol Buffers Encoding: Signed Integers. protobuf.dev
8. ↑ L. Noll, K. Vo, D. Eastlake 3rd, T. Hansen. The FNV Non-Cryptographic Hash Algorithm. RFC 9923, 2026. rfc-editor.org
9. ↑ G. Fiedler. Snapshot Compression. 2015. gafferongames.com
10. ↑ B. A. Galler, M. J. Fischer. An Improved Equivalence Algorithm. Communications of the ACM, 7(5): 301–303, 1964. doi:10.1145/364099.364331
11. ↑ R. E. Tarjan, J. van Leeuwen. Worst-Case Analysis of Set Union Algorithms. Journal of the ACM, 31(2): 245–281, 1984. doi:10.1145/62.2160
12. ↑ J. Hasselgren, T. Akenine-Möller, L. Ohlsson. Conservative Rasterization. In GPU Gems 2, ch. 42, 2005. 在线版
13. ↑ S. Gottschalk, M. C. Lin, D. Manocha. OBBTree: A Hierarchical Structure for Rapid Interference Detection. SIGGRAPH 1996, pp. 171–180. doi:10.1145/237170.237244
14. ↑ T. Akenine-Möller. Fast 3D Triangle-Box Overlap Testing. Journal of Graphics Tools, 6(1): 29–33, 2001. doi:10.1080/10867651.2001.10487535
15. ↑ T. Saito, J. Toriwaki. New Algorithms for Euclidean Distance Transformation of an n-Dimensional Digitized Picture with Applications. Pattern Recognition, 27(11): 1551–1565, 1994. doi:10.1016/0031-3203(94)90133-3
16. ↑¹ ↑² A. Meijster, J. B. T. M. Roerdink, W. H. Hesselink. A General Algorithm for Computing Distance Transforms in Linear Time. In Mathematical Morphology and its Applications to Image and Signal Processing, pp. 331–340. Kluwer, 2000. doi:10.1007/0-306-47025-X_36
17. ↑ P. F. Felzenszwalb, D. P. Huttenlocher. Distance Transforms of Sampled Functions. Theory of Computing, 8(19): 415–428, 2012. doi:10.4086/toc.2012.v008a019
18. ↑ H. Blum. A Transformation for Extracting New Descriptors of Shape. In W. Wathen-Dunn (ed.), Models for the Perception of Speech and Visual Form, pp. 362–380. MIT Press, 1967.
19. ↑ F. Chazal, A. Lieutier. The λ-Medial Axis. Graphical Models, 67(4): 304–331, 2005. doi:10.1016/j.gmod.2005.01.002
20. ↑ P.-E. Danielsson. Euclidean Distance Mapping. Computer Graphics and Image Processing, 14(3): 227–248, 1980. doi:10.1016/0146-664X(80)90054-4
21. ↑ R. E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2): 146–160, 1972. doi:10.1137/0201010
22. ↑ R. Wein, J. van den Berg, D. Halperin. The Visibility–Voronoi Complex and Its Applications. Computational Geometry: Theory and Applications, 36(1): 66–87, 2007. doi:10.1016/j.comgeo.2005.11.007
23. ↑¹ ↑² G. Borgefors. Distance Transformations in Digital Images. Computer Vision, Graphics, and Image Processing, 34(3): 344–371, 1986. doi:10.1016/S0734-189X(86)80047-0
24. ↑ E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1: 269–271, 1959. doi:10.1007/BF01386390
25. ↑ T. Lozano-Pérez, M. A. Wesley. An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles. Communications of the ACM, 22(10): 560–570, 1979. doi:10.1145/359156.359164
26. ↑¹ ↑² A. Nash, S. Koenig, C. Tovey. Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D. AAAI 2010, 24(1): 147–154. doi:10.1609/aaai.v24i1.7566
27. ↑ A. Nash, K. Daniel, S. Koenig, A. Felner. Theta*: Any-Angle Path Planning on Grids. AAAI 2007, pp. 1177–1183. PDF
28. ↑ J. E. Bresenham. Algorithm for Computer Control of a Digital Plotter. IBM Systems Journal, 4(1): 25–30, 1965. doi:10.1147/sj.41.0025
29. ↑ D. Cohen-Or, A. Kaufman. Fundamentals of Surface Voxelization. Graphical Models and Image Processing, 57(6): 453–461, 1995. doi:10.1006/gmip.1995.1039
30. ↑ E. Andres, P. Nehlig, J. Françon. Supercover of Straight Lines, Planes and Triangles. DGCI 1997, LNCS 1347, pp. 243–254. doi:10.1007/BFb0024845