寻路、导航图与群体移动
寻路输出的是一条允许通行的路线,移动系统负责沿路线行动,碰撞系统负责实际几何约束,局部避让负责临时让开其他角色。把它们混成一个“朝玩家走”的函数,容易出现穿墙、卡角和成群重叠。先区分全局路线与局部执行,才能判断故障究竟出在哪层。
算法看到的是图
节点可以是格中心、房间、路点或导航多边形;边表示允许的移动。四邻接网格不能斜走,八邻接要决定斜向代价以及是否允许切过两个墙角。角色有体积时,可走格需要考虑半径,不能只让一个点穿过窄缝。更换导航表示,常比在错误图上优化算法更有效。
等权图用 BFS 可求最少边路径;非负权重图用 Dijkstra;A* 在已走代价 g 上加入到目标的估计 h,按 f=g+h 选择探索方向。权重可以表达泥地、危险或拥挤,但单位必须一致:若 g 以时间计,h 也应估算时间,不能直接加屏幕像素距离。
四邻接、每步代价为 1 时,曼哈顿距离 abs(dx)+abs(dy) 是常用启发;允许等价或根号二斜步时应选相应下界。h=0 时 A* 退化为 Dijkstra。要保证最短路径,启发应不高估,且实现应正确处理更优路径和必要的重新打开;采用一致启发可简化某些关闭集处理。提高 h 权重可能更快,但不再保留同样的最优性保证。
看懂核心松弛步骤
type Edge = { to: number; cost: number };
function relax(current: number, edge: Edge, goal: number,
g: Map<number, number>, parent: Map<number, number>,
heuristic: (a: number, b: number) => number,
push: (id: number, priority: number) => void) {
const nextCost = g.get(current)! + edge.cost;
if (nextCost >= (g.get(edge.to) ?? Infinity)) return;
g.set(edge.to, nextCost);
parent.set(edge.to, current);
push(edge.to, nextCost + heuristic(edge.to, goal));
}
这只是松弛片段:完整实现还需最小优先队列、起点初始化、过期队列项处理、终点出队判断、无路返回和路径反推。不要第一次发现终点就立刻结束,因为可能仍有更低总代价路径。路径反推从终点沿 parent 回到起点再反转;若终点未被到达,应返回明确失败而非伪造直线。
小图可以先用简单数组按最小值取出,便于验证;节点多或查询频繁再使用堆。优化不能删掉“新路径是否更优”的检查。调试覆盖层显示 open/closed、g/h/f 与 parent,能快速分辨队列排序、权重与启发错误。
路线还不是运动
角色沿路径点移动时要有到达阈值与越过处理,不能每步固定移动后在目标两侧抖动。可合并共线点,或使用可见性检查做平滑;平滑线段必须用角色体积检查通行,不能把墙角直接切掉。输出折线看起来不漂亮,有时只是存在多条同成本路径;固定 tie-break 能稳定外观与回放。
目标移动时无需每帧对每个怪重算完整路径。可以按时间间隔、目标换格、路径被阻断或距离阈值触发,给每帧重算设置预算。大量单位追同一目标时,可评估从目标反向计算的距离场/流场;它复用全局信息,但动态障碍、不同体型与局部避让仍要处理。
局部避让可以从简单分离力或占格预约开始;若每只怪只追下一个路径点,就可能挤在门口。分离力又不能把它们推过墙,需要与碰撞约束配合。复杂多人避让是额外系统,不应靠反复运行 A* 期待自然解决。
动态地图需要版本与失效策略
门打开、障碍销毁后,导航图版本改变;缓存路径应标记依赖的地图版本或区域,按需失效。若单位已无法通过下一段路线,应停止、重算或选择替代目标,不要一直顶墙。一次异步寻路完成时,还要确认单位仍存活、目标未换、请求代次仍有效,防止旧路线覆盖新命令。
Creator 负责地图转换、调试绘制和路径执行,核心图搜索可以是无引擎依赖 TypeScript,便于在 实验室 对固定图验证。不要把 Creator 的 3D 导航能力或某个插件自动当成 2D 网格完整方案。微信真机需要评估寻路尖峰与群体实例更新,浏览器算法耗时不能直接外推手机。
故障用最小地图复现
穿墙查邻居生成、网格转换与半径;绕远查权重与启发单位;无路死循环查访问和队列;终点在墙内查目标投影;密集单位卡门查局部避让与通道容量。先用 5×5、7×7 的手工图与 Dijkstra 对照,再测大图,能避免在复杂关卡里误判算法。
目标选择与路径成本相互影响
终点不可走时,可以拒绝命令、选择最近可达邻格或接近到攻击距离,但三者产生不同体验。最近的欧氏距离格也可能位于墙另一侧,因此替代终点需要考虑连通区域与实际路径代价。远程怪物不必走到玩家中心,选择有视线且在射程内的位置,往往比不断重算到玩家格更符合行为目标。
负权重不适用于这里的 Dijkstra 与 A* 合同;若奖励格被写成负代价,可能出现绕圈降低总代价的情况。奖励偏好可以转换为非负成本或在目标选择层处理,而不是直接破坏搜索假设。零成本边也要谨慎处理启发下界,不能继续假设每走一步至少花一个单位。
地图扩大时,房间图或分层导航能先确定经过哪些区域,再在局部求细路径。缓存应围绕真实重复查询,避免为每个敌人保存大量几乎不用的全图数据。追同一目标的距离场需要明确更新周期和障碍版本,玩家每移动一点就全图重建也可能比单次 A* 更贵。
行为验收要看单位是否完成任务,而不只是搜索函数返回数组。路线有效却走不完,可能是到达阈值、速度、碰撞或局部拥堵问题;路线无效则回到导航图与搜索。为这两层分别记录失败原因与耗时,能防止 AI 反复修改启发函数去修复一个实际上属于移动控制的卡墙问题。
AI 的导航任务
实现纯 TypeScript 四邻接 A*,支持非负格子成本、稳定 tie-break、无路返回与路径成本。用 BFS/Dijkstra 做小图对照,Creator 3.8.8 负责显示与执行。加入地图版本、重算预算和请求代次;提供不可达目标、门开关、窄通道与多单位压力场景。
验收:起终点相同、完全隔离、绕障碍和加权地形结果正确;路径相邻段合法且总代价匹配对照;不会斜穿墙角;旧请求不覆盖新目标;每帧重算数量封顶。性能记录包含图大小、扩展节点数与查询次数,并分开标注 Web 与微信真机。
来源与适用边界
核查日期:2026-11-17。示例目标 Creator 3.8.8,算法片段非完整实现;本文未执行性能试验。
- Red Blob Games:A* 介绍,作者的一手交互解释。
- Red Blob Games:A* 实现与排错,核对代价松弛、启发与队列边界。