论文解析：基于 A* 的 Minecraft 机器人寻路系统改进

本文是对论文《基于 A* 的 Minecraft 机器人寻路系统改进：路径平滑、3D 邻域建模与安全执行》的解析（论文原文）。论文作者为 K2CrO4__，代码库为 MCCTeam/Minecraft-Console-Client（MCC，C#/.NET 10，Minecraft 26.2 实测）。

论文概况#

MCC（Minecraft Console Client）的自动化能力依赖内置的 A* 网格寻路。平坦地形可用，但遇到人造建筑（楼梯、楼顶、1 格宽平台、深坑、梯子）就暴露出一系列问题：贴边锯齿走、爬不上 1 格台阶、跳楼梯中途滑落、平台踏空坠落、卡墙角无限重规划、爬梯被梯子方块卡死、远目标一次搜索数百万节点。

论文的核心贡献是两代共 19 项改进，覆盖两个层面：

规划层（Movement.cs）：在方块网格上搜出路
执行层（McClient.cs 及物理/碰撞模块）：每 tick（20 TPS）把路点转成物理输入

第一代（3.1–3.9 节）解决基础地形可通行性；第二代（3.10–3.19 节）面向大型迷宫、联机实机与长距离导航。验证结果：48/48 单元测试通过；Backrooms 迷宫 2 分 00 秒走完约 160 格，仅 3 次重规划；完整爬过多架 1 格宽梯子；240+ 格远目标通过分段规划持续推进。

问题清单#

编号	现象	根因
P1	贴边、锯齿状行走	路径是逐格中心折线，没有直线化
P2	爬不上 1 格高台阶	移动生成器没有”斜上跨步”，只能原地直跳（跳进空气）
P3	爬楼梯后边缘滑落	跳跃中途就判定”到达”，提前推进路点
P4	1 格宽平台踏空坠落	执行层不探测前方脚下是否有地面
P5	卡拐角/墙边反复跳	无卡住检测，重规划可无限循环
P6	直线路径穿过楼顶缺口	路径平滑没检查采样列的脚下支撑
P7	斜穿拐角扫到深坑	斜向移动没检查两侧直角格
P8	迷宫搜索 40 万+ 节点超时	平方距离启发式严重高估 H，A* 退化为贪心
P9	`-f` 模式走进虚空被弹回	无支撑虚空格被当可行走，执行层又误信陈旧缓存
P10	原地”小碎步”永不前进	服务器位置包钉回朝向 + 解卡差半步 + 重规划计数被杠杆效应卡死
P11	爬梯卡死/滑脱/无法翻顶	梯子被当实心方块、爬升依赖水平碰撞、梯子顶无法跳跃
P12	远目标在未加载地形上展开数百万节点	一次性全量搜索，未考虑区块流式加载

十个旧问题里有六个（P1-P7）是规划与物理执行脱节：规划器认为能走，执行器做不到。网格搜索的邻居生成必须与真实物理移动能力对齐。

第一代改进（3.1–3.9）：让路径可执行#

路径平滑（P1/P6）：贪心视线裁剪——锚点到候选路点之间的直线段（考虑碰撞盒半径 0.3 格，每 0.25 格采样）全程可通行则跳过中间路点。采样列必须”3 格内有地面支撑”，否则平滑会把路径压平跨过楼顶缺口
斜上跨步（P2）：生成 (Δx, +1, Δz) 节点——相邻格是 1 格高实心方块且目标格可容纳时视为合法移动；同列 Up 收紧为仅限攀爬/游泳
斜向安全约束（P7）：斜向移动除目标格外，两个相邻直角格也必须安全
物理一致的到达判定（P3）：水平 <0.7 格 + 垂直 <0.6 格 + 处于落地/攀爬/游泳状态，三条件缺一不可。路点在方块中心（Y+0.5）、脚在方块顶（Y+1），只比水平距离会在跳跃中途误判”到达”
卡住检测与自动重规划（P5）：落地状态 3 秒无水平进展即重规划；只有”距目标净前进 >1 格”才重置计数，连续 5 次无进展取消移动
自动跳跃（P3 执行侧）：探测正前方 0.7 格，有 1 格高台阶且上方两格可通行时轻跳，不冲刺
边缘探测（P4）：前方格子 2 格内无地面支撑即停步
居中校正（P7 执行侧）：两侧都是悬崖（1 格宽走廊）时，行进方向叠加回格中心的修正向量

第二代改进（3.10–3.19）：大迷宫、联机与远距离#

搜索层（3.10–3.12）#

真实距离启发式：旧实现用平方距离做 H，26 格远的目标评分 712 而不是 26，A* 退化为贪心，展开 40 万+ 节点。换成欧氏距离后降到 1~3 千。启发式不可采纳会让 A* 失去回溯能力
JPS 跳点搜索：JumpRecursive 沿方向连续前进，只在目标格、强制邻居、垂直过渡点、悬空/未加载边缘处产出跳点；开阔走廊压缩为首尾两个跳点
双向 A*：正反向同时搜索，反向邻居与正向共享同一支撑规则，防止把正向不可达的虚空格引入路径
异步搜索：搜索挪到后台任务，120 秒超时；主循环每 tick 检查完成并接管，重规划不阻塞 20 TPS 物理循环

联机信任（3.13–3.15）#

虚空拦截与服务器信任（P9）：-f 模式下规划层对未加载区块”视为未知并放行”，已加载的无底虚空列不生成边；执行层完全跳过客户端缓存边缘探测，只靠服务器物理与重规划兜底。背景是实测发现客户端区块缓存与服务器存档不一致（同一坐标服务器是 yellow_concrete_powder，客户端缓存返回 Air）——缓存缺失会被当成”虚空”
朝向接管（P10）：服务器每 ~20 tick 回显位置包，把客户端 yaw 钉回旧值，yaw=0 是合法值，每 tick 覆盖物理朝向，路点朝向被抵消。修复：路径活跃期间完全忽略 yaw/pitch 钉扎，每 tick 无条件清除
定点解卡（P10）：碰撞后锁定解卡朝向 12 tick 连续移动，一次走完脱困距离（原实现修正量被远处路点方向稀释，永远差 0.07 格）

新增：爬梯与长距离导航（3.16–3.19）#

爬梯执行层（P11）：梯子从”实心方块”改为可穿过，爬升从”依赖水平碰撞”改为”有移动输入即爬升”；执行层先走到梯子格中心再贴墙爬，到顶后跳跃翻出。修梯子要动三层——碰撞形状、爬升物理、输入生成，任何一层按实心墙处理都会静默失败
联机位置同步与未知地面：服务器回显会把本地物理 Teleport 回上一已知点、清零速度——路径活跃且差距 <2 格时忽略回显，本地物理为权威，传送/大差距仍强制同步；未加载区块导致”物理悬空”时跳过重力并强制 OnGround，等区块流式加载
搜索预算与重规划计数：CalculatePath 增加节点预算（首段 40 万），耗尽时返回”离目标最近的已展开节点”到起点的前缀路径，先出发再续段；重规划计数改用线性距离比较（平方距离在远目标时 0.15 格抖动会被误判为进展，计数永不归零）
路上规划（分段导航）（P12）：路径终点到达后未到最终目标则自动以当前位置为起点发起下一段搜索（段数 <20，续段预算翻倍）；服务器回弹检测——客户端推进但位置被服务器拉回，累计 30 tick 触发重规划；未知地形感知细化到 Y section 级，区块加载等待最长 60 秒

四条关键经验#

邻居生成必须与物理执行能力一致（可落地的过渡），且启发式必须可采纳——平方距离启发式的高估是大型迷宫搜索爆炸的根源
执行层必须持续感知环境，但缓存探测只能用于安全模式：客户端区块缓存与服务器不一致时，-f 应信任服务器物理并以重规划兜底
联机联调时，朝向这类”看起来无害”的状态会被服务器位置包周期性覆盖，路径执行必须显式接管所有权
特殊方块（梯子）不能只修寻路器：碰撞形状、爬升物理、输入生成三层必须一致

验证数据#

单元测试：48/48 通过（38 个既有 + 10 个新增）
障碍路线：9 级无护栏楼梯 + 楼顶 + 1 格宽平台 + 深坑，机器人从 Y=112 逐级上行到 Y=121/122 并绕坑到达目标
Backrooms 迷宫：固定起点 (-176.12, 19, -308.32)，2 分 00 秒走完约 160 格到达目标 0.5 格内；首次搜索 65 路点 / 20,130 节点；全程 3 次重规划。改进前同一协议下机器人陷入”小碎步”，数分钟无净进展
爬梯验证：修复前卡在梯子格内 y=20.20 或爬到顶滑回循环；修复后第一架梯子 y 19.00 → 20.06 → 22.55 → 23.00 连续爬升并翻顶，居中偏差收敛到 0.01~0.1 格
远距离目标：240+ 格目标通过分段规划，首段约 2 分钟等待区块加载后持续推进
归因验证：3.13/3.14/3.15 缺一不可——去掉 3.14 卡在起点；只保留 3.14 会在 -214.70 反复顶墙

局限与展望#

论文自列待办：统一安全坠落深度配置、SimplifyPath 的 3D 直线平滑、楼梯/台阶半格形状建模（当前按整块实心处理）、-f 模式的服务器区块查询回退、未知区块搜索的预算与分段导航、把 Backrooms 迷宫（含多段爬梯）纳入官方集成测试。

其中半格建模是下一步的关键：Minecraft 楼梯、台阶、活板门的形状比整格复杂，支持它们需要把碰撞盒从”0.3 格半径圆柱”升级为精确形状，寻路会从方块级进入几何级。