TL2 走格寻路逆向分析：8 邻域 A*、恒 1.0 步长与平方启发，以及装饰物碰撞解耦机制

0. 核心结论速览 ​

1. 模块与入口：寻路模块位于 0x462F60–0x464400，共 24 个函数（已分析 8 个核心函数）。移动逻辑 sub_5425A0 调用 sub_464010(unit+112 /*世界X*/, unit+120 /*世界Z*/, goalX, goalZ) 触发寻路。
2. 8 邻域调用确认：sub_463940 中对 sub_4637B0 的 call 指令共有 8 处，整段 .text 对 sub_4637B0 的引用亦仅此 8 处。结点结构中分配了 8 个后继槽位（cmp ecx, 8 @ 0x463881），对应 8 邻域展开。
3. ★★★ 每步代价恒 1.0，启发函数为距离平方：每步代价固定增加 1.0（fadd dword ptr [0x213C5DC]，内存值为 float 1.0），斜向移动亦为 1.0；启发函数 $h = (dx)^2 + (dz)^2$（单位为格²）。由于启发不可采纳，原版无法保证最短路径。辅助证明：sub_463650 为向已闭合结点回传并更新更优 g 值的专用例程。
4. 起终点 ±16 格吸附：目标吸附 sub_463270 在 [cx−16, cx+16] × [cz−16, cz+16]（33×33 方格范围）内选取世界坐标欧氏距离最近的可走格，哨兵距离 9999.0；起点吸附 sub_4633F0 同样扫描 ±16 范围，但候选格额外要求周围具备净空。16 格对应 6.4 世界单位。
5. A 内核结构*：结点通过 calloc(1, 0x40) 分配（64 字节）；Open 表 ctx+12 与 Closed 表 ctx+16 均为单链表，sub_463220 按 f 值升序插入，主循环取表头；按索引查找结点采用单链表线性遍历（$O(n)$）。
6. 迭代上限与提前收敛退出：主循环存在迭代次数限制（if (i > *(DWORD*)(ctx+68)) break;），超出上限时以当前 h 最小结点作为局部路径返回，并清零完整路径标志（ctx+66 = 0）。若目标曾被吸附修正，只要当前最佳结点 $h < 2.0$（格²，约 1.41 格距离，常量地址 [0x2143F64]）即提前终止搜索。
7. ★★ 可行走判定与路径规划判定分离：CLevel::isWalkable（sub_5DB690）为单点无半径查表，判定单位能否在此处站立；寻路例程 sub_463940 具备净空要求（正交移动要求侧向有空格，斜向要求两个正交邻格均可走），判定能否规划路径通过。因此单格宽（0.4u）缝隙无法规划穿行，地图通道设计应至少预留 2 格宽。
8. 双层格网与阻挡极性：ctx+48 为主格网（必查），ctx+52 受 ctx+65 门控（仅为 false 时检查）。阻挡判定条件为有符号字节 $> 0$；255 解释为 $-1$ 视为可行走，与 isWalkable（有符号 $\le 0$ 可走）保持一致。
9. 地图连通分量分布：7 张官方测试地图走格并非单块整体，包含 3 至 67 个独立连通分量，主分量占比在 39.7% 至 92.1% 之间。寻路系统无“最大连通分量”概念，吸附格不可达即寻路失败。
10. ★★★ 静态模型碰撞脱节（幽灵墙现象）：7 张地图中 4,943 个标记为 OBSTACLE 的装饰道具中，有 639 个（约 13%）其坐标所在格子在 .mpp 中为可行走。TL2 原版不使用 3D 碰撞体裁剪移动，阻挡完全由 .mpp 走格决定，因此穿透部分装饰模型属于原版设计行为。
11. 未闭环事项：净空规则总开关 ctx+72 的写入条件、双层格网的具体职责分工、迭代上限配置值以及是否存在视线平滑（string pulling）例程尚未定位。

1. 模块位置、入口与函数清单 ​

寻路模块是 .text 里一段连续的区间：0x462F60–0x464400，ALLFUNCS/_realfuncs.json 落在该区间的条目共 24 个。本文已分析 8 个核心例程，职责如下：

其余未分析函数：sub_462F60 / sub_463030 / sub_4630A0 / sub_463130 / … / sub_4642A0 / sub_464360 等。部分高级机制（如平滑拉线）仍需结合剩余函数进一步排查。

入口：移动侧 sub_5425A0 调 sub_464010(unit+112, unit+120, goalX, goalZ)，其中 +112 / +120 是单位结构体里的世界 X / Z。

搜索方向：sub_464010 调的是 sub_463EA0(goalX, goalZ, startX, startZ, 1)——根结点是起点、终止条件是走到终点；最后那个 1 让它把 parent 链就地反转，结果读出来是「起点 → 终点」。起终点落在同一格时不跑搜索，直接置 ctx+67 = 1（=「已经到了」）。

MOD 开发结论：寻路系统为独立硬编码算法，不解析单位 DAT 配置，无法通过单位属性修改搜索行为；地图通行性仅由对应关卡的 .mpp 走格数据决定。

2. 走格取值：格子换算、两层格网、阻挡极性 ​

2.1 世界坐标到格坐标 ​

cell = floor((world − origin) × (1.0 / cellSize))

寻路上下文（下文写作 ctx）里与格网相关的字段：

2.2 两层格网 ​

ctx+48 永远查；ctx+52 只在 ctx+65 为假时查，两层的判定完全同形。

2.3 阻挡极性：有符号 byte > 0 ​

阻挡判定条件为有符号 byte > 0。这与 CLevel::isWalkable（sub_5DB690）的 setle（有符号 ≤ 0 视为可走）保持一致：数值 255 在两处均被解析为 −1（可行走）。

该判定与走格导出工具的解析规则 walk = (cells == 0) 相互印证——发行 .mpp 中的原始数据仅包含 {0, 1, 255}，255 在装载后进入内存不会被视为阻挡。

MOD 开发结论：走格数据中可行走判定采用区间模型（有符号 ≤ 0）。数值 255（−1）通常代表地图边界外或未定义瓦片，引擎将其视为可行走。编写走格编辑工具时切忌将 255 误判为实心阻挡。

3. 起点与目标的吸附：±16 格 ​

3.1 目标吸附 sub_463270 ​

目标格越界或被挡时，扫 [cx−16, cx+16] × [cz−16, cz+16] 这个 33×33 方块，把每个空格换算回世界坐标求欧氏距离，取最小。哨兵是 9999.0；一个空格都没有就原样返回。命中时把 ctx+64 置 1（=「目标被挪过」）。

字节层：lea ebx, [esi − 0x10] @ 0x4632DD、lea eax, [esi + 0x10] @ 0x4632E4；哨兵 float 9999.0 在 0x214882C。

3.2 起点吸附 sub_4633F0 ​

同样的 ±16 方块、同样的欧氏最近，但候选格额外要求周围有净空（见 §5）。

3.3 吸附机制的影响 ​

玩家点击阻挡区域角色移动至边缘的现象，并非前端表现层插值，而是寻路规划层吸附逻辑的直接结果。

MOD 开发结论：

• 16 格对应 6.4 世界单位。目标点距最近可行走格超过 16 格时寻路直接判定失败，单位不会尝试部分趋近。
• 吸附计算取世界坐标欧氏最近距离，非简单的曼哈顿或切比雪夫逐圈扩展，斜向边界处判定更为严格。
• 目标若触发吸附（ctx+64 置 1），将激活 §4.5 中的提前终止条件（最佳结点 $h < 2.0$ 即退出），可能导致单位在距离吸附目标约 1.41 格处停止移动。

4. A* 内核：结点、开闭表、代价、启发 ​

4.1 结点：64 字节 ​

主循环用 calloc(1, 0x40) 分配结点（push 0x40 @ 0x463ED7），布局按 DWORD 下标：

4.2 开表与闭表：单链表 + 线性扫 ​

开表 ctx+12、闭表 ctx+16，都是单链表（next 在结点 +60）。sub_463220（65 字节）按 f 升序插入，主循环每轮摘表头 ⇒ 等价于优先队列。

但按 index 找结点是线性扫链（while (node[5] != idx)），O(n)。这正是它需要迭代上限的原因。

4.3 ★★★ 代价恒 1.0，启发是距离的平方 ​

sub_4637B0 松弛一个邻居：

g = parent.g + 1.0        // fadd dword ptr [0x213C5DC]，该四字节现读 = float 1.0
h = (dx)² + (dz)²         // 单位是格²
f = g + h

两项关键特征：

1. 每步代价恒定 1.0：正交与斜向移动代价相同，度量标准为切比雪夫度量，而非欧几里得度量。
2. 启发函数为欧氏距离平方：$g$ 的度量单位为格，而 $h$ 的单位为格²。量纲不匹配导致 $h$ 远距离时呈平方级放大，启发函数不可采纳（Admissible 条件失效）。算法整体偏向贪心最佳优先搜索，无法保证生成最短路径。

代码佐证：sub_463650（266 字节）为专门负责向已闭合结点回传更优 g 值的逻辑。在经典 A* 中若启发函数严格可采纳，闭合结点的 g 值即为最优，无需回传；当启发不可采纳导致闭表结点可能被更优路径重新松弛时，方需此逻辑进行修正。

MOD 开发结论：怪物绕行、贴墙转弯或舍近求远等寻路表现，由底层启发函数的数学特性决定，并非 AI 决策层逻辑缺陷或碰撞半径配置错误。

4.4 迭代上限与部分路径 ​

if (i > *(DWORD*)(ctx+68)) break;      // cmp ebp, [esi+0x44] @ 0x463F8A

迭代计数超过上限后，搜索直接将 ctx+8（历史 h 最小结点）作为局部终点返回，并将 ctx+66 设为 0（标记非完整路径）。

MOD 开发结论：超大开阔场景中超远距离点击可能导致单位中途停步，系触发迭代步数上限所返回的截断路径。

4.5 提前终止退出：h < 2.0 ​

当目标曾触发吸附（ctx+64 置位）时，若当前搜索最优结点的启发值 $h < 2.0$（格²，即实际距离小于约 1.41 格），寻路立即提前终止并退出，同时标记 ctx+66 = 0。浮点常量 2.0 读取自 [0x2143F64]（fld dword ptr [0x2143F64] @ 0x463F76）。

注意触发前提：该逻辑仅在目标曾被吸附修正时生效。若目标初始即落在可走格上，搜索将严格推进至终点。

5. 8 邻域展开与净空规则分析 ​

5.1 8 邻域调用点静态核对 ​

sub_463940（1367 字节）负责邻域展开，汇编中调用 sub_4637B0 的 call 指令共有 8 处：

• sub_463940 内部包含 8 处 call sub_4637B0；
• 整个 .text 代码段中对 sub_4637B0 的交叉引用亦严格仅有 8 处；
• _realfuncs.json 统计显示 sub_4637B0 仅被单个函数调用。

结点数据结构中偏移 [7..14] 预留了 8 个后继结点槽位（cmp ecx, 8 @ 0x463881），在结构层面印证了 8 邻域模型。

5.2 净空与拐角约束 ​

正交移动约束表明：单格宽度（0.4u）的狭缝无法被规划算法选为通路。即便狭缝内各格子 isWalkable 均返回可通行，由于缺乏侧向净空格，寻路算法依然会拒绝规划穿行。

5.3 ★★ 可行走判定与路径规划判定的分离机制 ​

两者在引擎中具有明确分工：

二者互不冲突：“单位可以被放置于单格宽缝隙中站立”与“寻路规划器拒绝将单位规划穿过单格宽缝隙”同时成立。

MOD 开发结论：

• 场景通路设计须保持至少 2 格宽度（0.8u）。单格宽度的通道即使在 .mpp 中刷为可走，寻路算法亦无法生成穿越路径。
• 摆放装饰物与绘制走格时，通道余量应依据规划净空规则评估，而非仅以单点可站立为准。

6. 字节锚点表 ​

下表列出本文所有关键结论的 PE 字节级锚点。每一条都可以在 Torchlight2.exe 里按虚地址直接核对。

7. 发行地图走格的连通分量普查 ​

用 tools/f2_walkgrid_reach.py 离线读七张验收图导出的走格（四邻域洪泛），分量阈值 200 格（≥ 200 算「主要分量」，否则算碎屑）。「最近可走格」一列以复刻实现侧的合成出生点 (132.0, 44.0) 为基准。

七张里 3 张的「最近可走格」不在主分量上。echopass_pb 最极端：主分量 53,709 格，最近可走格却落在一块 129 格（0.1%）的碎屑上。

MOD 开发结论：

• 引擎内部不存在“最大连通分量”的概念。目标吸附仅在 ±16 格范围内寻找欧氏距离最近的可行空格，不预先验证该空格与起点是否处于同一连通块；若不可达则寻路直接失败。
• 地图全局“可行走”不代表“任意两点可互相到达”。拼装地图中被水体、悬崖物理阻隔划分的孤岛属于正常地形；但若将出生点、传送门或关键 NPC 放置在孤立碎屑连通分量中，将导致逻辑死锁。

8. 场景物理碰撞与走格阻挡解耦分析（幽灵墙现象） ​

8.1 现象复现与微观抖动 ​

在 echopass_jd（seed 1234）场景测试中，移动状态机出现持续卡顿：无法移动至目标点，解卡逻辑持续触发（849 次），坐标在 $x = 45.3$ 与 $45.7$ 之间往复振荡，振幅严格等于单次解卡步长（0.4u）。

8.2 阻挡源排查定位链路 ​

1. 启用碰撞体检测，获取产生阻挡接触的具体碰撞体名称：col_Room_Piece0_clone723428_85，法线方向为 (0.96, 0.00, 0.29)，呈现朝向 +X 的竖直阻挡面。
2. 前方每 0.4u 发射垂直射线检测地面高度剖面：0.00 / 0.00 / 2.00 / 1.72 / 0.79 / 0.00 …，证实前方存在约 2.0u 的高度突变，台阶攀爬判定正确拒绝（最大攀爬高度限制为 0.6u）。
3. 将走格通行性与物理几何模型映射至同一网格比对：走格整行全部显示为可行走，而几何模型上呈现 1.1–4.0u 的隆起带。
4. 追溯场景模型资源节点：对应 Mesh 路径为 props/z1tundra_props/rock_06.res（独立石头模型）。

8.3 通行阻挡裁决机制定性 ​

早期移植管线根据模型资源命名包含 rock 将其归入 OBSTACLE_KEYS 并挂载了实心 3D 碰撞体。然而发行 .mpp 走格数据中该位置标记为可行走。

原版走格具有唯一裁决权：Torchlight II 客户端在角色常规通行中不依赖 3D Mesh 物理碰撞体，能否通行完全由 CLevel::isWalkable（sub_5DB690）单点查表决定。场景装饰物（如石头、路障模型）在原版中不具备实体碰撞阻挡效果，角色穿透模型通过属于符合原版设计的行为。

8.4 官方场景资源普查统计 ​

通过工具扫描官方场景瓦片，比对模型分类与底层走格的可通行性：

echopass_jd 典型样例如下：

8.5 调试过程中的常见误区与工具校验陷阱 ​

1. 碰撞射线误判落脚面：排查初期将模型高度抬升误认为桥面落脚点，反复调整高度解卡逻辑无果。后经核查发现测试射线未配置 collision_mask，射线击中 OBSTACLE 层而非 GROUND 真实可行走地形。
2. 正则边界导致普查漏检：早期普查脚本对瓦片节点末尾 groups=["tl2_room_piece"] 中的闭合括号解析错误，导致含组属性的房间瓦片被全部过滤。后引入端到端基准对照机制（以实测卡顿节点作为强制测试样本），消除工具解析偏差。

8.6 MOD 制作与关卡设计准则 ​

• ★★★ 装饰道具不产生通行阻挡：通行性完全由 .mpp 走格数据决定。单纯摆放石头、木箱等装饰模型无法阻挡角色；若需形成阻挡，必须在走格数据中将对应格子刷为阻挡。
• ★ 避免空气墙事故：若在 .mpp 中刷为阻挡但视觉上无任何模型覆盖，将导致玩家遭遇“空气墙”。
• ★ 重制与移植建议：若基于资源名称规则自动生成 3D 碰撞体，必须与 .mpp 走格数据进行双向对账校验，防止生成阻挡原本可行走的幽灵墙。

9. 移植与复刻实现口径对照 ​

本节对照重制与移植开发中的算法参数与行为差异：

幽灵墙临时工程处理方案：在物理层发生卡顿时，临时从碰撞检测掩码中剔除装饰碰撞层，待移动指定位移或超时后恢复；关卡生成期根据走格数据过滤重合碰撞体方为根本解决方案。

10. 未闭环事项清单 ​

附录 A：核心符号与虚拟地址表（Torchlight2.exe，ImageBase 0x400000） ​

附录 B：支撑源材料与逆向结论映射 ​

• 逆向验证项：
  • 走格寻路：8 邻域展开模型、切比雪夫移动代价与平方启发函数；可行走与路径规划判定分离；
  • 碰撞解耦：静态装饰道具碰撞与 .mpp 走格阻挡解耦机制、场景幽灵墙普查分析。
• 数据结构与静态配置清单：walkgrid_pathfinding.json、phantom_walls.json。
• 分析工具：tools/f2_walkgrid.py（走格导出）、tools/f2_walkgrid_reach.py（连通分量普查）、tools/f2_phantom_walls.py（装饰物与走格重合普查）。